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

[Steve]

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.
http://www.haskell.org/haskellwiki/Prime_numbers
I've just updated the page to split it into "Finding Primes" and
"Testing Primality".

Steve