BigDecimal division breaks down when dividing by factorials

Question

I'm writing a brute-force solution to a combinatorics problem that involves dividing by very large numbers. I turned to BigInteger and BigDecimal to handle these, but I've come upon an error when the factorial gets big enough that I haven't been able to pin down.

    int n = num;
    int k = num;
    BigDecimal sum = new BigDecimal("0");
    BigDecimal factorialN = new BigDecimal(factorial(n));
    BigInteger factorialI;
    BigInteger factorialJ;
    BigInteger factorialM;
    BigInteger denominator;
    double threePowerN = pow(3, n);        

    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            for (int m = 0; m < k; m++) {

                if (i + j + m == n) { 
                    factorialI = factorial(i);
                    factorialJ = factorial(j);
                    factorialM = factorial(m);
                    denominator = factorialI.multiply(factorialJ);
                    denominator = denominator.multiply(factorialM);
                    denominator = denominator.multiply(new BigInteger(String.valueOf((int)threePowerN)));
                    BigDecimal lastTerm = new BigDecimal(denominator);
                    lastTerm = factorialN.divide(lastTerm, 100, RoundingMode.HALF_EVEN);
                    sum = sum.add(lastTerm);
                }
            }
        }
    }
    // prints
    // -0.62366051209329651, which doesn't make sense because this should 
    // be a percentage between 0 and 1. 
    System.out.println(new BigDecimal("1").subtract(sum));

Here is the factorial method:

 public static BigInteger factorial(int n) {
    BigInteger result = BigInteger.ONE;
    while (n != 0) {
        result = result.multiply(new BigInteger(n + ""));
        n--;
    }
    return result;
} 

All others cases, from n = k = num = 1 to 19, all work as expected: the printed value is between 0 and 1. Once I reach num = 20, sum exceeds 1, and sum - 1 becomes negative, which makes me think there's an overflow issue here. But can this be with BigIntegers/BigDecimals? What could be the problem here? Thanks in advance for your help.

Answer 1

3²⁰ is too big to fit in an int. So this will fail:

  denominator = denominator.multiply(new BigInteger(String.valueOf((int)threePowerN)));

The cast will wrap around and you will actually be multiplying by a negative number.

BigInteger has a pow function. Instead of:

double threePowerN = pow(3, n);        

try

BigInteger threePowerN = BigInteger.valueOf(3).pow(n);

and then

denominator = denominator.multiply(threePowerN);

By the way, you don't have to convert your integers to String in order to convert them to a BigInteger. BigInteger doesn't have a constructor that takes an integer value, but it does have a static valueOf method.