Corner cases while calculating pow(x,n)%d

Question

I've come up with a working code for the above problem, for both positive and negative values of x. And the answers for the majority of situations is correct, however the code fails at a corner case and I can't seem to find what the issue is! What condition am I missing:`

int pow(int x, int n, int d) {
int i=0,rem=1;
long long l;
    if(x==0)
    {
        return 0;
    }
    if(x==1)
    {
        return 1;
    }
    if(n==0)
    {
        return 1;
    }
    x=x%d;
    if(n%2==0||n==0)
    {
        l = ((pow(x,n/2,d))*(pow((x),n/2,d)))%d;
    }
    else
    {
        l = ((x)*(pow(x,(n-1)/2,d))*(pow((x),(n-1)/2,d)))%d;
    }
    if(x<0 && n%2!=0)
    {
        return d+l;
    } 
    else
    {
        return l;
    }
}

` The case at which the code gives wrong ans:

A: 71045970
B : 41535484
C : 64735492  
My Output: 12942068
Actual Output:20805472

This code should not compile unless you declare `l` somewhere. Next, what is the idea behind `&n==0`? Finally, what's your corner case? — sweber, Jun 05 '17 at 07:11
looks like int overflow problem to me ... I am doing `modpow` like this: [Modular arithmetics and NTT (finite field DFT) optimizations](https://stackoverflow.com/q/18577076/2521214). Also I would feel safer with more `()` brackets in your `if` statements — Spektre, Jun 05 '17 at 07:28
I personally avoid using l as a variable name for obvious reasons — AndersK, Jun 05 '17 at 07:45
I think that the most susceptible for an overflow is this line: `l = ((x)*(pow(x,(n-1)/2,d))*(pow((x),(n-1)/2,d)))%d;`, which performs 3 multiplications before doing the modulo. You can try inserting an additional modulo d operation after the first multiplication. — danbanica, Jun 05 '17 at 08:30

Sumsuddin Shojib · Accepted Answer · 2017-06-05T08:28:46.293

Here is the simplified version of yours.

int pow(int x, int n, int d) {
    long long l;
    if(n==0)
    {
        return 1;
    }
    if(n%2==0)
    {
        l = (long long)pow(x,n/2,d);
        return (int)((l * l) % (long long)d);
    }
    else
    {
        //check negative value of x, and make it positive, so that negative values never come in result
        if (x < 0) {
            x += d;
        }
        return (int)(((long long)x * (long long)pow(x,n-1,d)) % (long long)d);
    }
}

I think your code is logically correct but there exists a data overflow problem on int data type if the modulo d value is large enough.

eg. (pow(x,n/2,d))*(pow((x),n/2,d)) here two big int value multiplication can result in datatype overflow.

Corner cases while calculating pow(x,n)%d

1 Answers1