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

Lennart Augustsson lennart at augustsson.net
Sat Feb 24 13:10:41 EST 2007

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

>> but how it looks compared with classic C implementation of sieve
>> algorithm?
>
> It's still worse.  I Googled for a "typical" implementation and
> 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
>
> Enjoy,
>
>     Melissa.
>
> _______________________________________________