[jira] Commented: (MATH-241) MathUtils.binomialCoefficient(n,k) fails for large results

["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.