Biginteger.Pow(Biginteger)

BigIntegers for exponent (in function pow)

If the BigInteger exponent is small enough, you can convert it to Int first using BigInteger.intValue().

However, if you do need to use actual BigInteger-range exponents, you may have to think about what your computer can actually hold in memory.
Please have a look at this existing question which I guess is a duplicate of yours (it's in Java but it's about the same API).

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

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.

Java BigInteger pow with BigInteger exponent

I suspect the reason they didn't bother including anything like this is that in most cases, the number would be too big to represent.

Consider 2^(256 bit number). The result has (256bit number) bits, meaning that it takes more memory then there are particles in the universe.

So you'll have to find a different way to represent your logic. Perhaps you could do it symbolically.

It would be possible to do 2^(2^32) and exponents close to that, but this was probably seen as a niche case that they just didn't bother adding a function for.

java.math.BigInteger pow(exponent) question

The algorithm uses repeated squaring (squareToLen) and multiplication (multiplyToLen). The time for these operations to run depends on the size of the numbers involved. The multiplications of the large numbers near the end of the calculation are much more expensive than those at the start.

The multiplication is only done when this condition is true: ((exponent & 1)==1). The number of square operations depends on the number of bits in the number (excluding leading zeros), but a multiplication is only required for the bits that are set to 1. It is easier to see the operations that are required by looking at the binary representation of the number:


2000000: 0000111101000010010000000
2500000: 0001001100010010110100000
3000000: 0001011011100011011000000
3500000: 0001101010110011111100000
4000000: 0001111010000100100000000
4500000: 0010001001010101000100000
5000000: 0010011000100101101000000

Note that 2.5M and 4.5M are lucky in that they have fewer high bits set than the numbers surrounding them. The next time this happens is at 8.5M:


8000000: 0011110100001001000000000
8500000: 0100000011011001100100000
9000000: 0100010010101010001000000

The sweet spots are exact powers of 2.


1048575: 0001111111111111111111111 // 16408 ms
1048576: 0010000000000000000000000 //  6209 ms

What are complexities of BigInteger.pow and BigInteger.isProbablePrime?

Assuming the standard algorithms, the complexities are:

pow()             : O( M(n * exponent) )
IsProbablePrime() : O( M(n) * n )

where:

n is the number of digits in the operand.
exponent is the exponent of the power function.
M(n) is the run-time for an n x n digit multiplication. Which I believe is O(n^2) as of Java 6.

Explanation for pow():

For an input operand of n-digits long raised to a power of exp, the output is roughly n * exp digits long. This is done by binary-powering algorithm where the operand is squared at each iteration. So the complexity becomes:

O( M(n) + M(2*n) + M(4*n) + ... M(n * exp/2) ) = O( M(n * exp) )

This is a geometric sum, so the sum becomes O( M(n * exp) ).

Explanation for IsProbablePrime():

For a fixed number of Rabin-Miller iterations, each iteration has O(n) multiplications of size n x n digits. Therefore, the complexity becomes O( n * M(n) ).

Negative exponent at java.base/java.math.BigInteger.pow

pattern.intValue()

pattern is some enormous number. .intValue() converts that to an int (hence the name), which is why this goes wrong, as this doesn't fit (and happens to turn into a negative number due to how intValue() works when you call that on a bigInteger whose value exceeds what int can represent. The reason only ints go there is because if you put a huge number there, your RAM can't hold it and your CPU would take a few million years to calculate it. There'd be no point.

How do I fix it?

By going back to whomever gave you this assignment. your code has a bug, but reading what it is intending to do, it is ((n+1)/4)^b.

Which is a number that has... a lot a lot of digits. Many, many more than what you expect for output.

Clearly that isn't what you really wanted, or if it is, no computer can calculate this, and the result would be nothing like what you wanted.

Possibly that output really is ((n+1)/4)^b, but mod something. Which the API does support: b.modPow(pattern, FigureOutWhatTheModuloIsAndPutThatHere).