exact-combinatorics-0.2.0.4: Efficient exact computation of combinatoric functions.

Portability Haskell98 + CPP experimental wren@community.haskell.org Safe-Inferred

Math.Combinatorics.Exact.Factorial

Description

The factorial numbers (http://oeis.org/A000142). For negative inputs, all functions return 0 (rather than throwing an exception or using `Maybe`).

Notable limits:

• 12! is the largest factorial that can fit into `Int32`.
• 20! is the largest factorial that can fit into `Int64`.
• 170! is the largest factorial that can fit into 64-bit `Double`.

Synopsis

# Documentation

factorial :: (Integral a, Bits a) => Int -> aSource

Exact factorial numbers. For a fast approximation see `math-functions:Numeric.SpecFunctions.factorial` instead. The naive definition of the factorial numbers is:

``` factorial n
| n < 0     = 0
| otherwise = product [1..n]
```

However, we use a fast algorithm based on the split-recursive form:

``` factorial n =
2^(n - popCount n) * product [(q k)^k | forall k, k >= 1]
where
q k = product [j | forall j, n*2^(-k) < j <= n*2^(-k+1), odd j]
```