Java Compute C(n,k) and factorial with biginteger

Question

I want to compute the answer of C(n,k),such as C(10,2)=10*9/2*1 = 45 If I test my code by small numbers like 10, the code works. However, when I try to compute C(1000,900), it compiles

Exception in thread "main" java.lang.ArithmeticException: / by zero

I've seen someone says it should use BigInteger,But after I tried, it still has errors.

For example: I change int factorial into BigInteger factorial, while the for loop in cSelect, I can not change int i into BigInteger type, As result, the answer up/factorial(y) has errors.

Please help me to fix this problem. Thanks!!

public class Test {

    // Write a factorial function
    static int factorial(int m) {
        int result =1;
        for (int i=2; i<=m; i++) {
            result = result*i;
        }
        return result;
    }

    // Caculate C(x,y)
    static int cSelect(int x, int y) {
        int up=1;
        for(int i=x; i>=(x-y+1); i--) {
            up = up*i;
        }
        return up/factorial(y);
    }

    public static void main(String[] args) {
        System.out.println(cSelect(1000,900));

    }

}

Answer 1

First, return value must be BigInteger, because result of C(1000,900) far exceeds the range on an int.

Second, you don't need separate factorial() method. Doing the division as you iterate will improve memory footprint by not creating excessively large intermediate values (at cost of doing multiple divisions, but even so it might actually be faster).

Like this:

static BigInteger cSelect(int x, int y) {
    BigInteger v = BigInteger.ONE;
    for (int i = x, j = 1; j <= y; i--, j++)
        v = v.multiply(BigInteger.valueOf(i)).divide(BigInteger.valueOf(j));
    return v;
}

By counting i down and j up, there will never be a fraction from the division.

Test

System.out.println(cSelect(10, 2));
System.out.println(cSelect(1000, 900));

Output

45
63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890