Node:Binomial Coefficients Algorithm, Next:Fibonacci Numbers Algorithm, Previous:Factorial Algorithm, Up:Other Algorithms
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.
An obvious improvement would be to strip factors of 2 from each multiplier and divisor and count them separately, to be applied with a bit shift at the end. Factors of 3 and perhaps 5 could even be handled similarly. Another possibility, if n is not too big, would be to determine the prime factorization of the result based on the factorials involved, and power up those primes appropriately. This would help most when k is near n/2.