problem with Modular exponentiation

general
1

Consider a code for Modular exponentiation
assume we are calculating (x^n)% MOD

while(n>0)
{
    if(n&1)
    result = (result*x)%MOD;
    cout<<result<<"\n";
    x=(x*x)%MOD;

    n=n>>1;
}

suppose x = 4 and n is large say 100 and MOD is 10^9 +6

so my program has overflow and giving result in -ve number
so in this program x can be very large < MOD
and when we multiply it be result intermediate value is very large so how to do it

p.s i am newbie :slight_smile:

2

Let say, you need to calculate (x * y) % MOD as some intermediate step.

Use ((x % MOD) * (y%MOD)) % MOD.

By doing this, both the terms will be less than MOD.

Now the intermediate result can be as large as (MOD^2). So make sure you either store the intermediate result in the suitable datatype or typecast it accordingly.

An example of typecasting in such cases. For eg.

res = (int)((long long)x * x) % MOD;

This will make sure that your result never overflows. This works for those cases where MOD fits in a 32 bit integer. If the MOD is larger, then you can use your own multiplication by using repeated addition in a O(log(multiplier)) method.
If the MOD is still larger(does not fit 64 bits), you will have to implement your own BigInteger.

6 Likes
3

Hi Mukul. Thanks for the article but there is one correction you need to do.
res = (int)((long long)x * x)%MOD must be changed to res = (int)(((long long)base*base)%MOD);

for x = 1000000000 and n=2. The first version gives the wrong answer because of overflow while typecasting from long long to int. But instead, typecasting must be done after taking the modulo.