Wednesday, June 13, 2012

Binomial Coefficients - Part 2

In many problems, it is required to find the answer modulo a large prime, such as 1000000007 (hereby referred to as MAX or m). If the problem involves binomial coefficients, then they have to be calculated modulo MAX too.

It is easy to calculate factorials modulo MAX, because
(a*b) mod m = (a mod m) * (b mod m)
but the same does not hold for division, which makes it tricky to calculate binomial coefficients.

However, the following relation holds :
(a/b) mod m = (a mod m) * (c mod m)
where 'c' is the modular multiplicative inverse[1] of 'b'.

Thus, the relation
C(n, k) = fact(n)/(fact(n-k)*fact(k))
is reduced to
C(n,k) = fact(n)*invfact(n-k)*invfact(k)
where C(a,b) and fact(a) are expressed modulo m, and invfact(a) denotes the multiplicative inverse of fact(a) modulo m. Multiplication is also performed modulo m.

Implementation :

The above implementation employs efficient routines for modular arithmetric.

[1] - http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

2 comments:

  1. It's important to note that this relation:
    (a*b) mod m = (a mod m) * (b mod m)
    isn't always true.

    For example:
    (7*8) mod 13 = (7 mod 13) * (8 mod 13)
    4 = 56 !!!

    ReplyDelete
  2. True. The correct relation is,
    (a*b) mod m = ((a mod m) * (b mod m)) mod m

    @DiĆ³genes : Thanks for the observation!

    ReplyDelete