Efficiently calculating nCk mod p

Question

I have came across this problem many time but I am unable to solve it. There would occur some cases or the other which will wrong answer or otherwise the program I write will be too slow. Formally I am talking about calculating

nCk mod p where p is a prime n is a large number, and 1<=k<=n.

What have I tried:

I know the recursive formulation of factorial and then modelling it as a dynamic programming problem, but I feel that it is slow. The recursive formulation is (nCk) + (nCk-1) = (n+1Ck). I took care of the modulus while storing values in array to avoid overflows but I am not sure that just doing a mod p on the result will avoid all overflows as it may happen that one needs to remove.

Maybe related to this [question] http://stackoverflow.com/questions/9370251/mod-compatible-ways-of-generating-binomial-coefficients — Tengis, Dec 08 '12 at 17:53
[This](https://github.com/madaan/entire-src/blob/master/c/Marbles.c) may help in calculating nCk for a larger range. Look out for the function `c(n,k)`. — axiom, Dec 08 '12 at 17:58
How large is `n`? Does it fit into 64 bits? Is `p` large too (e.g. is it less than `n`; does it fit into 64 bits)? — anatolyg, Dec 08 '12 at 21:55
You might be interested int [this answer](http://stackoverflow.com/a/10862881/1011995). — Daniel Fischer, Dec 09 '12 at 00:25

score 1 · Answer 1 · answered Oct 25 '17 at 23:10

To compute nCr, there's a simple algorithm based on the rule nCr = (n - 1)C(r - 1) * n / r:

def nCr(n,r):
  if r == 0:
    return 1
  return n * nCr(n - 1, r - 1) // r

Now in modulo arithmetic we don't quite have division, but we have modulo inverses which (when modding by a prime) are just as good

def nCrModP(n, r, p):
  if r == 0:
    return 1
  return n * nCrModP(n - 1, r - 1) * modinv(r, p) % p

Here's one implementation of modinv on rosettacode

score 0 · Answer 2 · answered Dec 08 '12 at 18:21

Not sure what you mean by "storing values in array", but I assume they array serves as a lookup table while running to avoid redundant calculations to speed things up. This should take care of the speed problem. Regarding the overflows - you can perform the modulo operation at any stage of computation and repeat it as much as you want - the result will be correct.

score 0 · Answer 3 · answered Dec 08 '12 at 19:35

First, let's work with the case where p is relatively small. Take the base-p expansions of n and k: write n = n_0 + n_1 p + n_2 p^2 + ... + n_m p^m and k = k_0 + k_1 p + ... + k_m p^m where each n_i and each k_i is at least 0 but less than p. A theorem (which I think is due to Edouard Lucas) states that C(n,k) = C(n_0, k_0) * C(n_1, k_1) * ... * C(n_m, k_m). This reduces to taking a mod-p product of numbers in the "n is relatively small" case below.

Second, if n is relatively small, you can just compute binomial coefficients using dynamic programming on the formula C(n,k) = C(n-1,k-1) + C(n-1,k), reducing mod p at each step. Or do something more clever.

Third, if k is relatively small (and less than p), you should be able to compute n!/(k!(n-k)!) mod p by computing n!/(n-k)! as n * (n-1) * ... * (n-k+1), reducing modulo p after each product, then multiplying by the modular inverses of each number between 1 and k.

Efficiently calculating nCk mod p

3 Answers3