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?
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)