Possible solutions to BigDecimal underflow error

Question

I am trying to use the BigDecimal.pow(int i) with very big base and exponents, however I'm getting an ArithmeticException: Underflow error.

To simply put it, the code is:

BigDecimal base = BigDecimal.valueOf(2147483645.4141948);
BigDecimal product = base.pow(987654321);

System.out.println("product = " + product.toPlainString());

Yes, this is a Project Euler problem. However I know my numbers are correct. This is not a mathematical problem, it is purely me not understanding why BigDecimal.pow(int i) is giving me an ArithmeticException: Underflow.

I know that BigDecimal's scale is a 32-bit int but is there any way at all to bypass this and calculate such a big value? If it helps, I do plan on flooring the product and modding it by 100000000 since I only want the last 8 digits. If there is any other way I could do this mathematically, I'd like a hint.

Stack trace:

Exception in thread "main" java.lang.ArithmeticException: Underflow
    at java.math.BigDecimal.checkScale(BigDecimal.java:3841)
    at java.math.BigDecimal.pow(BigDecimal.java:2013)
    at test.main(test.java:10)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:498)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

Process finished with exit code 1

Thanks.

Answer 1

The answer is a decimal number with 6913580247 decimals ending in "11234048" (the last 8 decimals). You have 7 decimals in your base, and 987654321 * 7 equals 6913580247.

My problem is this number cannot be represented in a BigDecimal because it would need a scale of 6913580247, which overflows the integer that BigDecimal uses for its scale. I don’t know in which format you want your number instead. The following code prints out the result as

Result is 1.1234048e-6913580240

That is, like scientific notation, only with an exponent out of the normal range for scientific notation. For the modulo 100000000 I am using:

public static final BigDecimal moduloBase = new BigDecimal(10).pow(8); // 8 digits

Now I do:

    long noOfDecimals = 987654321L * 7L;

    BigDecimal bd = new BigDecimal("54141948"); // last 8 digits of base
    bd = bd.pow(379721);
    bd = bd.remainder(moduloBase);
    bd = bd.pow(2601);
    bd = bd.remainder(moduloBase);

    double result = bd.doubleValue() / 10_000_000.0; // print with 7 decimals
    System.out.println("Result is " + result + "e" + (-(noOfDecimals - 7)));

I am using the trick from Anton Dovzhenko’s answer and the fact that 987654321 is 2601 * 379721. The calculation takes some 4 seconds on my computer, this will probably vary a great deal.

Looking forward to your follow-up questions.

EDIT: The central part of the calculation can be done both with simpler code and faster using BigInteger instead of BigDecimal:

    BigInteger bi = new BigInteger("54141948");
    bi = bi.modPow(new BigInteger("987654321"), new BigInteger("100000000"));
    System.out.println("As BigInteger: " + bi);

(It prints 11234048 as we now know it should.)

Answer 2

Computation could be broken in several parts, for example:

BigDecimal base = BigDecimal.valueOf(2147483645.4141948);
base = base.setScale(20, BigDecimal.ROUND_FLOOR);
// 109739369 = 6455257 * 17
base = base.pow(17).setScale(20, BigDecimal.ROUND_FLOOR);
base = base.pow(6455257);

ArithmeticException is thrown because scaleValue * powValue is outside [Integer.MIN_VALUE; Integer.MAX_VALUE] segment. Note, that resetting of scale after applying pow is necessary, because BigDecimal scale is recalculated every time pow is invoked and equal to oldScaleValue * powValue

Also, I assume, that getting pow value will take much time