4

Is there faster algo to calculate (n! modulo m). faster than reduction at every multiplication step. And also Is there faster algo to calculate (a^p modulo m) better than right-left binary method.

here is my code: n! mod m

ans=1
for(int i=1;i<=n;i++)
    ans=(ans*i)%m;

a^p mod m

result=1;
while(p>0){
    if(p%2!=0)
        result=(result*a)%m;
    p=(p>>1);
    a=(a*a)%m;
}
Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
user1131274
  • 493
  • 6
  • 20
  • 1
    possible duplicate of [Fast way to calculate n! mod m where m is prime?](http://stackoverflow.com/questions/9727962/fast-way-to-calculate-n-mod-m-where-m-is-prime) – Tacet Nov 11 '14 at 00:14

3 Answers3

1

Now the a^n mod m is a O(logn), It's the Modular Exponentiation Algorithm.

Now for the other one, n! mod m, the algorithm you proposed is clearly O(n), So obviously the first algorithm is faster.

st0le
  • 33,375
  • 8
  • 89
  • 89
  • are'nt there any number theory results which can make this better. – user1131274 Jan 05 '12 at 08:51
  • @user1131274, I tried an alternative method for calculating `n! mod m` but it wasn't much faster. I broke `n` into its prime factors `n = p1^e1 p2^e2...pn^en` and then used `powMod` (first algorithm) to calculate `pi^ei mod m` and multiplied them together...There is probably a better method, but i don't know yet. – st0le Jan 05 '12 at 09:12
  • a^n mod m and n!mod m are fundamentally two different problems, I'm confused that you compared these two solutions. – Paul Lo Jan 16 '15 at 14:54
1

The standard trick for computing a^p modulo m is to use successive square. The idea is to expand p into binary, say

p = e0 * 2^0 + e1 * 2^1 + ... + en * 2^n

where (e0,e1,...,en) are binary (0 or 1) and en = 1. Then use laws of exponents to get the following expansion for a^p

a^p = a^( e0 * 2^0 + e1 * 2^1 + ... + en * 2^n )
    = a^(e0 * 2^0) * a^(e1 * 2^1) * ... * a^(en * 2^n)
    = (a^(2^0))^e0 * (a^(2^1))^e1 * ... * (a^(2^n))^en

Remember that each ei is either 0 or 1, so these just tell you which numbers to take. So the only computations that you need are 

a, a^2, a^4, a^8, ..., a^(2^n)

You can generate this sequence by squaring the previous term. Since you want to compute the answer mod m, you should do the modular arithmetic first. This means you want to compute the following

A0 = a mod m
Ai = (Ai)^2 mod m for i>1

The answer is then

a^p mod m = A0^e0 + A1^e1 + ... + An^en

Therefore the computation takes log(p) squares and calls to mod m.

I'm not certain whether or not there is an analog for factorials, but a good place to start looking would be at Wilson's Theorem. Also, you should put in a test for m <= n, in which case n! mod m = 0.

PengOne
  • 48,188
  • 17
  • 130
  • 149
0

For the first computation, you should only bother with the mod operator if ans > m:

ans=1
for(int i=1;i<=n;i++) {
    ans *= i;
    if (ans > m) ans %= m;
}

For the second computation, using (p & 1) != 0 will probably be a lot faster than using p%2!=0 (unless the compiler recognizes this special case and does it for you). Then the same comment applies about avoiding the % operator unless necessary.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • While we are micro optimizing, `if(ans > m) ans -= m` will be faster. – st0le Jan 05 '12 at 03:57
  • @st0le but we're multiplying, so `ans` can be larger than `2m`. – Daniel Fischer Jan 05 '12 at 04:14
  • @DanielFischer, doh! you're right and clearly `while(ans > m) ans-=m` will be slower aswell. So I respectfully retract my comment. :) – st0le Jan 05 '12 at 04:39
  • That would be `if(ans >= m) ...` Still, assuming `i! mod m` is fairly evenly distributed, the probability that the modulo operation is unnecessary is only about `1/i`. The branching may actually do more harm than good. – Jeffrey Sax Jan 05 '12 at 05:49
  • @JeffreySax - Yeah, I thought about that, but didn't analyze it. I figured that a subtract is really cheap compared to a mod. But maybe not that cheap. – Ted Hopp Jan 05 '12 at 06:13
  • hey guys is'nt there any number theory result which can be handy in above situations because i am dealing with real big numbers – user1131274 Jan 05 '12 at 08:46