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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
