[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.
http://www.haskell.org/haskellwiki/Prime_numbers
I've just updated the page to split it into "Finding Primes" and
"Testing Primality".
Steve
More information about the Haskell-Cafe
mailing list