--------------------------------------------
-- combinatorics 0.1.0
--------------------------------------------
The 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.)
--------------------------------------------
-- Long Description
--------------------------------------------
* Math.Combinatorics.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.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.Factorial: offers a fast computation of factorial
numbers. As Peter Luschny comments[1], 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.
[1] http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
--------------------------------------------
-- Links
--------------------------------------------
Homepage:
http://code.haskell.org/~wren/
Hackage:
http://hackage.haskell.org/package/combinatorics
Darcs:
http://community.haskell.org/~wren/combinatorics
Haddock (Darcs version):
http://community.haskell.org/~wren/combinatorics/dist/doc/html/combinatorics
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
