# MathUtils.binomialCoefficient(n,k) fails for large results

XMLWordPrintableJSON

#### Details

• Bug
• Status: Closed
• Major
• Resolution: Fixed
• 2.0
• None
• None

#### Description

Probably due to rounding errors, MathUtils.binomialCoefficient(n,k) fails for results near Long.MAX_VALUE.

The existence of failures can be demonstrated by testing the recursive property:

```         assertEquals(MathUtils.binomialCoefficient(65,32) + MathUtils.binomialCoefficient(65,33),
MathUtils.binomialCoefficient(66,33));
```

Or by directly using the (externally calculated and hopefully correct) expected value:

```         assertEquals(7219428434016265740L, MathUtils.binomialCoefficient(66,33));
```

I suggest a nonrecursive test implementation along the lines of

MathUtilsTest.java
```    /**
* Exact implementation using BigInteger and the explicit formula
* (n, k) == ((k-1)*...*n) / (1*...*(n-k))
*/
public static long binomialCoefficient(int n, int k) {
if (k == 0 || k == n)
return 1;
BigInteger result = BigInteger.ONE;
for (int i = k + 1; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
for (int i = 1; i <= n - k; i++) {
result = result.divide(BigInteger.valueOf(i));
}
if (result.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
throw new ArithmeticException(
"Binomial coefficient overflow: " + n + ", " + k);
}
return result.longValue();
}
```

Which would allow you to test the expected values directly:

```         assertEquals(binomialCoefficient(66,33), MathUtils.binomialCoefficient(66,33));
```

#### Attachments

1. binomialPatch.txt
15 kB
Phil Steitz
2. binomialPatch_cs.txt
8 kB
Christian Semrau

#### People

Phil Steitz
Christian Semrau