CODEWITHSUNDEEP
javabiginteger
angstrom91
angstrom91

Reputation: 178

How do you raise a Java BigInteger to the power of a BigInteger without doing modular arithmetic?

I'm doing some large integer computing, and I need to raise a BigInteger to the power of another BigInteger. The .pow() method does what I want, but takes an int value as an argument. The .modPow method takes a BigInteger as an argument, but I do not want an answer congruent to the value I'm trying to compute.

My BigInteger exponent is too large to be represented as an int, can someone suggest a way to work around this limitation?

Upvotes: 8

Views: 8284

Answers (4)

Marcelo Salamanca Cox
Marcelo Salamanca Cox

Reputation: 69

Assuming we've already accepted the fact that we shouldn't do this for the reasons outlined in all of the previous answers, here's a working solution that can be used for testing purposes only:

Exponent greater than or equal to 0

BigInteger pow(BigInteger base, BigInteger exponent) {
    BigInteger result = BigInteger.ONE;
    for (BigInteger i = BigInteger.ZERO; i.compareTo(exponent) != 0; i = i.add(BigInteger.ONE)) {
        result = result.multiply(base);
    }
    return result;
}

This will work for both positive and negative bases. You might want to handle 0 to the power of 0 according to your needs, since that's technically undefined.

Exponent can be both positive or negative

BigDecimal allIntegersPow(BigInteger base, BigInteger exponent) {
    if (BigInteger.ZERO.compareTo(exponent) > 0) {
        return BigDecimal.ONE.divide(new BigDecimal(pow(base, exponent.negate())), 2, RoundingMode.HALF_UP);
    }
    return new BigDecimal(pow(base, exponent));
}

This uses the first method to return a BigDecimal with 2 decimal places, you can define the scale and rounding mode as per your needs.

Again, you should not do this in a real-life, production-level system.

Upvotes: 0

User_67128
User_67128

Reputation: 1250

You can't find the the value of "Java BigInteger to-the-power BigInteger" because according to JavaDoc "BigInteger must support values in the range -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range."

So, Java BigInteger does not support anything above 2^Integer.MAX_VALUE. Tha's why pow method does not take any argument above int.

Hope this answer helps.

Upvotes: 0

Mark Byers
Mark Byers

Reputation: 838116

You shouldn't try to calculate the power of an extremely large number with another extremely large number. The resulting number would use huge amounts of memory. If you calculate a.pow(b) it will have approximately log(a)*b digits. If b is too large to fit in an integer then for even quite small values of a the result will have several billion digits.

Try to rethink what you are trying to achieve and how to achieve it without doing this operation.

Upvotes: 14

Stephen C
Stephen C

Reputation: 718758

The practical solution is to convert the exponent from a BigInteger to an int.

If you cannot do this because the exponent is too large, your algorithm is unimplementable. The resulting number would almost certainly be too large to represent as a BigInteger. (A BigInteger uses an array of bytes to represent the number, and the maximum size of a Java array is 2**31 - 1 elements no matter how large the heap is.) And even if you implemented a "BiggerInteger" class that would represent the number, you would soon be pushing the limits of the physical memory size of your machine. (And the time taken to do calculate N.pow(M) would be ... NP-tricky ... O((MlogN)^M) I think).

Of course, if the number you are taking the power of is 0, 1 or -1, then the result will easily fit in a BigInteger. But in those cases, there are better ways to calculate the power :-).

Upvotes: 6

Related Questions