Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-241

MathUtils.binomialCoefficient(n,k) fails for large results

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 2.0
    • Fix Version/s: 2.0
    • Labels:
      None

      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:

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

      Or by directly using the (externally calculated and hopefully correct) expected value:

               assertEquals(7219428434016265740L, MathUtils.binomialCoefficient(66,33));
      

      I suggest a nonrecursive test implementation along the lines of

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

        Attachments

        1. binomialPatch_cs.txt
          8 kB
          Christian Semrau
        2. binomialPatch.txt
          15 kB
          Phil Steitz

          Activity

            People

            • Assignee:
              psteitz Phil Steitz
              Reporter:
              chsemrau Christian Semrau
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: