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

Question

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?

Answer 1

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, and since b is too large to fit in an integer 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.

Answer 2

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 :-).