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.
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.
Thanks for the benchmarks!
I'm pretty sure it also uses less memory.
Do you understand the memory requirements of my implementation? I'm not sure if I do. Is it only that the queue of multiples gets larger and larger the more primes we query?
I want to find efficient algorithms for the other proposed functions before forking, but I figured I'd let you know in the meantime.
Thanks! Feel free to incorporate ideas from NaurPrimes.hs. I don't understand them yet. Cheers, Sebastian
Hello, On Thursday 16 April 2009 17:22, Sebastian Fischer wrote:
... Thanks! Feel free to incorporate ideas from NaurPrimes.hs. I don't understand them yet.
NaurPrimes.hs is derived from the EratoS.hs that you get from unpacking thorkilnaur.dk/~tn/Haskell/EratoS/T64_20070303_1819.tar.gz. EratoS.hs is explained in thorkilnaur.dk/~tn/Haskell/EratoS/EratoS2.txt. Please don't hesitate to ask questions about this. I'll do my best to answer.
...
Best regards Thorkil
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
On Thu, Apr 16, 2009 at 12:39 PM, 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
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
participants (5)
-
Daniel Fischer -
Geoffrey Irving -
Niemeijer, R.A. -
Sebastian Fischer -
Thorkil Naur