search

davidedc / Algebrite

Computer Algebra System in Javascript (Typescript)
http://algebrite.org
MIT License
966 stars 59 forks source link

Computation of binomial #172

Open soegaard opened 1 year ago

soegaard commented 1 year ago

Currently the text book formula

binomial(n, k) = n! / k! / (n - k)!

is used to compute binomial coefficients.

I suggest using the algorithm below. The text is from [1].

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 Exact Division).

[1] https://web.archive.org/web/20111229055708/https://www.gnu.org/software/gmp/manual/html_node/Binomial-Coefficients-Algorithm.html