[Haskell-cafe] Re: Simple FAST lazy functional primes
Sjoerd Visscher
sjoerd at w3future.com
Mon Nov 2 11:24:58 EST 2009
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
More information about the Haskell-Cafe
mailing list