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

XMLWordPrintableJSON

#### Details

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.0
• Fix Version/s:
• Labels:
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_cs.txt
8 kB
Christian Semrau
2. binomialPatch.txt
15 kB
Phil Steitz

#### People

• Assignee:
Phil Steitz
Reporter:
Christian Semrau