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

[Melissa O'Neill]

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.