(gmp.info.gz) Binomial Coefficients Algorithm
Info Catalog
(gmp.info.gz) Factorial Algorithm
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Fibonacci Numbers Algorithm
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 ( 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.
Info Catalog
(gmp.info.gz) Factorial Algorithm
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Fibonacci Numbers Algorithm
automatically generated byinfo2html