javabiginteger

Convert to BigInteger


I want to rewrite this function code to BigInteger class in Java:

 static int power(int x, int y, int p)
    {
        int res = 1; // Initialize result
 
        while (y > 0) {
 
            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = res * x;
 
            // y must be even now
            y = y >> 1; // y = y/2
            x = x * x; // Change x to x^2
        }
        return res % p;
    }

I tried and wrote the following code:

static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
        BigInteger res = BigInteger.ONE; // Initialize result

        while (y.compareTo(BigInteger.ZERO) == 1) {   

            // If y is odd, multiply x with result
            if ((y.and(BigInteger.ONE)) != BigInteger.ZERO)  
                res = res.multiply(x);  

            // y must be even now
            y = y.shiftRight(1); // y = y/2   
            x = x.multiply(x); // Change x to x^2
        }
        return res.mod(p);
    }

But when I tested input "power(2, 5, 13)", the output was 11, however, the correct answer is 6.

I checked the code I wrote several times, but couldn't find the problem. Can you please help me to output the correct answer code?


Solution

  • You should compare reference types with .equals, not == as for primitives.

    if (!BigInteger.ZERO.equals(y.and(BigInteger.ONE)))
    

    In addition, you should only consider the sign of the result of compareTo; do not directly compare to a fixed value like 1.

    while (y.compareTo(BigInteger.ZERO) > 0)