30

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.

Sean Patrick Floyd
  • 292,901
  • 67
  • 465
  • 588
PeterW
  • 309
  • 1
  • 3
  • 3
  • `BigInteger` cannot represent numbers of infinite size, it can only represent numbers "close to" arbitrary size. The maximum representable number depends on your implementation (internal data structures) and the available heap memory. – Roland Illig Jan 03 '11 at 06:45
  • why do you need it? Like Saeed says below even smallest such value where int is not enough is too big... – Fakrudeen Jan 03 '11 at 07:35
  • It only makes sense when you compute modulo a `BigInteger`, for that case it exists: http://download.oracle.com/javase/6/docs/api/java/math/BigInteger.html#modPow(java.math.BigInteger,%20java.math.BigInteger) – starblue Jan 03 '11 at 12:28
  • possible duplicate of [How do you raise a Java BigInteger to the power of a BigInteger without doing modular arithmetic?](http://stackoverflow.com/questions/2839262/how-do-you-raise-a-java-biginteger-to-the-power-of-a-biginteger-without-doing-mod) – finnw Jan 30 '11 at 21:12

9 Answers9

24

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.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • 3
    +1 for showing that it's possible (even though it's probably not a good idea) – Sean Patrick Floyd Jan 03 '11 at 09:30
  • @Sean Patrick Floyd, @Keith Randall, It's possible to write code as simple as this but it's not possible to use it, what's the usage of big integer coef in this case????? did you can use a range of big integer which is not in int????? This code is just slow, because biginteger is very slower than int. – Saeed Amiri Jan 03 '11 at 11:38
  • 1
    Yes, it will be pretty slow, and probably not very useful. But it answers the OP's question as to how to test how big a BigInteger he can make. And the same algorithm IS useful when using modular arithmetic - see BigInteger.modPow, which does take a BigInteger exponent. – Keith Randall Jan 03 '11 at 16:26
  • I think `OP` asked for why there is no pow for big integer coef in java not how to implement it. – Saeed Amiri Jan 03 '11 at 17:25
  • 3
    @Saeed, he didn't ask why BigInteger.pow is that way, he asked if it was possible to use a larger exponent. – Keith Randall Jan 03 '11 at 20:29
  • I tried 99999999999999999^99999999999999999 and it seems to run forever. Here is snippet of my code: `BigInteger number1 = BigInteger.valueOf(99999999999999999L); BigInteger number2 = BigInteger.valueOf(99999999999999999L); System.out.println(pow(number1, number2));` – HendraWD Sep 29 '16 at 05:26
  • 2
    @HendraWijayaDjiono: the result has ~10^18 digits in it. Load your computer up with a million terabytes of RAM and try again... – Keith Randall Sep 29 '16 at 07:00
15

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.

mimibar
  • 7
  • 2
Raul Rene
  • 10,014
  • 9
  • 53
  • 75
13

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • plus one for "BTW" portion... just a question more, what about if I only store such a "BIG" BigInteger in a BigInteger type variable? I did it, divided it with another BigInteger and tried to get the remainder. Then I tried to print remainder, but console is taking too much time to show the remainder. – Mukit09 Nov 15 '17 at 05:33
  • @Mukit09 if all you need is the remainder and that is relatively small, most likely it is more efficient to just calculate the remainder instead of the large value. e.g. `pow` can be very expensive but `modPow` can be dramatically faster. Note: consoles esp the DOS console is very slow. Try writing the number to a file instead. – Peter Lawrey Nov 15 '17 at 08:36
  • thanks for your reply. My that problem is solved, but I want to know the fact now. When I tried to store such BIG BigInteger in a variable, I guess, it's a problem too, as my RAM is not able to give such spaces to that variable. Would you please tell me if I'm wrong? – Mukit09 Nov 15 '17 at 08:48
  • 1
    @Mukit09 memory is one problem however large numbers can take much longer to process and display even if you have plenty of memory. – Peter Lawrey Nov 17 '17 at 07:10
  • thanks for your reply, @Peter Lawrey. I'm clear now. :) – Mukit09 Nov 29 '17 at 09:32
  • 1
    toString would not work because strings internally use arrays which are limited to Integer.MAX_VALUE in their size. – mmirwaldt Aug 13 '19 at 21:23
2

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.

Suraj Rao
  • 29,388
  • 11
  • 94
  • 103
Marcelo Salamanca Cox
  • 59
  • 1
  • 6
1

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

dede9714
  • 73
  • 2
  • 13
1

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.

Abraham Adam
  • 635
  • 1
  • 6
  • 16
1

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.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • 1
    @Fakrudeen, It's NPC in space. – Saeed Amiri Jan 03 '11 at 11:35
  • Computing power is not NPC. It is very much polynomial. For an example algo. see Keith's answer. Calculating n^m is atmost (mlogn) ^2 * logm which is clearly less than (max(n,m))^4. Also your definition of NPC is not correct. NPC means you can verify the answer in polynomial time, but the solution is NP hard (polynomial in non deterministic TM model). – Fakrudeen Jan 03 '11 at 11:40
  • NPC in space would imply atleast NPC in time, Because using up that much space itself will take up NPC time! – Fakrudeen Jan 03 '11 at 11:42
  • @Fakrudeen, The input can be coded in O(log(m) + log(n), this is true yes? and the outpul m^n can be coded in `n log(m)` which has no polynomial relation to input size (log(m) +log(n))^veryLargeNumber < n log(m) (i.e m == n), and NPC in space doesn't mean NPC in time or vise versa. and that's not my definition it's Gary and Johnson books definition. – Saeed Amiri Jan 03 '11 at 11:45
  • Also for your computation, input can be coded in O(log m+ log n) and if the answer is `n log(m)*...` indeed it's NPC in time too, but I just try to talk about space (to say we can't use it) – Saeed Amiri Jan 03 '11 at 11:49
0

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

haventchecked
  • 1,916
  • 1
  • 21
  • 24
-5

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())
Mick MacCallum
  • 129,200
  • 40
  • 280
  • 281
powerkor
  • 31
  • 2