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