Implement pow(x,n)%d with integers only. (without making use of library functions)

Question

Basically I used the classic divide and conquer whenever the exponent is even and came up with this.

int mymod(int a,int b){ //returns only positive value between 0 to b-1
    return a%b<0 ? (a%b)+b : a%b;
}
int Solution::pow(int x, int n, int d) {
    if(n==0) return mymod(1,d);
    int result = 1;
    while(n>0){
        if(n%2 == 1)
            result = mymod((result * x),d);
        n = n>>1; //dividing exponent by 2, if it's even. Divide and conquer whenever exponent is even
        x = mymod(x*x,d);
    }
    return result;
}

Now I'm using mymod function to calculate modulus, 'cuz normal modulus gave me a -ve result which wasn't in accordance with the test cases. I need to implement it with integers. There's one major thing to note here. Overflow situation. some test cases have large enough x, which when multiplied might overflow. Here are some of the test cases this program should satisfy.

X : 0
N : 0
D : 1
expected output: 0

X : -1
N : 1
D : 20
expected output: 19

X : 71045970
N : 41535484
D : 64735492
expected output: 20805472

The above code satisfies the first two test cases (TRIVIAL) but fails at the last test case. Python is also accepted by the OJ, I'll be needing a bit of an explanation in case of python. THANK YOU!!

So what is your question? Modular exponentiation is a very common operation in cryptography. It is not that hard to find algorithms, that will do it fast for pretty big `x`, `n` and `d` — Konstantin, May 18 '15 at 14:29
Python has a powerful built-in `pow()` function that takes a 3rd arg to specify the modulus. And because it's a built-in it's always available, no modules need to be imported. — PM 2Ring, May 18 '15 at 14:31

score 0 · Answer 1 · answered May 18 '15 at 14:30

In the line

result = mymod((result * x),d);

in result * x your both result and x can be as large as d (more precisely, d-1), so you need a data type that can hold integers as big as d*d. For your cases, this may be long long int.

Another approach will be not to use library operator* for ints, but implement a manual multiplication function with a similar divide and conquer approach using only additions. This way you will need a data type that can hold integers as big as 2d only.

Also note that you do not need to call mymod each time in the main loop. You can call it only once before the loop to make x positive (x=mymod(x,d)), and then use just the operator%.

Implement pow(x,n)%d with integers only. (without making use of library functions)

1 Answers1