Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login Win a copy of Arduino in Action this week in the General Computing forum! A special promo: Enter your blog post or vote on a blogger to be featured in an upcoming Journal

# Working with Verrry Large Numbers

Yogesh Chhawasaria
Ranch Hand

Joined: Apr 02, 2004
Posts: 53
Hello

I need to work with very large numbers (e.g. 2 ^ 8192 , 2 ^ (8192*8192)) and so on

I am using BigInteger but overall computing becomes very slow when i go for 2 ^ (500 * 8192)

Can someone sugggest me someway to make this faster or
Is there any way to utilize CPU power of other machine (besides my machine)

ANy suggestions are welcome.

When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18670
First, are you using BigInteger's pow() method? That has a nice trick inside it which is somewhat faster than, for example, performing 8192 multiplications to get 2^8192. Instead it uses successive squares, i.e. 2, 4, 16, 256, 65536, etc.

Unfortunately for numbers the size you're talking about, this still becomes very slow. There are just so many digits to compute.

If you can make use of an approximate answer, e.g. one rounded to the same precision used by doubles, then you can get a result fairly quickly. You probably already know that your numbers are outside the range of a double, and some are even outside the range of BigDecimal, since it uses an int for its exponent, internally. But you can still get results with a little creativity:

This returns a String giving a result in exponential form. E.g. pow(2, 4) = "1.6E1" which is 16. I'm not sure how useful the String itself might be to you, but you could create a new class that has mantissa and exponent as member fields, and use this class to represent really huge numbers and perform calculations with them, similar to BigInteger and BigDecimal. By using double for the mantissa and long for the exponent, you get fast results at the expense of losing all digits after the first, what, 16 or so. You could probably also use a double for the exponent and represent even bigger numbers, but I'm not sure how necessary that is, and there may be additional roundoff errors to deal with.

If you need exact results and have access to additional processors, I think you may be able to parallelize multiplication somewhat. E.g.

12345789 * 987654321

could be computed as

(123 * 987654321) + (456 * 1000 * 987654321) + (789 * 1000000 * 987654321)

Each of these terms might be sent to a different processor for calculation, then the results added together. For numbers this size (nine digits), that's not worth the trouble - but for thousands and millions of digits, it could be beneficial. You'd want to keep the simple power-of-ten factors out of the operation and track those separately, so that for each mulitiplication performed by BigInteger, the number of digits in one of the factors has been reduced by a factor of three (or however many ways you split it). You could similarly break the 987654321 into subgroups. So you could, for example, have nine different processors computing parts:

(123 * 987 * 10^12) + (123 * 654 * 10^9) + (123 * 321 * 10^6) +
(456 * 987 * 10^9) + (456 * 654 * 10^6) + (456 * 321 * 10^3) +
(789 * 987 * 10^6) + (789 * 654 * 10^3) + (789 * 321 * 10^0)

I think that to make use of something like this, you'd want to make a new class, something like

So for example

(123 * 987 * 10^12)

which came from

(123 * 10^6 * 897 * 10^6)

could be represented as

Out of curiosity, what are you doing that requires such huge numbers, anyway?

"I'm not back." - Bill Harding, Twister

I agree. Here's the link: http://ej-technologies/jprofiler - if it wasn't for jprofiler, we would need to run our stuff on 16 servers instead of 3.

subject: Working with Verrry Large Numbers