How to find power of power of a number like 2^(10^9) in java

Question

Math.pow() returns a double value and takes only int as parameters...BigInteger as no function for finding BigInteger^BigInteger Doing it through loops takes really long time... Is there any more way i am missing?

Thnx in advance...

Have a look at this question: http://stackoverflow.com/questions/4582277/biginteger-powbiginteger — micha, Nov 01 '13 at 19:58
You can look into exp (http://docs.oracle.com/javase/6/docs/api/java/lang/Math.html#exp%28double%29) — Mike, Nov 01 '13 at 19:58
Two things to note: 1. assuming no overhead, you would need 125MB (1Gb) of memory to store that numerical value. Probably, you will need more while calculating it. 2. before doing this hardcore math, ask yourself if it is necessary. Simplify and apply mathematical properties/identities (e.g. you could easily calculate in mind the 1GB value I gave you some lines above) — Stefano Sanfilippo, Nov 01 '13 at 20:04
`2^(10^9)` is, in binary, a `1` followed by one billion zeros. In decimal it's approximately `10^(3x10^8)`, or `1` followed by 300-million zeros. — Jim Garrison, Nov 01 '13 at 20:08
@JimGarrison if yours was the answer to the question "how to calculate 2^(10^9)", then I would give you my +1000 ;) anyway the OP wants an answer for values _like_ that, I assume he/she means "of the same order of magnitude". — Stefano Sanfilippo, Nov 01 '13 at 20:11
@everyone: used modPow(BigInteger, BigInteger) and it worked... thnx to all :) — gonephishing, Nov 01 '13 at 20:19
@StefanoSanfilippo my (subtle) point was that even if you calculated that number you couldn't do anything with it... you certainly couldn't print it out :-) — Jim Garrison, Nov 01 '13 at 20:35

Ted Hopp · Accepted Answer · 2013-11-01T20:12:00.613

You can use BigInteger.pow() to take a large exponent. Since 10⁹ fits into an int and is also exactly representable as a double, you can do this:

int exp = (int) Math.pow(10, 9);
BigInteger answer = BigInteger.valueOf(2).pow(exp);

This obviously breaks down for exponents larger than Integer.MAX_VALUE. However, you can then use BigInteger.modPow(BigInteger exponent, BigInteger m) to raise a BigInteger to another BigInteger as a power, module a third BigInteger. You just need to first create a BigInteger that is larger than your expected answer to serve as a modulus.

score 3 · Answer 2 · answered Nov 01 '13 at 20:06

3

If you have 2^x, where x is some large number then you can do this through bit shifting. Example:

2^4 == (1 << 4);
2^12 == (1 << 12);

With BigIntegers you can do the same thing with the shiftLeft() and shiftRight() methods.

answered Nov 01 '13 at 20:06

Dale Myers

2,703
3
26
48

score 1 · Answer 3 · answered Nov 01 '13 at 20:02

1

Math.pow() returns a double value and takes only int as parameters.

No, it takes two doubles and returns a double: Javadoc.

If you don't need the exact answer, it will probably do just fine.

answered Nov 01 '13 at 20:02

NPE

486,780
108
951
1,012

score 1 · Answer 4 · answered Nov 01 '13 at 20:17

You can use pow, but left shift is likely to be faster.

 BigInteger bi = BigInteger.ONE.shiftLeft(1_000_000_000);

The reason BigInteger.pow(BigInteger) is not support is likely to be that for even the most trivial examples, you would need more memory than any computer in the world to hold such a value. The smallest value which requires a BigInteger exponent is 2^63 and 2<<2^63 requires 2^60 bytes of memory or one trillion GB.

How to find power of power of a number like 2^(10^9) in java

4 Answers4

Linked