[Haskell-cafe] Looking for the fastest Haskell primes algorithm

[ajb at spamcop.net]

G'day all.

Quoting Dan Weston <westondan at imageworks.com>:

> Unless primesUpTo n goes from highest to lowest prime (ending in 2), I
> don't see how sharing is possible (in either space or time) between
> primesUpTo for different n.

Given that it's a mistake for a library to leak memory, there are
essentially three possibilities: Make the implementation impure, move
responsibility onto the application, or only retain a finite number
of primes between calls.

This library:

     http://andrew.bromage.org/darcs/numbertheory/

only retains primes up to product [2,3,5,7,11,13,17], for several
reasons:

     - It's convenient for the wheel algorithm to store all primes up
       to the product of the first k primes for some k.
     - It's ultra-convenient if the stored primes can fit in machine
       words.
     - For the types of numbers that we typically care about, it's
       useful to store at least all primes up to 2^(w/2) where w
       is the machine word size.
     - Storing more than a million seemed wrong.

Cheers,
Andrew Bromage