[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)

Melissa O'Neill oneill at cs.hmc.edu
Fri Feb 23 00:27:15 EST 2007

```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