[Haskell-cafe] RE: [Announce] primes

[Geoffrey Irving]

On Thu, Apr 16, 2009 at 12:39 PM, Daniel Fischer
<daniel.is.fischer at 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