GNU Info

(gmp.info)Binomial Coefficients Algorithm

---

Next: Fibonacci Numbers Algorithm Prev: Factorial Algorithm Up: Other Algorithms

---

Enter node , (file) or (file)node

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 (Note: 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.