Copyright | Copyright (c) 2011--2015 wren gayle romano |
---|---|

License | BSD |

Maintainer | wren@community.haskell.org |

Stability | experimental |

Portability | Haskell98 + CPP |

Safe Haskell | Safe |

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]