You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Christian Semrau (JIRA)" <ji...@apache.org> on 2009/01/17 00:35:59 UTC
[jira] Created: (MATH-241) MathUtils.binomialCoefficient(n,k) fails
for large results
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.
[jira] Resolved: (MATH-241) MathUtils.binomialCoefficient(n,k)
fails for large results
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz resolved MATH-241.
------------------------------
Resolution: Fixed
Applied second patch along with changes to double, log versions from first patch in r735879. Many thanks.
> 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
> Assignee: Phil Steitz
> Fix For: 2.0
>
> Attachments: binomialPatch.txt, binomialPatch_cs.txt
>
>
> 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.
[jira] Commented: (MATH-241) MathUtils.binomialCoefficient(n,k)
fails for large results
Posted by "Christian Semrau (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12665253#action_12665253 ]
Christian Semrau commented on MATH-241:
---------------------------------------
I think the recursive computation of Pascal's triangle (even with caching or dynamic programming) is unnecessarily complicated except to ensure correct values.
The attached patch ensures accuracy for all values that can be represented as a long integer, with a running time proportional to k*log(k) (assuming gcd(i,j) takes log(j) steps). It should be faster than the current version for n <= 61, but for n > 61 my version computes as much as k different gcd values, which might be slower.
I did not modify the double and log version, but your patch can be applied to these.
> 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
> Assignee: Phil Steitz
> Fix For: 2.0
>
> Attachments: binomialPatch.txt, binomialPatch_cs.txt
>
>
> 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.
[jira] Updated: (MATH-241) MathUtils.binomialCoefficient(n,k) fails
for large results
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-241:
-----------------------------
Fix Version/s: 2.0
Assignee: Phil Steitz
> 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
> Assignee: Phil Steitz
> Fix For: 2.0
>
>
> 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.
[jira] Updated: (MATH-241) MathUtils.binomialCoefficient(n,k) fails
for large results
Posted by "Christian Semrau (JIRA)" <ji...@apache.org>.
[ 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.
[jira] Updated: (MATH-241) MathUtils.binomialCoefficient(n,k) fails
for large results
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-241:
-----------------------------
Attachment: binomialPatch.txt
First, thanks for reporting this. Due to log/exp rounding and double/long conversion, the current code returns bad values for many long-representable values, starting as low as n = 48. The returned value can be off by as much as 200,000. The error in binomial(66, 29) is 214,880. All b(n,k) for n < 48 are exact.
Attached is a patch that ensures accuracy up to n = 200 (specified as a constant) and allows the user to force exact computation for values beyond this if desired. For n <= 200, the implementation works like an unwound recursive implementation. I also improved the accuracy of the double-valued and log versions. The latter perform better than the current implementations, but the long-valued version is approximately 8x slower than the current version. I did not benchmark the BigInteger version, but suspect that would be slower still. The most accurate (for n <= 200) non-recursive formula that I could find is the one that I implemented in the double version.
I also investigated overflow behavior and added tests to confirm correctness. As stated in the API doc, overflows start at n = 67. For n = 200, values of k less than 14 or greater than 186 can still be computed without overflow; but all others throw ArithmeticException.
I would appreciate feedback on the patch and any better ideas on how to fix the problem.
> 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
> Assignee: Phil Steitz
> Fix For: 2.0
>
> Attachments: binomialPatch.txt
>
>
> 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.
[jira] Updated: (MATH-241) MathUtils.binomialCoefficient(n,k) fails
for large results
Posted by "Christian Semrau (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Christian Semrau updated MATH-241:
----------------------------------
Attachment: binomialPatch_cs.txt
Attached is my version of a new binomialCoefficient function.
> 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
> Assignee: Phil Steitz
> Fix For: 2.0
>
> Attachments: binomialPatch.txt, binomialPatch_cs.txt
>
>
> 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.