Infinite Loop During Calculation of Power of Big Integers Java

Question

I have been staring at this code and cannot figure out what is wrong with it, maybe a fresh pair of eyes could help.

public static BigInteger powerOfBigInteger (BigInteger base, BigInteger power){
    if (power == BigInteger.valueOf(0)){
        return BigInteger.valueOf(1);
    }

    if (power == BigInteger.valueOf(1)){
        return base;
    }

    BigInteger x = BigInteger.valueOf(1);
    while (x != power ){
        base.multiply(base);
        x.add(BigInteger.valueOf(1));
        System.out.println(x + " " + power);
                   return base;
    } 

    return base;

I run this and apparently x never equals power. Any help is appreciated.

Why implement this method? `BigInteger` already has a `pow(int)` method, and for any power too big to fit in an `int` will run you out of memory anyway. — Louis Wasserman, Jun 14 '12 at 01:56

Eugene Ryzhikov · Accepted Answer · 2012-06-14T01:30:35.277

5

You should do

if (BigInteger.ZERO.equals(power)) return BigInteger.ONE;
if (BigInteger.ONE.equals(power))  return base;

and you have to accumulate the result of your multiplication and addition because BigInteger is immutable and returns new BigInteger instance

The infinite loop is because your x NEVER changes - should be

x = x.add(BigInteger.ONE);

multiplication should change to

result = result.mulitply(base);

where initial result value should be BigInteger.ONE

edited Jun 14 '12 at 01:30

answered Jun 14 '12 at 01:20

Eugene Ryzhikov

17,131
3
38
60

Thank you. How silly of me to not set x to the new value, I did not completely understand BigInteger. – user1446565 Jun 14 '12 at 01:44

score 1 · Answer 2 · answered Jun 14 '12 at 01:19

One thing I see is you are comparing using == instead of .equals. Compare objects with equals.

public static BigInteger powerOfBigInteger (BigInteger base, BigInteger power){
    if (power.equals(BigInteger.valueOf(0))){
        return BigInteger.valueOf(1);
    }

    if (power.equals(BigInteger.valueOf(1))){
        return base;
    }

    BigInteger x = BigInteger.valueOf(1);
    while (!x.equals(power)){
        base.multiply(base);
        x.add(BigInteger.valueOf(1));
        System.out.println(x + " " + power);
                   return base;
    } 

    return base;
}

score 1 · Answer 3 · edited May 23 '17 at 12:08

I see you're using == with BigInteger. Don't do this. Use .equals(other) instead. BigInteger is not a primitive that can be compared with normal operators (you're just comparing the object references, which are most likely not going to be equal). Also, you're not setting anything when you perform the calculations on your BigInteger instances; they don't operate on the local object and store the result in the local object. You need to store the returned object.

Problematic lines:

base.multiply(base);
x.add(BigInteger.valueOf(1));

There's also some discussion in this other post on SO re. BigInteger to the power of BigInteger: BigInteger.pow(BigInteger)?

score 0 · Answer 4 · answered Dec 23 '16 at 02:11

Maybe I'm missing something but isn't it as simple as the fact that he's doing base.multiply(base). When figuring a power, the base should stay as given. Example 2^3 should generate a sequence of 2,4,8 but this code would generate 2,4,16 because after the first loop base is four, and four.multiple(four) is 16, not 8. I must be missing something.

Infinite Loop During Calculation of Power of Big Integers Java

4 Answers4

Linked