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]:= <