[Haskell-cafe] RE: [Announce] primes

[Daniel Fischer]

Am Donnerstag 16 April 2009 16:45:59 schrieb Niemeijer, R.A.:
> Sebastian Fischer wrote:
> > I am pleased to announce the package 'primes' that implements lazy
> > wheel sieves for efficient, purely functional generation of prime
> > numbers in Haskell.
> >
> > The implementation is reasonably efficient. The query
> >
> >  > primes !! 1000000
> >
> > 15485867
> >
> > answers after a few seconds.
> >
> > Feel free to contribute more functionality to this package. The
> > sources are on Github:
> >
> >      http://github.com/sebfisch/primes
> >
> > If you fork my project, I'll be happy to merge your changes.
>
> I have just finished benchmarking all the implementations provided in
> http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip (the zip file linked
> to from the Haskell wiki article on primes).
>
> NaurPrimes.hs is by far the fastest version, and at least 2 or 3 times
> faster than your current implementation. I'm pretty sure it also uses less
> memory. I want to find efficient algorithms for the other proposed
> functions before forking, but I figured I'd let you know in the meantime.

Nevertheless, a bitsieve is much faster:

Prelude NaurPrimes> length $ primesToLimit (10^8)
5761455
(26.50 secs, 5734921092 bytes)
Prelude NaurPrimes> :l
Ok, modules loaded: none.
(0.00 secs, 0 bytes)
Prelude> :m +Euler.Primes
Prelude Euler.Primes> length $ primesUpTo (10^8)
Loading package base-3.0.3.0 ... linking ... done.
Loading package euler-0.1 ... linking ... done.
5761455
(2.14 secs, 573050276 bytes)

The problems for a bitsieve are
a) you don't easily get the small primes before sieving is complete
b) how to proceed after the sieving bound