How did you compare the C version with the Haskell versions? The Haskell programs produce the Nth prime, whereas the C code produces the last prime less than N. To make the C code to what the Haskell code does you need to set some upper bound that is related to the prime number distribution. I see no trace of this in your code. -- Lennart On Feb 23, 2007, at 05:27 , Melissa O'Neill wrote:
Bulat Ziganshin asked:
but how it looks compared with classic C implementation of sieve algorithm?
It's still worse. I Googled for a "typical" implementation and added it to the collection. The best Haskell implementation is still about two orders of magnitude slower, but remember that the Haskell versions we'd looked at so far are able to incrementally produce a list of primes of arbitrary length.
Andrew Bromage wrote:
Just to fill out the implementations:
http://andrew.bromage.org/darcs/numbertheory/
Math/Prime.hs has an implementation of the Atkin-Bernstein sieve.
Cool, thanks. When I ran your code trying to find the 10,000th prime, I got AtkinSieveTest: Ix{Integer}.index: Index (36213) out of range ((0,36212)) but that went away when I made your array one bigger.
Here's the updated table...
------------------------------------------------------------------ Time (in seconds) for Number of Primes ---------------------------------------------------- Algorithm 10^3 10^4 10^5 10^6 10^7 10^8 ------------------------------------------------------------------ C-Sieve 0.00 0.00 0.01 0.29 5.12 88.24 O'Neill (#2) 0.01 0.09 1.45 22.41 393.28 - O'Neill (#1) 0.01 0.14 2.93 47.08 - - Bromage 0.02 0.39 6.50 142.85 - - "sieve" (#3) 0.01 0.25 7.28 213.19 - - Naive 0.32 0.66 16.04 419.22 - - Runciman 0.02 0.74 29.25 - - - Reinke 0.04 1.21 41.00 - - - Gale (#1) 0.12 17.99 - - - - "sieve" (#1) 0.16 32.59 - - - - "sieve" (#2) 0.01 32.76 - - - - Gale (#2) 1.36 268.65 - - - - ------------------------------------------------------------------
Notes: - Bromage is Andrew Bromage's implementation of the Atkin-Bernstein sieve. Like O'Neill (#2) and "sieve" (#3), asks for some upper limit on the number of primes it generates. Unlike O'Neill (#2) and "sieve" (#3), it uses arrays, and the upper limit causes a large initial array allocation. Also, unlike the other Haskell algorithms, it does not produce a lazy list; no output is produced until sieving is complete - C-Sieve is a "typical" simple implementation of the sieve in C found with Google; it skips multiples of 2 and uses a bit array. Also, obviously, it doesn't produce incremental output.
I've also updated the zip file of implementations at http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip
Enjoy,
Melissa.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe