BigInteger.pow(BigInteger)?

问题:

I'm playing with numbers in Java, and want to see how big a number I can make. It is my understanding that BigInteger can hold a number of infinite size, so long as my computer has enough Memory to hold such a number, correct?

My problem is that BigInteger.pow accepts only an int, not another BigInteger, which means I can only use a number up to 2,147,483,647 as the exponent. Is it possible to use the BigInteger class as such?

BigInteger.pow(BigInteger)

Thanks.

回答1:

You can write your own, using repeated squaring:

BigInteger pow(BigInteger base, BigInteger exponent) {
  BigInteger result = BigInteger.ONE;
  while (exponent.signum() > 0) {
    if (exponent.testBit(0)) result = result.multiply(base);
    base = base.multiply(base);
    exponent = exponent.shiftRight(1);
  }
  return result;
}

might not work for negative bases or exponents.

回答2:

You can only do this in Java by modular arithmetic, meaning you can do a a^b mod c, where a,b,c are BigInteger numbers.

This is done using:

 BigInteger modPow(BigInteger exponent, BigInteger m) 

Read the BigInteger.modPow documentation here.

回答3:

The underlying implementation of BigInteger is limited to (2^31-1) * 32-bit values. which is almost 2^36 bits. You will need 8 GB of memory to store it and many times this to perform any operation on it like toString().

BTW: You will never be able to read such a number. If you tried to print it out it would take a life time to read it.

回答4:

2^2,147,483,647 has at least 500000000 digit, in fact computing pow is NPC problem, [Pow is NPC in the length of input, 2 input (m,n) which they can be coded in O(logm + logn) and can take upto nlog(m) (at last the answer takes n log(m) space) which is not polynomial relation between input and computation size], there are some simple problems which are not easy in fact for example sqrt(2) is some kind of them, you can't specify true precision (all precisions), i.e BigDecimal says can compute all precisions but it can't (in fact) because no one solved this up to now.

回答5:

java wont let you do BigInteger.Pow(BigInteger) but you can just put it to the max integer in a loop and see where a ArithmeticException is thrown or some other error due to running out of memory.

回答6:

I can suggest you make use of BigInteger modPow(BigInteger exponent, BigInteger m)

Suppose you have BigInteger X, and BigInteger Y and you want to calculate BigInteger Z = X^Y.

Get a large Prime P >>>> X^Y and do Z = X.modPow(Y,P);

回答7:

For anyone who stumbles upon this from the Groovy side of things, it is totally possible to pass a BigInteger to BigInteger.pow().

groovy> def a = 3G.pow(10G) 
groovy> println a 
groovy> println a.class 

59049
class java.math.BigInteger

http://docs.groovy-lang.org/2.4.3/html/groovy-jdk/java/math/BigInteger.html#power%28java.math.BigInteger%29

回答8:

Just use .intValue() If your BigInteger is named BigValue2, then it would be BigValue2.intValue()

So to answer your question, it's

BigValue1.pow(BigValue2.intValue())