Tom Clement

Greenhorn

Posts: 26

posted 13 years ago

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

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

posted 13 years ago

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

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

posted 13 years ago

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 ]

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

posted 13 years ago

as I know, BigInteger does have a pow() method, if you must

use BigDecimal class, put multiply() inside for loop to

get desired power.

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

posted 13 years ago

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 ]

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 Clement

Greenhorn

Posts: 26

posted 13 years ago

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

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

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 13 years ago

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

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 ]

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

Posts: 40

Tom Clement

Greenhorn

Posts: 26

posted 13 years ago

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

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