• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Working with Verrry Large Numbers

 
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Now I am super curious what sports would be like if we allowed drugs and tiny ads.
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic