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

Steve stevech1097 at yahoo.com.au
Thu Nov 5 05:32:38 EST 2009

On Tue, 2009-11-03 at 10:52 -0500, Will wrote:
> I've just tried it and it was twice slower than mine. (?) I didn't use
> the [Int]
> signature in both. Maybe it's not real issues we're dealing with here,
> but
> compiler/OS/CPU issues? (or have you've forgotten to put the [Int]
> signature
> into my code too, when tested? It runs twice as fast with it).
> Although your
> code has an advantage that it is very easy to add the wheel
> optimization to it.

I used [Int] for both. If you didn't use [Int] then it defaults to
[Integer] and you are probably testing the speed of GMP integer
operations (rather than the speed of Haskell Int operations) which could
give differing conclusions.

I had looked into using a wheel before. Its nice in theory, but not so
useful in practice. At least that's my experience where using a wheel
made the primes function slower.

> What I have now, is this:
>  qprimes   = 2: 3: sieve emptyQ primes' 5  where
>   primes'  = tail qprimes        
>   sieve q (p:ps) x                  
>            = h ++ sieve (addQ q' (2*p) (p*p+2*p)) ps (p*p+2)  
>              where
>                (h,q') = noComps q [x,x+2..p*p-2] 
>   ......

Adding your code and conclusions to "Prime numbers" on the Haskell wiki,
could be useful.
I've just updated the page to split it into "Finding Primes" and
"Testing Primality".


More information about the Haskell-Cafe mailing list