# [Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

Thorkil Naur naur at post11.tele.dk
Tue Jul 24 19:42:23 EDT 2007

```Hello Melissa,

On Tuesday 24 July 2007 19:09, Melissa O'Neill wrote:
> apfelmus wrote:
> > After some pondering, the  List a  data structure for merging is
> > really
> > ingenious! :) Here's a try to explain how it works:
>
> Thanks apfelmus!  A detailed explanation of this code is really
> helpful for anyone trying to understand what is going on.  The VIP/
> Crowd analogy is also very nice.
>
> > I think that this approach has the potential to outperform O'Neill's
> > (old?) code because it doesn't incorporates another prime number to
> > the
> > sieve mechanism until it really has to. I mean the following: in the
> >
> >  1st, 2nd, 3rd, 4th, ...  step,
> >
> > O'Neill's code adds the multiples
> >
> >  2*2, 3*3, 5*5, 7*7, ...
> >
> > to the priority queue and uses them to sieve for potential prime
> > numbers
> > from then on.
>
> Yeah, that's (only) what the code in my paper does -- it's good
> enough for explicative purposes, but all recent versions have used a
> slightly augmented priority queue.  It's a priority queue coupled
> with a "feeder list" that provides entries to add to the queue (in
> increasing order).  They are only admitted to the heap data structure
> only once when the root of the heap "gets there".
>
> The two most important bits are:
>
> 	type HybridQ k v = (PriorityQ k v, [(k,v)])
>
>          -- postRemoveHQ  is called when the min element of the heap
> has changed
>          postRemoveHQ :: Ord k => HybridQ k v -> HybridQ k v
>          postRemoveHQ mq@(pq, []) = mq
>          postRemoveHQ mq@(pq, (qk,qv) : qs)
>              | qk < minKeyPQ pq = (insertPQ qk qv pq, qs)
>              | otherwise        = mq
>
>
> primes.zip for the complete code.  I've also added Thorkil Naur's
> code from March, which is also a good performer,

Do you have detailed measurements that you wish to share? I would be most
interested, I assure you.

> although its another
> case where most readers would find a detailed explanation of the code
> instructive.)

I'll do my very best to provide such an explanation within, say, the next
couple of weeks.

>
> > the approach here adds 5*5=25 to the heap only after considering
> > the 9th prime 23.
>
> Yep, that's what mine does too.
>
> Best Regards,
>
>      Melissa.
>
> _______________________________________________