[Haskell-cafe] Looking for the fastest Haskell primes
algorithm
ajb at spamcop.net
ajb at spamcop.net
Sun Apr 19 20:29:29 EDT 2009
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
More information about the Haskell-Cafe
mailing list