[Haskell-cafe] RE: [Announce] primes
r.a.niemeijer at tue.nl
Thu Apr 16 10:45:59 EDT 2009
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
> answers after a few seconds.
> Feel free to contribute more functionality to this package. The
> sources are on Github:
> 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.
More information about the Haskell-Cafe