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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe