G'day all.
Quoting Dan Weston <weston...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
