Please explain this code for modular exponential

Question

here x can be negative i am not able to understand that why we have written d+x in if(x<0) condition and why we have taken modulo ans%d at last since we have already taken modulo with d while finding ans inside if-else condition

public class Solution {
        public int pow(int x, int n, int d) {
    
        long ans;
        if(x==0) return 0;
        if(n==0) return 1;
        if(x<0)  return pow(d+x,n,d);
        
        long temp = pow(x,n/2,d);
        if(n%2==0)
            ans = ((temp%d)*(temp%d))%d;
        else
            ans = ((((x%d)*(temp%d))%d)*(temp%d))%d;
        
        return (int)ans%d;
    
        }
    }

In my opinion, the last line should have been ```return (int)(ans+d)%d``` — Abhinav Mathur, Apr 19 '21 at 13:21
Some languages return negative numbers from the modulus/remainder operation. Java is one such language. See https://stackoverflow.com/questions/5385024/mod-in-java-produces-negative-numbers — Welbog, Apr 19 '21 at 13:27

score 1 · Answer 1 · answered Apr 19 '21 at 13:35

From definition of modular exponentiation,

c = xⁿ % d where 0 <= c < d

When x < 0, the answer returned can be negative.
So by changing x to x+d,

if(x<0)  return pow(d+x,n,d);

we are trying to avoid negative answer as solution.

At the last you don't need to perform modulo again,

(int)ans;

However, you can altogether ignore the x < 0 case by changing last line to ,

return (int)(ans+d)%d

Code,

public class Solution {
    public int pow(int x, int n, int d) {
    
        long ans;
        if(x==0) return 0;
        if(n==0) return 1;
        
        long temp = pow(x,n/2,d);
        if(n%2==0)
            ans = ((temp%d)*(temp%d))%d;
        else
            ans = ((((x%d)*(temp%d))%d)*(temp%d))%d;
        
        return (int)(ans+d)%d;
    
        }
    }

Please explain this code for modular exponential

1 Answers1