ANN: exact-combinatorics

[winterkoninkje]

exact-combinatorics 0.2.0

The exact-combinatorics package offers efficient exact computation of common combinatorial functions like the binomial coefficients and factorial. (For fast approximations, see the math-functions package instead.)

Description

Math.Combinatorics.Exact.Primes

Provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.)

Math.Combinatorics.Exact.Binomial

Offers a fast computation of the binomial coefficients based on the prime factorization of the result. As it turns out, it's easier to compute the prime factorization of the answer than it is to compute the answer directly! And you don't even need the factorial function to do so. Albeit, with a fast factorial function, the naive definition of binomial coefficients gives this algorithm a run for its money.

Math.Combinatorics.Exact.Factorial

Offers a fast computation of factorial numbers. As Peter Luschny comments, the factorial function is often shown as a classic example of recursive functions, like addition of Peano numbers, however that naive way of computing factorials is extremely inefficient and does a disservice to those learning about recursion. The current implementation uses the split-recursive algorithm which is more than sufficient for casual use. I'm working on implementing the parallel prime-swing algorithm, which should be a bit faster still.

Links

• Homepage: http://code.haskell.org/~wren/
• Hackage: http://hackage.haskell.org/package/exact-combinatorics
• Darcs: http://community.haskell.org/~wren/exact-combinatorics
• Haddock: Darcs version