On Thu, Apr 16, 2009 at 12:39 PM, Daniel Fischer <daniel.is.fisc...@web.de> wrote: > 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
You can solve both of these by always sieving up to powers of 2. If you've sieved up to 2^n you can extend it to 2^(n+1) by restarting the sieve and using the fact that you don't need to recheck the first half of the range. The result shouldn't be much slower than a full sieve, and can probably be written entirely with unboxed array monads (no unsafePerformIO) if desired. Geoffrey _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
