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

License | BSD |

Maintainer | wren@cpan.org |

Stability | experimental |

Portability | Haskell98 + BangPatterns |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

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`

.

# 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]