CODEWITHSUNDEEP
javamathbigintegerpow
PeterW
PeterW

Reputation: 319

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.

Upvotes: 31

Views: 47118

Answers (9)

Marcelo Salamanca Cox
Marcelo Salamanca Cox

Reputation: 69

Please be sure to read the previous answers and comments and understand why this should not be attempted on a production level application. The following is 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 re-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: 2

dede9714
dede9714

Reputation: 73

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);

Upvotes: 1

Raul Rene
Raul Rene

Reputation: 10270

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.

Upvotes: 15

haventchecked
haventchecked

Reputation: 2016

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

Upvotes: 0

powerkor
powerkor

Reputation: 31

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())

Upvotes: -5

Peter Lawrey
Peter Lawrey

Reputation: 533492

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.

Upvotes: 14

Keith Randall
Keith Randall

Reputation: 23265

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.

Upvotes: 24

Saeed Amiri
Saeed Amiri

Reputation: 22555

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.

Upvotes: 1

Abraham Adam
Abraham Adam

Reputation: 633

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.

Upvotes: 1

Related Questions