NumberTheory` Binomial`
=======================
This package implements fast evaluation of binomial coefficients.
The evaluation of the standard binomial coefficients is accomplished
using their prime factorization (see I. Vardi, Computational
Recreations in Mathematica, Addison Wesley, 1991). This reduces
the number of multiplications by a factor of log. In the case of
Binomial[2n, n], there exists a still better algorithm due to the
coefficient's explicit factorization. These algorithms require
the function PrimePi[x]. The package also implements a method to
compute factorials that is faster than the built-in version for
large arguments.
The fast evaluation of Mod[Binomial[n, k], p] is accomplished using
a well-known theorem of E. Lucas. All products in the computation
are taken mod p.
-----------------------
| |
| FastBinomial[n,k] efficiently compute Binomial[n,k] for values of |
| n and k with hundreds of digits |
| |
| FastFactorial[n] efficiently compute n! for values of n with |
| hundreds of digits |
| |
| BinomialMod[n,k,p] efficiently compute Mod[Binomial[n,k],p], where |
| p is a prime number |
| |
--------------------------------------------------------------------------------
^^Fast binomial and factorial operations^^
This loads the package.
In[1]:= <