pow for LargeInteger

Question

LargeInteger doesn't seem to have a pow function, or if it does, it cannot process pow(0) though BigInteger can.

I have tried to construct my own, but memory seems to spike badly, and there may be an infinite loop as it runs endlessly:

public static LargeInteger liPow(LargeInteger base, int exponent){
    if(exponent == 0){
        return LargeInteger.valueOf(1);
    }
    else if(exponent == 1){
        return base;
    }
    else{
        for(int i=1; i<exponent; i++){
            base = base.times(base);
        }
        return base;
    }
}

How can a pow method be developed for LargeInteger?

Answer 1

Each time through your for loop, you are effectively squaring the result with this line:

base = base.times(base);

You would wind up with base to the power of (2 to the exponent power), not base to the power of exponent.

Start with 1 and multiply in the base each loop.

LargeInteger result = LargeInteger.valueOf(1);
for(int i = 0; i < exponent; i++){
    result = result.times(base);
}
return result;

For optimization, you can try modifying the algorithm to use exponentiation-by-squaring.