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

[Lennart Augustsson]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe