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

CopyrightCopyright (c) 2011--2019 wren gayle romano
LicenseBSD
Maintainerwren@community.haskell.org
Stabilityexperimental
PortabilityHaskell98 + BangPatterns
Safe HaskellSafe
LanguageHaskell98

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 -> a Source #

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]