Copyright | Copyright (c) 2011--2015 wren gayle romano |
---|---|
License | BSD |
Maintainer | wren@community.haskell.org |
Stability | experimental |
Portability | Haskell98 + CPP |
Safe Haskell | Safe-Inferred |
Language | Haskell98 |
The factorial numbers (http://oeis.org/A000142). For negative
inputs, all functions return 0 (rather than throwing an exception
or using Maybe
).
Notable limits:
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]