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

[Sjoerd Visscher]

On Nov 2, 2009, at 5:11 PM, Will Ness wrote:

> Sjoerd Visscher <sjoerd <at> w3future.com> writes:
>
>>
>> Excuse me, 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
>>
>
> Hi,
>
> I've run it now. In producing 100,000 primes, your above code takes  
> x3.5 more
> time than the one I posted.

Too bad. The order of the primes when filtering matters quite a lot!

> The code modified as I suggested with (qs++[p])
> takes exactly the same time as mine. :)

Yes, append and take are both O(n).

Here's another variation which I rather like:

primes = 2 : 3 : sieve (tail primes) (notDivides 3) 5
sieve (p:ps) test from
         = [x | x <- [from, from + 2 .. p * p - 2], test x]
           ++ sieve ps (\x -> test x && notDivides p x) (p * p + 2)
notDivides d x = (x `rem` d) /= 0

I'm curious if GHC can compile this to the same speed as your code.

--
Sjoerd Visscher
sjoerd at w3future.com