[Haskell-cafe] ANN: exact-combinatorics (re-release of combinatorics)
wren ng thornton
wren at freegeek.org
Fri Feb 3 06:39:15 CET 2012
--------------------------------------------
-- exact-combinatorics 0.2.0
--------------------------------------------
I've chosen to rename the combinatorics package to exact-combinatorics
to make it clearer what the purpose of the package is. Anyone
repackaging things for individual distros should use the new package and
not bother with the old one. Sorry for the noise and confusion.
Along the way I've also moved the Math.Combinatorics.* modules to
Math.Combinatorics.Exact.* so as not to claim the whole
Math.Combinatorics namespace. The code is otherwise unchanged so far.
The original announcement is below.
On 1/28/12 11:06 PM, wren ng thornton wrote:
> --------------------------------------------
> -- 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Live well,
~wren
More information about the Haskell-Cafe
mailing list