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

License | BSD |

Maintainer | wren@community.haskell.org |

Stability | experimental |

Portability | Haskell98 |

Safe Haskell | Safe |

Language | Haskell98 |

Binomial coefficients (http://oeis.org/A007318), aka the count
of possible combinations. For negative inputs, all functions
return 0 (rather than throwing an exception or using `Maybe`

).

# Documentation

choose :: Integral a => a -> a -> a Source #

Exact binomial coefficients. For a fast approximation see
`math-functions:Numeric.SpecFunctions.choose`

instead. The naive
definition of the binomial coefficients is:

n `choose` k | k < 0 = 0 | k > n = 0 | otherwise = factorial n `div` (factorial k * factorial (n-k))

However, we use a fast implementation based on the prime-power
factorization of the result (Goetgheluck, 1987). Each time `n`

is larger than the previous calls, there will be some slowdown
as the prime numbers must be computed (though it is still much
faster than the naive implementation); however, subsequent calls
will be extremely fast, since we memoize the list of `primes`

.
Do note, however, that this will result in a space leak if you
call `choose`

for an extremely large `n`

and then don't need
that many primes in the future. Hopefully future versions will
correct this issue.

- P. Goetgheluck (1987)
*Computing Binomial Coefficients*, American Mathematical Monthly, 94(4). pp.360--365. http://www.jstor.org/stable/2323099, http://dl.acm.org/citation.cfm?id=26272