Working with Verrry Large Numbers

[Yogesh Chhawasaria]

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]

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:

    public static String pow(double base, double power) {
        double logResult = Math.log10(base) * power;
        long exponent = (long) Math.floor(logResult);
        double mantissa = Math.pow(logResult - exponent);
        return mantissa + "E" + exponent;
    }

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

public class HugeInteger {
    private final BigInteger value;
    private final long extraExponent;
 
    public HugeInteger(BigInteger value, long extraExponent) {
        this.value = value;
        this.extraExponent = extraExponent;
    }
 

    public HugeInteger(long value, long extraExponent) {
        this(BigInteger.valueOf(value), extraExponent);
    }
 
    public HugeInteger multiply(HugeInteger other) {
        return new HugeInteger(value.multiply(other.value), extraExponent + other.extraExponent);
    }
 
    // define other operations as needed
}

So for example

(123 * 987 * 10^12)

which came from

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

could be represented as

HugeInteger product = new HugeInteger(123, 6).multiply(new HugeInteger(987, 6));

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