# commons-issues mailing list archives

##### Site index · List index
Message view
Top
From "Christian Semrau (JIRA)" <j...@apache.org>
Subject [jira] Created: (MATH-241) MathUtils.binomialCoefficient(n,k) fails for large results
Date Fri, 16 Jan 2009 23:35:59 GMT
MathUtils.binomialCoefficient(n,k) fails for large results
----------------------------------------------------------

Key: MATH-241
URL: https://issues.apache.org/jira/browse/MATH-241
Project: Commons Math
Issue Type: Bug
Affects Versions: 2.0
Reporter: Christian Semrau

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 recursion property:

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

I suggest a nonrecursive test implementation along the lines of

/**
* 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));

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

Mime
View raw message