This week's book giveaway is in the OCPJP forum.
We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line!
See this thread for details.
The moose likes Java in General and the fly likes large exponents? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "large exponents?" Watch "large exponents?" New topic
Author

large exponents?

Tom Clement
Greenhorn

Joined: Mar 21, 2004
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

Joined: Mar 15, 2004
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

Joined: Mar 21, 2004
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

Joined: Aug 24, 2001
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

Joined: Mar 21, 2004
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

Joined: Aug 24, 2001
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

Joined: Mar 21, 2004
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

Joined: Mar 21, 2004
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

Joined: Jan 30, 2000
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 ]

"I'm not back." - Bill Harding, Twister
Parth Sagdeo
Ranch Hand

Joined: Mar 18, 2004
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

Joined: Mar 21, 2004
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
 
 
subject: large exponents?