[Haskell-cafe] ANN: primes-0.2.0.0

[Sebastian Fischer]

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.)