15.7.3 Binomial Coefficients

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 section 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.

This document was generated on March 31, 2014 using texi2html 5.0.