[Haskell-cafe] Re: Simple FAST lazy functional primes

[Will Ness]

Sjoerd Visscher <sjoerd <at> w3future.com> writes:

> [...] 2 doesn't have to be in the list of smaller primes, as  
> we're only generating odd numbers:
> 
> primes = 2 : 3 : 5 : 7 : sieve [3] (drop 2 primes)
> sieve qs@(q:_) (p:ps)
>         = [x | x<-[q*q+2,q*q+4..p*p-2], and [(x`rem`p)/=0 | p<-qs]]
>           ++ sieve (p:qs) ps
> 
> Sjoerd

Thanks!

I haven't tested your code's speed yet, but have few points:

i wouldn't expect eliminating a parameter to have any effect on performance in
compiled code (I haven't a clue whether -O2 or -O3 should be used BTW) if it
doesn't eliminate any superfluous computations.

second, you prepend bigger primes in front of a list (building the prefix in
reverse order); this will cause them to be tested against first. I think (1)
we're supposed to test composites against smaller factors first, for the tests
to stop sooner. IMO it'll slow the code down. I think (2) you can safely append
them at the end instead, for a compiler should be able to just maintain a tail
pointer there. But then you loose immediate access to the last found prime; so
will need to return the 'x' parameter back. Then you end up with my code exactly
:) (only replicating the prefix):

primes = 2 : 3 : 5 : 7 : sieve [3] (drop 2 primes) 9
sieve pfx (p:ps) x
       = [x | x<-[x+2,x+4..p*p-2], and [(x`rem`p)/=0 | p<-pfx]]
         ++ sieve (pfx++[p]) ps (p*p)

it'll be interesting to test my hypothesis (two of them :) ) and see if this has
in fact better time than your code.

thirdly, (take k) could be compiled out completely into a tail pointer too,
maintained and advanced after each step. I would hope a smart compiler to do
just that. Again, some more testing is in order. Although, I tested the two
approaches on some previous incarnation of this code, and the (take k) vs
(pfx++[p]) had exactly same run time (or was better).

What I'm after mostly here, is for the code to be clear and simple, and
reasonably efficient. Right now it corresponds very nicely to the description of
the sieve as filtering all the odds testable by a known prefix of primes, and
then going on to proceed with the next batch of them with a prefix that was
grown by one more prime. And so on.

But more importantly I want it to be known that there's a lot that can be done
here, in a natural functional lazy kind of way, before resorting to priority
queues and mutable arrays. We could always just use C too. ;)

Thanks for the feedback! :)