javabigdecimalarithmeticexception

Possible solutions to BigDecimal underflow error


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.


Solution

  • 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.)