P! modulo m, a ^ p modulo m

Question

Is there an acceleration algorithm for computing (n! Modulo m). faster than contraction at each step of the multiplication. And also Is the calculation algorithm faster (a ^ p modulo m) better than the right-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; } 

Answer 1

Now a^n mod m is O(logn) , it is Modular O(logn) Algorithm.

Now for another, n! mod m n! mod m , the algorithm you proposed is explicitly O(n) , so obviously the first algorithm runs faster.

Answer 2

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

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

where (e0,e1,...,en) are binary ( 0 or 1 ) and en = 1 . Then we use the laws of exponentials to obtain 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 they just tell you which numbers to take. So the only calculations you need are

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

You can generate this sequence by squaring the previous word. Since you want to calculate the mod m answer, you need to do modular arithmetic first. This means that you want to calculate the following

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

Answer then

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

Therefore, the calculation takes the squares of log(p) and calls mod m .

I'm not sure if there is an analogue of factorials, but Wilson's theorem will be a good place to search. In addition, you must put the test m <= n , in this case n! mod m = 0 n! mod m = 0 .

Answer 3

For the first calculation, you only need to worry 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 calculation, using (p & 1) != 0 is likely to be much faster than using p%2!=0 (unless the compiler recognizes this special case and does it for you). Then the same comment about the % operator exception is applied, if necessary.