# large exponents?

Tom Clement
Greenhorn
Posts: 26
I'm working on a project which must calculate large exponents.
For example: 20 raised to the 10,000 etc...
Right now it simply overflows. Is there some sort of approximation,
(Stirling's comes to mind, but it's been awhile) that I could use to get larger exponents?
I looked at the newest version of jdk and it looks like there will be support
but I guess it's still beta. I'm looking for a formula....Thanks in advance
Tom

Tim West
Ranch Hand
Posts: 539
Are you aware of the BigInteger class?
BigIntegers can be arbitrarily large.
The downside is that you can't use infix + or -, it's all mySum = myBigInt.add(myOtherBigInt)
--Tim

Tom Clement
Greenhorn
Posts: 26
Yeah, I'm aware of it, but haven't figured out how to use it to solve my
problem. I tried it and BigDecimal, with the exception of the new methods in the beta I referenced, nothing simple like Math.pow(20,10000).

Here's what I get from example code:
---------------------------
import java.math.*;
class BigInt
{
public static void main(String args[])
{
BigInteger bi = BigInteger.valueOf(20);
System.out.println(bi.pow(10000));
}
}
------------------------------------
It handles the size fine, the final display is poor. Can I
get some exponential notation, e.g., 1.9950631168807583848837421627e13010
Any code snippets, or suggestions? Thanks for the reply.
Tom
[ March 21, 2004: Message edited by: Tom Thumb ]

chi Lin
Ranch Hand
Posts: 348
as I know, BigInteger does have a pow() method, if you must
use BigDecimal class, put multiply() inside for loop to
get desired power.

Originally posted by Tom Thumb:
Yeah, I'm aware of it, but haven't figured out how to use it to solve my
problem. I tried it and BigDecimal, with the exception of the new methods in the beta I referenced, nothing simple like Math.pow(20,10000).
Any code snippets, or suggestions? Thanks for the reply.
Tom

Tom Clement
Greenhorn
Posts: 26
Hello chi,
Thanks for the reply, I was editing my post above before I saw yours.
What I'm looking for is a return of the following from our example data.
1.9950631168807583848837421627e+13010
See above for snippet that demonstrates what BigInteger returns. Must be
a way to format that data that I'm missing. Could you provide snippet of
your multiply() idea? Or are you saying that I could do the brute force method?
BigInteger bi = BigInteger.valueOf(20);
for (int i = 0; i < 10000; i++)
{
bi*= 20;
}
Just in case, I'll give that a try....
Thanks again...
Tom
[ March 21, 2004: Message edited by: Tom Thumb ]

chi Lin
Ranch Hand
Posts: 348
Tom,
For formatting the output, try the following, once
it works, you can create a method to dynamically
generate how many precision bits you need.

HTH
[ March 21, 2004: Message edited by: chi Lin ]

Tom Clement
Greenhorn
Posts: 26
Thanks, I'll give it a try right away.
I tried the multiply()
import java.math.*;
class BigInt
{
public static void main(String args[])
{
BigInteger bi1 = BigInteger.valueOf(20);
BigInteger bi2 = BigInteger.valueOf(20);
for (int i = 0; i < 10000; i++)
{
bi1= bi1.multiply(bi2);
}
System.out.println(bi1);
}
}
Worked the same but slower.....Thanks again...
Tom

Tom Clement
Greenhorn
Posts: 26
That's it
Chi, you're a life(time)saver. I only have a limited number of hours in
my life and you've just saved me a bunch. Thanks, consider this topic's question solved......
Tom

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Another possibility:
Math.pow(x, y) == Math.exp( y * Math.log(x) )
This equation is exact, except that since Math.pow() and Math.log() use doubles, they will be accurate to "only" 18 digits or so. If you want an exact answer, you'll need BigInteger as suggested. But if an approximation is acceptable, the above formula can be much faster, especially for large values of y.
Note also that it's possible to modify the BigInteger algorithm to greatly reduce the number of multiplications (though it will still be slower than the above formula). E.g.
20 ^ 10000 = (20 ^ 8192) * (20 ^ 1024) * (20 ^ 512) * (20 ^ 256) * (20 ^ 16)
These factors can be calculated thus:
20 ^ 4 = (20 ^ 2) ^2
20 ^ 8 = (20 ^ 4) ^2
20 ^ 16 = (20 ^ 8) ^2
20 ^ 32 = (20 ^ 16) ^2
20 ^ 64 = (20 ^ 32) ^2
20 ^ 128 = (20 ^ 64) ^2
20 ^ 256 = (20 ^ 128) ^2
20 ^ 512 = (20 ^ 256) ^2
20 ^ 1024 = (20 ^ 512) ^2
20 ^ 2048 = (20 ^ 1024) ^2
20 ^ 4096 = (20 ^ 2048) ^2
20 ^ 8192 = (20 ^ 4096) ^2
Thus 20 ^ 8192 can be calculated using only twelve multiplications - and along the way, you've calculated all the other factors from the formula I gave for 20 ^ 10000. The entire calculation can now be completed in four more multiplications.
Generalizing this algorithm for x ^ y is left as an excercise for the student. If time and motivation warrant.
[ March 21, 2004: Message edited by: Jim Yingst ]

Parth Sagdeo
Ranch Hand
Posts: 40
What if you just used scientific notation? That would seem to be the easiest. Or, if you wanted to print the whole thing out, what if you increased the size alloted to JVM?Those seem easiest, but might not work.

Tom Clement
Greenhorn
Posts: 26
Parth, I'll look into that, as I saw some reference to it during my search for answers. Any assistance would be greatly appreciated.
I do have one more problem which I need help solving. I tried for the last
two days but to no avail.
Chi's method works fine for my purposes, except when I have to multiply
"with a negative exponent."
I don't know how to implement that.
I understand that dividing is the same as multiplying with a negative exponent.
But when I use BigDecimal.divide() it stops at zero. When I use double it
continues into the negative. Example:
import java.math.*;
public class Test {
public static void main(String[] args) {
//say the exponent is -10
//using BigDecimal
BigDecimal bd1 = BigDecimal.valueOf(20);
BigDecimal bd2 = BigDecimal.valueOf(20);
for(int j = -2; j > -10; j--)
{
bd1= bd1.divide(bd2,10,BigDecimal.ROUND_DOWN);
System.out.println("Big Decimal = " +bd1);
}
//using double
double d1 = 20;
double d2 = 20;
for(int k = -2; k > -10; k--)
{
d1 = d1 / d2;
System.out.println("double = " +d1);
}
}//end main
}
What's going on? Anybody studied this topic before?
Thanks,
Tom