• Post Reply Bookmark Topic Watch Topic
  • New Topic

Working with Verrry Large Numbers  RSS feed

 
Yogesh Chhawasaria
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!