DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH
 

(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