Avoid overflow with fast modular exposure

Question

I am trying to solve the issue of SPOJ, which requires modular exponentiation. I am using the following C code

long long modpow(long long a,long long b,long long mod) { long long product,pseq; product=1 pseq=a%mod; while(b>0) { if(b&1) product=(product*pseq)%mod; pseq=(pseq*pseq)%mod; b>>=1 } return product; } 

The problem is when I want to calculate (2^249999999997)%999999999989 , it gives the answer 0 due to overflow. How to avoid overflow?

Answer 1

Untestet, but you get the idea. This should work as long as 2*mod less than the maximum displayed value long long and a , b and mod are positive.

 long long modpow(long long a,long long b,long long mod) { long long product,pseq; product=1; pseq=a%mod; while(b>0) { if(b&1) product=modmult(product,pseq,mod); pseq=modmult(pseq,pseq,mod); b>>=1; } return product; } long long modmult(long long a,long long b,long long mod) { if (a == 0 || b < mod / a) return (a*b)%mod; long long sum; sum = 0; while(b>0) { if(b&1) sum = (sum + a) % mod; a = (2*a) % mod; b>>=1; } return sum; } 

Answer 2

Another suggestion is to use the fact that 999999999989 is simple. Using the relation, (a ^ n) = a% n (where n is a prime), u can simplify the operation.

Answer 3

You can use unsigned long long instead of long long , this will help you play with higher values, the range of which is from 0 to 18 446 744 073 709 551 615.