Next: Fibonacci Numbers Algorithm, Previous: Factorial Algorithm, Up: Other Algorithms [Index]

Binomial coefficients *C(n,k)* are calculated
by first arranging *k <= n/2* using *C(n,k) = C(n,n-k)* if necessary, and then
evaluating the following product simply from *i=2* to *i=k*.

k (n-k+i) C(n,k) = (n-k+1) * prod ------- i=2 i

It’s easy to show that each denominator *i* will divide the product so
far, so the exact division algorithm is used (see Exact Division).

The numerators *n-k+i* and denominators *i* are first accumulated
into as many fit a limb, to save multi-precision operations, though for
`mpz_bin_ui`

this applies only to the divisors, since *n* is an
`mpz_t`

and *n-k+i* in general won’t fit in a limb at all.