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.