[
https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Christian Semrau updated MATH-241:
----------------------------------
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:
{noformat}
assertEquals(MathUtils.binomialCoefficient(65,32) +
MathUtils.binomialCoefficient(65,33),
MathUtils.binomialCoefficient(66,33));
{noformat}
Or by directly using the (externally calculated and hopefully correct) expected
value:
{noformat}
assertEquals(7219428434016265740L,
MathUtils.binomialCoefficient(66,33));
{noformat}
I suggest a nonrecursive test implementation along the lines of
{code:title=MathUtilsTest.java|borderStyle=solid}
/**
* 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();
}
{code}
Which would allow you to test the expected values directly:
{noformat}
assertEquals(binomialCoefficient(66,33),
MathUtils.binomialCoefficient(66,33));
{noformat}
was:
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));
> 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 recursive
> property:
> {noformat}
> assertEquals(MathUtils.binomialCoefficient(65,32) +
> MathUtils.binomialCoefficient(65,33),
> MathUtils.binomialCoefficient(66,33));
> {noformat}
> Or by directly using the (externally calculated and hopefully correct)
> expected value:
> {noformat}
> assertEquals(7219428434016265740L,
> MathUtils.binomialCoefficient(66,33));
> {noformat}
> I suggest a nonrecursive test implementation along the lines of
> {code:title=MathUtilsTest.java|borderStyle=solid}
> /**
> * 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();
> }
> {code}
> Which would allow you to test the expected values directly:
> {noformat}
> assertEquals(binomialCoefficient(66,33),
> MathUtils.binomialCoefficient(66,33));
> {noformat}
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
