Computing n choose k mod p

Let's talk about algorithms!

Moderator: Board moderators

Computing n choose k mod p

Postby joshi13 » Tue Apr 14, 2009 4:49 am

Hi all.

How can we apply the modular multiplicative inverse when calculating

(n choose k) mod p, where 'p' is a prime number.

If you could suggest some related problems, it would be very helpful.

Thanks in advance.
joshi13
New poster
 
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am

Re: Computing n choose k mod p

Postby mf » Tue Apr 14, 2009 10:56 am

You could use Lucas's theorem.
mf
Guru
 
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Re: Computing n choose k mod p

Postby maxdiver » Tue Apr 14, 2009 12:03 pm

There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.

C_n^k = n! / (k! (n-k)!)
Let's learn how to compute n! mod p, but factorial without factors p and so on:
n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2) * ... * (2p-1) * _2_ * (2p+1) * (2p+2) * ... * n.
We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on).
I name this 'strange factorial'.

If n is not very large, we can calculate this simply, then GOTO END_SCARY_MATHS :)
If p is not large, then GOTO BEGIN_SCARY_MATHS:
Else - skip the rest of the post :)

BEGIN_SCARY_MATHS:
After taking each factor mod p, we get:
n!* mod p = 1 * 2 * ... * (p-1) * 1 * 2 * ... * (p-1) * 2 * 1 * 2 * ... * n.
So 'strange factorial' is really several blocks of construction:
1 * 2 * 3 * ... * (p-1) * i
where i is a 1-indexed index of block taken again without factors p ('strange index' :) ).
The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
The result in each block is multiplication 1 * 2 * ... * (p-1), which is common to all blocks, and multiplication of all 'strange indices' i from 1 to floor(n/p).
But multiplication of all 'strange indices' is really a 'strange factorial' again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.

So... After so much brainfucking maths I must give a code :)
Code: Select all
int factmod (int n, int p) {
   long long res = 1;
   while (n > 1) {
      long long cur = 1;
      for (int i=2; i<p; ++i)
         cur = (cur * i) % p;
      res = (res * powmod (cur, n/p, p)) % p;
      for (int i=2; i<=n%p; ++i)
         res = (res * i) % p;
      n /= p;
   }
   return int (res % p);
}

Asymptotic... There are log_p n iterations of while, inside it there O(p) multiplications, and calculation of power, that can be done in O(log n). So asymptotic is O ((log_p n) (p + log n)).
Unfortunately I didn't check the code on any online judge, but the idea (which was explained by Andrew Stankevich) is surely right.
END_SCARY_MATHS:

So, we can now compute this 'strange factorial' modulo p. Because p is prime, and we've excluded all multiples of p, then the result would be different from zero. This means we can compute inverse for them, and compute C_n^k = n!* / (k!* (n-k)!*) (mod p).
But, of course, before all this, we should check, if p was in the same power in the nominator and denominator of the fraction. If it was indeed in the same power, then we can divide by it, and we get exactly these 'strange factorials'. If the power of p in nominator was greater, then the result will obviously be 0. The last case, when power in denominator is greater than in nominator, is obviously incorrect (the fraction won't be integer).

P.S. How to compute power of prime p in n! ? Easy formula: n/p + n/(p^2) + n/(p^3) + ...
maxdiver
Learning poster
 
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov

Re: Computing n choose k mod p

Postby joshi13 » Mon Apr 20, 2009 5:59 am

Thanks guys, that theorem and the general approach have proven to be very useful.
joshi13
New poster
 
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am


Return to Algorithms

Who is online

Users browsing this forum: No registered users and 1 guest