Hello,
I have uploaded new versions of the primes package to Hackage:
http://hackage.haskell.org/package/primes
Version 0.2.0.0 significantly improves the memory requirements (and as
a result also the run time) compared to 0.1.1. The run time is now
almost linear and when streaming an infinite list of primes the memory
requirements are almost constant. I think, primes is now the most
efficient prime generator on Hackage.
The interface has been generalised to support arbitrary Integral types
and not just Integers and I have added two convenience functions:
isPrime :: Integral int => int -> Bool
primeFactors :: Integral int => int -> [int]
These functions can be used for numbers with moderately large prime
factors but are impractical when passing RSA numbers [1] because they
simply use trial division [2].
The performance improvements have also been implemented in version
0.1.1.1 which provides the old interface. As the only API changes (of
0.2) are additions and the generalisation to Integral types, switching
directly to 0.2 should be straightforward.
The implementation is similar to Melissa O'Neil's code on the Haskell
Wiki [3] which is one of the most efficient (pure) prime generators
(without an upper bound) in Haskell that I know of. My goal was to
simplify her implementation without sacrificing performance
significantly. The performance of the prime package now almost matches
the performance of Melissa's code. Judge for yourself whether you find
the implementation more readable:
http://github.com/sebfisch/primes/blob/0.1.1.1/Data/Numbers/Primes.hs
The 0.2 tarball contains (source, not binary) programs that can be
used to measure the performance of my implementation using Criterion
(runtime.hs) and checking the memory requirements when generating
large primes (memory.hs).
Cheers,
Sebastian
[1]: http://en.wikipedia.org/wiki/RSA_numbers
[2]: http://en.wikipedia.org/wiki/Trial_division
[3]: http://www.haskell.org/haskellwiki/Prime_numbers
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
