commons-issues mailing list archives

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

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


Mime
View raw message