Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BinomialMod

Source Notebook

Efficient computation of a binomial coefficient modulo a given number

Contributed by: Aster Ctor

ResourceFunction["BinomialMod"][n,m,p]

is equivalent to Mod[Binomial[n,m],p].

Details and Options

ResourceFunction["BinomialMod"] uses some mathematical theory to speed up operations.
If the modulus is prime, then it uses Lucas’s theorem.
If it is square-free, then Lucas’s theorem is used on the prime factors, and the Chinese Remainder algorithm is used to form the final result.

Examples

Basic Examples (1) 

The following formula illustrates the fundamental equivalence with Mod[Binomial[…]]:

In[1]:=
ResourceFunction["BinomialMod"][7, 5, 11] == Mod[Binomial[7, 5], 11]
Out[1]=

Scope (6) 

Prime Case (3) 

1299709 is a prime number:

In[2]:=
PrimeQ[p = Prime[100000]]
Out[2]=

Ordinary algorithms take a long time:

In[3]:=
Mod[Binomial[100000000, 7654321], p] // AbsoluteTiming
Out[3]=

The optimized algorithm is much faster:

In[4]:=
ResourceFunction["BinomialMod"][100000000, 7654321, p] // AbsoluteTiming
Out[4]=

Square-Free Case (3) 

1005973 is a square-free number:

In[5]:=
SquareFreeQ[p = Times @@ NextPrime[1000, {-1, +1}]]
Out[5]=

Ordinary algorithms take a long time:

In[6]:=
Mod[Binomial[100000000, 87654321], p] // AbsoluteTiming
Out[6]=

The optimized algorithm is much faster:

In[7]:=
ResourceFunction["BinomialMod"][100000000, 87654321, p] // AbsoluteTiming
Out[7]=

Possible Issues (2) 

Handling of non-square moduli can be slow:

In[8]:=
ResourceFunction["BinomialMod"][100000000, 7654321, Prime[1234]^2] // Timing
Out[8]=

In such cases the code simply uses Mod[Binomial[…]]:

In[9]:=
Mod[Binomial[100000000, 7654321], Prime[1234]^2] // Timing
Out[9]=

Publisher

Aster Ctor (MoeNet)

Version History

  • 1.0.0 – 06 November 2019

Related Resources

Author Notes

Acceleration of non-square free numbers is possible, but I still don't fully understand the mathematical theory needed. For more information, see https://math.stackexchange.com/questions/222637/binomial-coefficient-modulo-prime-power.

License Information