• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

large exponents?

 
Tom Clement
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic