[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:
> 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
More information about the Haskell-Cafe
mailing list