commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From celes...@apache.org
Subject svn commit: r1182658 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/analysis/polynomials/ main/java/org/apache/commons/math/distribution/ main/java/org/apache/commons/math/fraction/ main/java/org/apache/commons/math/util/ test/j...
Date Thu, 13 Oct 2011 05:29:28 GMT
Author: celestin
Date: Thu Oct 13 05:29:28 2011
New Revision: 1182658

URL: http://svn.apache.org/viewvc?rev=1182658&view=rev
Log:
Finished moving methods from MathUtils to ArithmeticsUtils (MATH-689)

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/HypergeometricDistributionImpl.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/PascalDistributionImpl.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/fraction/Fraction.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/ArithmeticsUtils.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/linear/InverseHilbertMatrix.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/ArithmeticsUtilsTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.java Thu Oct 13 05:29:28 2011
@@ -22,8 +22,8 @@ import java.util.List;
 import java.util.Map;
 
 import org.apache.commons.math.fraction.BigFraction;
+import org.apache.commons.math.util.ArithmeticsUtils;
 import org.apache.commons.math.util.FastMath;
-import org.apache.commons.math.util.MathUtils;
 
 /**
  * A collection of static methods that operate on or return polynomials.
@@ -326,7 +326,7 @@ public class PolynomialsUtils {
         final int[][] coeff = new int[dp1][dp1];
         for (int i = 0; i < dp1; i++){
             for(int j = 0; j <= i; j++){
-                coeff[i][j] = (int) MathUtils.binomialCoefficient(i, j);
+                coeff[i][j] = (int) ArithmeticsUtils.binomialCoefficient(i, j);
             }
         }
 

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/HypergeometricDistributionImpl.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/HypergeometricDistributionImpl.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/HypergeometricDistributionImpl.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/HypergeometricDistributionImpl.java Thu Oct 13 05:29:28 2011
@@ -23,7 +23,7 @@ import org.apache.commons.math.exception
 import org.apache.commons.math.exception.NotStrictlyPositiveException;
 import org.apache.commons.math.exception.NumberIsTooLargeException;
 import org.apache.commons.math.exception.util.LocalizedFormats;
-import org.apache.commons.math.util.MathUtils;
+import org.apache.commons.math.util.ArithmeticsUtils;
 import org.apache.commons.math.util.FastMath;
 
 /**
@@ -231,9 +231,9 @@ public class HypergeometricDistributionI
      * @return PMF for the distribution.
      */
     private double probability(int n, int m, int k, int x) {
-        return FastMath.exp(MathUtils.binomialCoefficientLog(m, x) +
-               MathUtils.binomialCoefficientLog(n - m, k - x) -
-               MathUtils.binomialCoefficientLog(n, k));
+        return FastMath.exp(ArithmeticsUtils.binomialCoefficientLog(m, x) +
+               ArithmeticsUtils.binomialCoefficientLog(n - m, k - x) -
+               ArithmeticsUtils.binomialCoefficientLog(n, k));
     }
 
     /**

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/PascalDistributionImpl.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/PascalDistributionImpl.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/PascalDistributionImpl.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/distribution/PascalDistributionImpl.java Thu Oct 13 05:29:28 2011
@@ -22,7 +22,7 @@ import org.apache.commons.math.exception
 import org.apache.commons.math.exception.NotPositiveException;
 import org.apache.commons.math.exception.util.LocalizedFormats;
 import org.apache.commons.math.special.Beta;
-import org.apache.commons.math.util.MathUtils;
+import org.apache.commons.math.util.ArithmeticsUtils;
 import org.apache.commons.math.util.FastMath;
 
 /**
@@ -128,7 +128,7 @@ public class PascalDistributionImpl exte
         if (x < 0) {
             ret = 0.0;
         } else {
-            ret = MathUtils.binomialCoefficientDouble(x +
+            ret = ArithmeticsUtils.binomialCoefficientDouble(x +
                   numberOfSuccesses - 1, numberOfSuccesses - 1) *
                   FastMath.pow(probabilityOfSuccess, numberOfSuccesses) *
                   FastMath.pow(1.0 - probabilityOfSuccess, x);

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/fraction/Fraction.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/fraction/Fraction.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/fraction/Fraction.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/fraction/Fraction.java Thu Oct 13 05:29:28 2011
@@ -24,7 +24,6 @@ import org.apache.commons.math.exception
 import org.apache.commons.math.exception.MathArithmeticException;
 import org.apache.commons.math.exception.NullArgumentException;
 import org.apache.commons.math.util.ArithmeticsUtils;
-import org.apache.commons.math.util.MathUtils;
 import org.apache.commons.math.util.FastMath;
 
 /**
@@ -490,12 +489,12 @@ public class Fraction
         int d1 = ArithmeticsUtils.gcd(denominator, fraction.denominator);
         if (d1==1) {
             // result is ( (u*v' +/- u'v) / u'v')
-            int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
-            int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
+            int uvp = ArithmeticsUtils.mulAndCheck(numerator, fraction.denominator);
+            int upv = ArithmeticsUtils.mulAndCheck(fraction.numerator, denominator);
             return new Fraction
                 (isAdd ? ArithmeticsUtils.addAndCheck(uvp, upv) :
                  ArithmeticsUtils.subAndCheck(uvp, upv),
-                 MathUtils.mulAndCheck(denominator, fraction.denominator));
+                 ArithmeticsUtils.mulAndCheck(denominator, fraction.denominator));
         }
         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
         // exercise 7.  we're going to use a BigInteger.
@@ -517,7 +516,7 @@ public class Fraction
                                               w);
         }
         return new Fraction (w.intValue(),
-                MathUtils.mulAndCheck(denominator/d1,
+                ArithmeticsUtils.mulAndCheck(denominator/d1,
                         fraction.denominator/d2));
     }
 
@@ -543,8 +542,8 @@ public class Fraction
         int d1 = ArithmeticsUtils.gcd(numerator, fraction.denominator);
         int d2 = ArithmeticsUtils.gcd(fraction.numerator, denominator);
         return getReducedFraction
-        (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
-                MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
+        (ArithmeticsUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
+                ArithmeticsUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
     }
 
     /**

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/ArithmeticsUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/ArithmeticsUtils.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/ArithmeticsUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/ArithmeticsUtils.java Thu Oct 13 05:29:28 2011
@@ -18,6 +18,7 @@ package org.apache.commons.math.util;
 
 import org.apache.commons.math.exception.MathArithmeticException;
 import org.apache.commons.math.exception.NotPositiveException;
+import org.apache.commons.math.exception.NumberIsTooLargeException;
 import org.apache.commons.math.exception.util.Localizable;
 import org.apache.commons.math.exception.util.LocalizedFormats;
 
@@ -77,92 +78,193 @@ public final class ArithmeticsUtils {
     }
 
     /**
-     * Add two long integers, checking for overflow.
+     * Returns an exact representation of the <a
+     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
+     * Coefficient</a>, "{@code n choose k}", the number of
+     * {@code k}-element subsets that can be selected from an
+     * {@code n}-element set.
+     * <p>
+     * <Strong>Preconditions</strong>:
+     * <ul>
+     * <li> {@code 0 <= k <= n } (otherwise
+     * {@code IllegalArgumentException} is thrown)</li>
+     * <li> The result is small enough to fit into a {@code long}. The
+     * largest value of {@code n} for which all coefficients are
+     * {@code  < Long.MAX_VALUE} is 66. If the computed value exceeds
+     * {@code Long.MAX_VALUE} an {@code ArithMeticException} is
+     * thrown.</li>
+     * </ul></p>
      *
-     * @param a Addend.
-     * @param b Addend.
-     * @param pattern Pattern to use for any thrown exception.
-     * @return the sum {@code a + b}.
-     * @throws MathArithmeticException if the result cannot be represented
-     * as a {@code long}.
-     * @since 1.2
+     * @param n the size of the set
+     * @param k the size of the subsets to be counted
+     * @return {@code n choose k}
+     * @throws MathIllegalArgumentException if preconditions are not met.
+     * @throws MathArithmeticException if the result is too large to be
+     * represented by a long integer.
      */
-     private static long addAndCheck(long a, long b, Localizable pattern) {
-        long ret;
-        if (a > b) {
-            // use symmetry to reduce boundary cases
-            ret = addAndCheck(b, a, pattern);
+    public static long binomialCoefficient(final int n, final int k) {
+        ArithmeticsUtils.checkBinomial(n, k);
+        if ((n == k) || (k == 0)) {
+            return 1;
+        }
+        if ((k == 1) || (k == n - 1)) {
+            return n;
+        }
+        // Use symmetry for large k
+        if (k > n / 2) {
+            return binomialCoefficient(n, n - k);
+        }
+
+        // We use the formula
+        // (n choose k) = n! / (n-k)! / k!
+        // (n choose k) == ((n-k+1)*...*n) / (1*...*k)
+        // which could be written
+        // (n choose k) == (n-1 choose k-1) * n / k
+        long result = 1;
+        if (n <= 61) {
+            // For n <= 61, the naive implementation cannot overflow.
+            int i = n - k + 1;
+            for (int j = 1; j <= k; j++) {
+                result = result * i / j;
+                i++;
+            }
+        } else if (n <= 66) {
+            // For n > 61 but n <= 66, the result cannot overflow,
+            // but we must take care not to overflow intermediate values.
+            int i = n - k + 1;
+            for (int j = 1; j <= k; j++) {
+                // We know that (result * i) is divisible by j,
+                // but (result * i) may overflow, so we split j:
+                // Filter out the gcd, d, so j/d and i/d are integer.
+                // result is divisible by (j/d) because (j/d)
+                // is relative prime to (i/d) and is a divisor of
+                // result * (i/d).
+                final long d = gcd(i, j);
+                result = (result / (j / d)) * (i / d);
+                i++;
+            }
         } else {
-            // assert a <= b
-
-            if (a < 0) {
-                if (b < 0) {
-                    // check for negative overflow
-                    if (Long.MIN_VALUE - b <= a) {
-                        ret = a + b;
-                    } else {
-                        throw new MathArithmeticException(pattern, a, b);
-                    }
-                } else {
-                    // opposite sign addition is always safe
-                    ret = a + b;
-                }
-            } else {
-                // assert a >= 0
-                // assert b >= 0
-
-                // check for positive overflow
-                if (a <= Long.MAX_VALUE - b) {
-                    ret = a + b;
-                } else {
-                    throw new MathArithmeticException(pattern, a, b);
-                }
+            // For n > 66, a result overflow might occur, so we check
+            // the multiplication, taking care to not overflow
+            // unnecessary.
+            int i = n - k + 1;
+            for (int j = 1; j <= k; j++) {
+                final long d = gcd(i, j);
+                result = mulAndCheck(result / (j / d), i / d);
+                i++;
             }
         }
-        return ret;
+        return result;
     }
 
     /**
-     * Subtract two integers, checking for overflow.
+     * Returns a {@code double} representation of the <a
+     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
+     * Coefficient</a>, "{@code n choose k}", the number of
+     * {@code k}-element subsets that can be selected from an
+     * {@code n}-element set.
+     * <p>
+     * <Strong>Preconditions</strong>:
+     * <ul>
+     * <li> {@code 0 <= k <= n } (otherwise
+     * {@code IllegalArgumentException} is thrown)</li>
+     * <li> The result is small enough to fit into a {@code double}. The
+     * largest value of {@code n} for which all coefficients are <
+     * Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE,
+     * Double.POSITIVE_INFINITY is returned</li>
+     * </ul></p>
      *
-     * @param x Minuend.
-     * @param y Subtrahend.
-     * @return the difference {@code x - y}.
-     * @throws MathArithmeticException if the result can not be represented
-     * as an {@code int}.
-     * @since 1.1
+     * @param n the size of the set
+     * @param k the size of the subsets to be counted
+     * @return {@code n choose k}
+     * @throws IllegalArgumentException if preconditions are not met.
      */
-    public static int subAndCheck(int x, int y) {
-        long s = (long)x - (long)y;
-        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
-            throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_SUBTRACTION, x, y);
+    public static double binomialCoefficientDouble(final int n, final int k) {
+        ArithmeticsUtils.checkBinomial(n, k);
+        if ((n == k) || (k == 0)) {
+            return 1d;
         }
-        return (int)s;
+        if ((k == 1) || (k == n - 1)) {
+            return n;
+        }
+        if (k > n/2) {
+            return binomialCoefficientDouble(n, n - k);
+        }
+        if (n < 67) {
+            return binomialCoefficient(n,k);
+        }
+
+        double result = 1d;
+        for (int i = 1; i <= k; i++) {
+             result *= (double)(n - k + i) / (double)i;
+        }
+
+        return FastMath.floor(result + 0.5);
     }
 
     /**
-     * Subtract two long integers, checking for overflow.
+     * Returns the natural {@code log} of the <a
+     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
+     * Coefficient</a>, "{@code n choose k}", the number of
+     * {@code k}-element subsets that can be selected from an
+     * {@code n}-element set.
+     * <p>
+     * <Strong>Preconditions</strong>:
+     * <ul>
+     * <li> {@code 0 <= k <= n } (otherwise
+     * {@code IllegalArgumentException} is thrown)</li>
+     * </ul></p>
      *
-     * @param a Value.
-     * @param b Value.
-     * @return the difference {@code a - b}.
-     * @throws MathArithmeticException if the result can not be represented as a
-     * {@code long}.
-     * @since 1.2
+     * @param n the size of the set
+     * @param k the size of the subsets to be counted
+     * @return {@code n choose k}
+     * @throws IllegalArgumentException if preconditions are not met.
      */
-    public static long subAndCheck(long a, long b) {
-        long ret;
-        if (b == Long.MIN_VALUE) {
-            if (a < 0) {
-                ret = a - b;
-            } else {
-                throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_ADDITION, a, -b);
-            }
-        } else {
-            // use additive inverse
-            ret = addAndCheck(a, -b, LocalizedFormats.OVERFLOW_IN_ADDITION);
+    public static double binomialCoefficientLog(final int n, final int k) {
+        ArithmeticsUtils.checkBinomial(n, k);
+        if ((n == k) || (k == 0)) {
+            return 0;
         }
-        return ret;
+        if ((k == 1) || (k == n - 1)) {
+            return FastMath.log(n);
+        }
+
+        /*
+         * For values small enough to do exact integer computation,
+         * return the log of the exact value
+         */
+        if (n < 67) {
+            return FastMath.log(binomialCoefficient(n,k));
+        }
+
+        /*
+         * Return the log of binomialCoefficientDouble for values that will not
+         * overflow binomialCoefficientDouble
+         */
+        if (n < 1030) {
+            return FastMath.log(binomialCoefficientDouble(n, k));
+        }
+
+        if (k > n / 2) {
+            return binomialCoefficientLog(n, n - k);
+        }
+
+        /*
+         * Sum logs for values that could overflow
+         */
+        double logSum = 0;
+
+        // n!/(n-k)!
+        for (int i = n - k + 1; i <= n; i++) {
+            logSum += FastMath.log(i);
+        }
+
+        // divide by k!
+        for (int i = 2; i <= k; i++) {
+            logSum -= FastMath.log(i);
+        }
+
+        return logSum;
     }
 
     /**
@@ -419,4 +521,251 @@ public final class ArithmeticsUtils {
         } while (t != 0);
         return -u * (1L << k); // gcd is u*2^k
     }
+
+    /**
+     * <p>
+     * Returns the least common multiple of the absolute value of two numbers,
+     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
+     * </p>
+     * Special cases:
+     * <ul>
+     * <li>The invocations {@code lcm(Integer.MIN_VALUE, n)} and
+     * {@code lcm(n, Integer.MIN_VALUE)}, where {@code abs(n)} is a
+     * power of 2, throw an {@code ArithmeticException}, because the result
+     * would be 2^31, which is too large for an int value.</li>
+     * <li>The result of {@code lcm(0, x)} and {@code lcm(x, 0)} is
+     * {@code 0} for any {@code x}.
+     * </ul>
+     *
+     * @param a Number.
+     * @param b Number.
+     * @return the least common multiple, never negative.
+     * @throws MathArithmeticException if the result cannot be represented as
+     * a non-negative {@code int} value.
+     * @since 1.1
+     */
+    public static int lcm(int a, int b) {
+        if (a == 0 || b == 0){
+            return 0;
+        }
+        int lcm = FastMath.abs(ArithmeticsUtils.mulAndCheck(a / gcd(a, b), b));
+        if (lcm == Integer.MIN_VALUE) {
+            throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_32_BITS,
+                                              a, b);
+        }
+        return lcm;
+    }
+
+    /**
+     * <p>
+     * Returns the least common multiple of the absolute value of two numbers,
+     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
+     * </p>
+     * Special cases:
+     * <ul>
+     * <li>The invocations {@code lcm(Long.MIN_VALUE, n)} and
+     * {@code lcm(n, Long.MIN_VALUE)}, where {@code abs(n)} is a
+     * power of 2, throw an {@code ArithmeticException}, because the result
+     * would be 2^63, which is too large for an int value.</li>
+     * <li>The result of {@code lcm(0L, x)} and {@code lcm(x, 0L)} is
+     * {@code 0L} for any {@code x}.
+     * </ul>
+     *
+     * @param a Number.
+     * @param b Number.
+     * @return the least common multiple, never negative.
+     * @throws MathArithmeticException if the result cannot be represented
+     * as a non-negative {@code long} value.
+     * @since 2.1
+     */
+    public static long lcm(long a, long b) {
+        if (a == 0 || b == 0){
+            return 0;
+        }
+        long lcm = FastMath.abs(ArithmeticsUtils.mulAndCheck(a / gcd(a, b), b));
+        if (lcm == Long.MIN_VALUE){
+            throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_64_BITS,
+                                              a, b);
+        }
+        return lcm;
+    }
+
+    /**
+     * Multiply two integers, checking for overflow.
+     *
+     * @param x Factor.
+     * @param y Factor.
+     * @return the product {@code x * y}.
+     * @throws MathArithmeticException if the result can not be
+     * represented as an {@code int}.
+     * @since 1.1
+     */
+    public static int mulAndCheck(int x, int y) {
+        long m = ((long)x) * ((long)y);
+        if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
+            throw new MathArithmeticException();
+        }
+        return (int)m;
+    }
+
+    /**
+     * Multiply two long integers, checking for overflow.
+     *
+     * @param a Factor.
+     * @param b Factor.
+     * @return the product {@code a * b}.
+     * @throws MathArithmeticException if the result can not be represented
+     * as a {@code long}.
+     * @since 1.2
+     */
+    public static long mulAndCheck(long a, long b) {
+        long ret;
+        if (a > b) {
+            // use symmetry to reduce boundary cases
+            ret = mulAndCheck(b, a);
+        } else {
+            if (a < 0) {
+                if (b < 0) {
+                    // check for positive overflow with negative a, negative b
+                    if (a >= Long.MAX_VALUE / b) {
+                        ret = a * b;
+                    } else {
+                        throw new MathArithmeticException();
+                    }
+                } else if (b > 0) {
+                    // check for negative overflow with negative a, positive b
+                    if (Long.MIN_VALUE / b <= a) {
+                        ret = a * b;
+                    } else {
+                        throw new MathArithmeticException();
+
+                    }
+                } else {
+                    // assert b == 0
+                    ret = 0;
+                }
+            } else if (a > 0) {
+                // assert a > 0
+                // assert b > 0
+
+                // check for positive overflow with positive a, positive b
+                if (a <= Long.MAX_VALUE / b) {
+                    ret = a * b;
+                } else {
+                    throw new MathArithmeticException();
+                }
+            } else {
+                // assert a == 0
+                ret = 0;
+            }
+        }
+        return ret;
+    }
+
+    /**
+     * Subtract two integers, checking for overflow.
+     *
+     * @param x Minuend.
+     * @param y Subtrahend.
+     * @return the difference {@code x - y}.
+     * @throws MathArithmeticException if the result can not be represented
+     * as an {@code int}.
+     * @since 1.1
+     */
+    public static int subAndCheck(int x, int y) {
+        long s = (long)x - (long)y;
+        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
+            throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_SUBTRACTION, x, y);
+        }
+        return (int)s;
+    }
+
+    /**
+     * Subtract two long integers, checking for overflow.
+     *
+     * @param a Value.
+     * @param b Value.
+     * @return the difference {@code a - b}.
+     * @throws MathArithmeticException if the result can not be represented as a
+     * {@code long}.
+     * @since 1.2
+     */
+    public static long subAndCheck(long a, long b) {
+        long ret;
+        if (b == Long.MIN_VALUE) {
+            if (a < 0) {
+                ret = a - b;
+            } else {
+                throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_ADDITION, a, -b);
+            }
+        } else {
+            // use additive inverse
+            ret = addAndCheck(a, -b, LocalizedFormats.OVERFLOW_IN_ADDITION);
+        }
+        return ret;
+    }
+
+    /**
+     * Add two long integers, checking for overflow.
+     *
+     * @param a Addend.
+     * @param b Addend.
+     * @param pattern Pattern to use for any thrown exception.
+     * @return the sum {@code a + b}.
+     * @throws MathArithmeticException if the result cannot be represented
+     * as a {@code long}.
+     * @since 1.2
+     */
+     private static long addAndCheck(long a, long b, Localizable pattern) {
+        long ret;
+        if (a > b) {
+            // use symmetry to reduce boundary cases
+            ret = addAndCheck(b, a, pattern);
+        } else {
+            // assert a <= b
+
+            if (a < 0) {
+                if (b < 0) {
+                    // check for negative overflow
+                    if (Long.MIN_VALUE - b <= a) {
+                        ret = a + b;
+                    } else {
+                        throw new MathArithmeticException(pattern, a, b);
+                    }
+                } else {
+                    // opposite sign addition is always safe
+                    ret = a + b;
+                }
+            } else {
+                // assert a >= 0
+                // assert b >= 0
+
+                // check for positive overflow
+                if (a <= Long.MAX_VALUE - b) {
+                    ret = a + b;
+                } else {
+                    throw new MathArithmeticException(pattern, a, b);
+                }
+            }
+        }
+        return ret;
+    }
+
+    /**
+     * Check binomial preconditions.
+     *
+     * @param n Size of the set.
+     * @param k Size of the subsets to be counted.
+     * @throws NotPositiveException if {@code n < 0}.
+     * @throws NumberIsTooLargeException if {@code k > n}.
+     */
+    private static void checkBinomial(final int n, final int k) {
+        if (n < k) {
+            throw new NumberIsTooLargeException(LocalizedFormats.BINOMIAL_INVALID_PARAMETERS_ORDER,
+                                                k, n, true);
+        }
+        if (n < 0) {
+            throw new NotPositiveException(LocalizedFormats.BINOMIAL_NEGATIVE_PARAMETER, n);
+        }
+    }
 }

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java Thu Oct 13 05:29:28 2011
@@ -26,7 +26,6 @@ import org.apache.commons.math.exception
 import org.apache.commons.math.exception.NotFiniteNumberException;
 import org.apache.commons.math.exception.NotPositiveException;
 import org.apache.commons.math.exception.NullArgumentException;
-import org.apache.commons.math.exception.NumberIsTooLargeException;
 import org.apache.commons.math.exception.util.Localizable;
 import org.apache.commons.math.exception.util.LocalizedFormats;
 
@@ -77,214 +76,6 @@ public final class MathUtils {
     }
 
     /**
-     * Returns an exact representation of the <a
-     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
-     * Coefficient</a>, "{@code n choose k}", the number of
-     * {@code k}-element subsets that can be selected from an
-     * {@code n}-element set.
-     * <p>
-     * <Strong>Preconditions</strong>:
-     * <ul>
-     * <li> {@code 0 <= k <= n } (otherwise
-     * {@code IllegalArgumentException} is thrown)</li>
-     * <li> The result is small enough to fit into a {@code long}. The
-     * largest value of {@code n} for which all coefficients are
-     * {@code  < Long.MAX_VALUE} is 66. If the computed value exceeds
-     * {@code Long.MAX_VALUE} an {@code ArithMeticException} is
-     * thrown.</li>
-     * </ul></p>
-     *
-     * @param n the size of the set
-     * @param k the size of the subsets to be counted
-     * @return {@code n choose k}
-     * @throws MathIllegalArgumentException if preconditions are not met.
-     * @throws MathArithmeticException if the result is too large to be
-     * represented by a long integer.
-     */
-    public static long binomialCoefficient(final int n, final int k) {
-        checkBinomial(n, k);
-        if ((n == k) || (k == 0)) {
-            return 1;
-        }
-        if ((k == 1) || (k == n - 1)) {
-            return n;
-        }
-        // Use symmetry for large k
-        if (k > n / 2) {
-            return binomialCoefficient(n, n - k);
-        }
-
-        // We use the formula
-        // (n choose k) = n! / (n-k)! / k!
-        // (n choose k) == ((n-k+1)*...*n) / (1*...*k)
-        // which could be written
-        // (n choose k) == (n-1 choose k-1) * n / k
-        long result = 1;
-        if (n <= 61) {
-            // For n <= 61, the naive implementation cannot overflow.
-            int i = n - k + 1;
-            for (int j = 1; j <= k; j++) {
-                result = result * i / j;
-                i++;
-            }
-        } else if (n <= 66) {
-            // For n > 61 but n <= 66, the result cannot overflow,
-            // but we must take care not to overflow intermediate values.
-            int i = n - k + 1;
-            for (int j = 1; j <= k; j++) {
-                // We know that (result * i) is divisible by j,
-                // but (result * i) may overflow, so we split j:
-                // Filter out the gcd, d, so j/d and i/d are integer.
-                // result is divisible by (j/d) because (j/d)
-                // is relative prime to (i/d) and is a divisor of
-                // result * (i/d).
-                final long d = ArithmeticsUtils.gcd(i, j);
-                result = (result / (j / d)) * (i / d);
-                i++;
-            }
-        } else {
-            // For n > 66, a result overflow might occur, so we check
-            // the multiplication, taking care to not overflow
-            // unnecessary.
-            int i = n - k + 1;
-            for (int j = 1; j <= k; j++) {
-                final long d = ArithmeticsUtils.gcd(i, j);
-                result = mulAndCheck(result / (j / d), i / d);
-                i++;
-            }
-        }
-        return result;
-    }
-
-    /**
-     * Returns a {@code double} representation of the <a
-     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
-     * Coefficient</a>, "{@code n choose k}", the number of
-     * {@code k}-element subsets that can be selected from an
-     * {@code n}-element set.
-     * <p>
-     * <Strong>Preconditions</strong>:
-     * <ul>
-     * <li> {@code 0 <= k <= n } (otherwise
-     * {@code IllegalArgumentException} is thrown)</li>
-     * <li> The result is small enough to fit into a {@code double}. The
-     * largest value of {@code n} for which all coefficients are <
-     * Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE,
-     * Double.POSITIVE_INFINITY is returned</li>
-     * </ul></p>
-     *
-     * @param n the size of the set
-     * @param k the size of the subsets to be counted
-     * @return {@code n choose k}
-     * @throws IllegalArgumentException if preconditions are not met.
-     */
-    public static double binomialCoefficientDouble(final int n, final int k) {
-        checkBinomial(n, k);
-        if ((n == k) || (k == 0)) {
-            return 1d;
-        }
-        if ((k == 1) || (k == n - 1)) {
-            return n;
-        }
-        if (k > n/2) {
-            return binomialCoefficientDouble(n, n - k);
-        }
-        if (n < 67) {
-            return binomialCoefficient(n,k);
-        }
-
-        double result = 1d;
-        for (int i = 1; i <= k; i++) {
-             result *= (double)(n - k + i) / (double)i;
-        }
-
-        return FastMath.floor(result + 0.5);
-    }
-
-    /**
-     * Returns the natural {@code log} of the <a
-     * href="http://mathworld.wolfram.com/BinomialCoefficient.html"> Binomial
-     * Coefficient</a>, "{@code n choose k}", the number of
-     * {@code k}-element subsets that can be selected from an
-     * {@code n}-element set.
-     * <p>
-     * <Strong>Preconditions</strong>:
-     * <ul>
-     * <li> {@code 0 <= k <= n } (otherwise
-     * {@code IllegalArgumentException} is thrown)</li>
-     * </ul></p>
-     *
-     * @param n the size of the set
-     * @param k the size of the subsets to be counted
-     * @return {@code n choose k}
-     * @throws IllegalArgumentException if preconditions are not met.
-     */
-    public static double binomialCoefficientLog(final int n, final int k) {
-        checkBinomial(n, k);
-        if ((n == k) || (k == 0)) {
-            return 0;
-        }
-        if ((k == 1) || (k == n - 1)) {
-            return FastMath.log(n);
-        }
-
-        /*
-         * For values small enough to do exact integer computation,
-         * return the log of the exact value
-         */
-        if (n < 67) {
-            return FastMath.log(binomialCoefficient(n,k));
-        }
-
-        /*
-         * Return the log of binomialCoefficientDouble for values that will not
-         * overflow binomialCoefficientDouble
-         */
-        if (n < 1030) {
-            return FastMath.log(binomialCoefficientDouble(n, k));
-        }
-
-        if (k > n / 2) {
-            return binomialCoefficientLog(n, n - k);
-        }
-
-        /*
-         * Sum logs for values that could overflow
-         */
-        double logSum = 0;
-
-        // n!/(n-k)!
-        for (int i = n - k + 1; i <= n; i++) {
-            logSum += FastMath.log(i);
-        }
-
-        // divide by k!
-        for (int i = 2; i <= k; i++) {
-            logSum -= FastMath.log(i);
-        }
-
-        return logSum;
-    }
-
-    /**
-     * Check binomial preconditions.
-     *
-     * @param n Size of the set.
-     * @param k Size of the subsets to be counted.
-     * @throws NotPositiveException if {@code n < 0}.
-     * @throws NumberIsTooLargeException if {@code k > n}.
-     */
-    private static void checkBinomial(final int n, final int k) {
-        if (n < k) {
-            throw new NumberIsTooLargeException(LocalizedFormats.BINOMIAL_INVALID_PARAMETERS_ORDER,
-                                                k, n, true);
-        }
-        if (n < 0) {
-            throw new NotPositiveException(LocalizedFormats.BINOMIAL_NEGATIVE_PARAMETER, n);
-        }
-    }
-
-    /**
      * Returns the <a href="http://mathworld.wolfram.com/HyperbolicCosine.html">
      * hyperbolic cosine</a> of x.
      *
@@ -388,74 +179,6 @@ public final class MathUtils {
     }
 
     /**
-     * <p>
-     * Returns the least common multiple of the absolute value of two numbers,
-     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
-     * </p>
-     * Special cases:
-     * <ul>
-     * <li>The invocations {@code lcm(Integer.MIN_VALUE, n)} and
-     * {@code lcm(n, Integer.MIN_VALUE)}, where {@code abs(n)} is a
-     * power of 2, throw an {@code ArithmeticException}, because the result
-     * would be 2^31, which is too large for an int value.</li>
-     * <li>The result of {@code lcm(0, x)} and {@code lcm(x, 0)} is
-     * {@code 0} for any {@code x}.
-     * </ul>
-     *
-     * @param a Number.
-     * @param b Number.
-     * @return the least common multiple, never negative.
-     * @throws MathArithmeticException if the result cannot be represented as
-     * a non-negative {@code int} value.
-     * @since 1.1
-     */
-    public static int lcm(int a, int b) {
-        if (a == 0 || b == 0){
-            return 0;
-        }
-        int lcm = FastMath.abs(mulAndCheck(a / ArithmeticsUtils.gcd(a, b), b));
-        if (lcm == Integer.MIN_VALUE) {
-            throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_32_BITS,
-                                              a, b);
-        }
-        return lcm;
-    }
-
-    /**
-     * <p>
-     * Returns the least common multiple of the absolute value of two numbers,
-     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
-     * </p>
-     * Special cases:
-     * <ul>
-     * <li>The invocations {@code lcm(Long.MIN_VALUE, n)} and
-     * {@code lcm(n, Long.MIN_VALUE)}, where {@code abs(n)} is a
-     * power of 2, throw an {@code ArithmeticException}, because the result
-     * would be 2^63, which is too large for an int value.</li>
-     * <li>The result of {@code lcm(0L, x)} and {@code lcm(x, 0L)} is
-     * {@code 0L} for any {@code x}.
-     * </ul>
-     *
-     * @param a Number.
-     * @param b Number.
-     * @return the least common multiple, never negative.
-     * @throws MathArithmeticException if the result cannot be represented
-     * as a non-negative {@code long} value.
-     * @since 2.1
-     */
-    public static long lcm(long a, long b) {
-        if (a == 0 || b == 0){
-            return 0;
-        }
-        long lcm = FastMath.abs(mulAndCheck(a / ArithmeticsUtils.gcd(a, b), b));
-        if (lcm == Long.MIN_VALUE){
-            throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_64_BITS,
-                                              a, b);
-        }
-        return lcm;
-    }
-
-    /**
      * <p>Returns the
      * <a href="http://mathworld.wolfram.com/Logarithm.html">logarithm</a>
      * for base {@code b} of {@code x}.
@@ -476,78 +199,6 @@ public final class MathUtils {
     }
 
     /**
-     * Multiply two integers, checking for overflow.
-     *
-     * @param x Factor.
-     * @param y Factor.
-     * @return the product {@code x * y}.
-     * @throws MathArithmeticException if the result can not be
-     * represented as an {@code int}.
-     * @since 1.1
-     */
-    public static int mulAndCheck(int x, int y) {
-        long m = ((long)x) * ((long)y);
-        if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
-            throw new MathArithmeticException();
-        }
-        return (int)m;
-    }
-
-    /**
-     * Multiply two long integers, checking for overflow.
-     *
-     * @param a Factor.
-     * @param b Factor.
-     * @return the product {@code a * b}.
-     * @throws MathArithmeticException if the result can not be represented
-     * as a {@code long}.
-     * @since 1.2
-     */
-    public static long mulAndCheck(long a, long b) {
-        long ret;
-        if (a > b) {
-            // use symmetry to reduce boundary cases
-            ret = mulAndCheck(b, a);
-        } else {
-            if (a < 0) {
-                if (b < 0) {
-                    // check for positive overflow with negative a, negative b
-                    if (a >= Long.MAX_VALUE / b) {
-                        ret = a * b;
-                    } else {
-                        throw new MathArithmeticException();
-                    }
-                } else if (b > 0) {
-                    // check for negative overflow with negative a, positive b
-                    if (Long.MIN_VALUE / b <= a) {
-                        ret = a * b;
-                    } else {
-                        throw new MathArithmeticException();
-
-                    }
-                } else {
-                    // assert b == 0
-                    ret = 0;
-                }
-            } else if (a > 0) {
-                // assert a > 0
-                // assert b > 0
-
-                // check for positive overflow with positive a, positive b
-                if (a <= Long.MAX_VALUE / b) {
-                    ret = a * b;
-                } else {
-                    throw new MathArithmeticException();
-                }
-            } else {
-                // assert a == 0
-                ret = 0;
-            }
-        }
-        return ret;
-    }
-
-    /**
      * Normalize an angle in a 2&pi wide interval around a center value.
      * <p>This method has three main uses:</p>
      * <ul>

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/analysis/polynomials/PolynomialsUtilsTest.java Thu Oct 13 05:29:28 2011
@@ -18,8 +18,8 @@ package org.apache.commons.math.analysis
 
 import org.apache.commons.math.analysis.UnivariateRealFunction;
 import org.apache.commons.math.analysis.integration.LegendreGaussIntegrator;
+import org.apache.commons.math.util.ArithmeticsUtils;
 import org.apache.commons.math.util.FastMath;
-import org.apache.commons.math.util.MathUtils;
 import org.apache.commons.math.util.Precision;
 import org.junit.Assert;
 import org.junit.Test;
@@ -289,7 +289,7 @@ public class PolynomialsUtilsTest {
             for (int w = 0; w < 10; ++w) {
                 for (int i = 0; i < 10; ++i) {
                     PolynomialFunction jacobi = PolynomialsUtils.createJacobiPolynomial(i, v, w);
-                    double binomial = MathUtils.binomialCoefficient(v + i, i);
+                    double binomial = ArithmeticsUtils.binomialCoefficient(v + i, i);
                     Assert.assertTrue(Precision.equals(binomial, jacobi.value(1.0), 1));
                 }
             }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/linear/InverseHilbertMatrix.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/linear/InverseHilbertMatrix.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/linear/InverseHilbertMatrix.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/linear/InverseHilbertMatrix.java Thu Oct 13 05:29:28 2011
@@ -17,7 +17,7 @@
 package org.apache.commons.math.linear;
 
 import org.apache.commons.math.exception.DimensionMismatchException;
-import org.apache.commons.math.util.MathUtils;
+import org.apache.commons.math.util.ArithmeticsUtils;
 
 /**
  * This class implements inverses of Hilbert Matrices as
@@ -54,13 +54,13 @@ public class InverseHilbertMatrix
      */
     public long getEntry(final int i, final int j) {
         long val = i + j + 1;
-        long aux = MathUtils.binomialCoefficient(n + i, n - j - 1);
-        val = MathUtils.mulAndCheck(val, aux);
-        aux = MathUtils.binomialCoefficient(n + j, n - i - 1);
-        val = MathUtils.mulAndCheck(val, aux);
-        aux = MathUtils.binomialCoefficient(i + j, i);
-        val = MathUtils.mulAndCheck(val, aux);
-        val = MathUtils.mulAndCheck(val, aux);
+        long aux = ArithmeticsUtils.binomialCoefficient(n + i, n - j - 1);
+        val = ArithmeticsUtils.mulAndCheck(val, aux);
+        aux = ArithmeticsUtils.binomialCoefficient(n + j, n - i - 1);
+        val = ArithmeticsUtils.mulAndCheck(val, aux);
+        aux = ArithmeticsUtils.binomialCoefficient(i + j, i);
+        val = ArithmeticsUtils.mulAndCheck(val, aux);
+        val = ArithmeticsUtils.mulAndCheck(val, aux);
         return ((i + j) & 1) == 0 ? val : -val;
     }
 

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/ArithmeticsUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/ArithmeticsUtilsTest.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/ArithmeticsUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/ArithmeticsUtilsTest.java Thu Oct 13 05:29:28 2011
@@ -17,6 +17,9 @@
 package org.apache.commons.math.util;
 
 import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
 
 import org.apache.commons.math.exception.MathArithmeticException;
 import org.apache.commons.math.exception.MathIllegalArgumentException;
@@ -30,15 +33,16 @@ import org.junit.Test;
  * @version $Id$
  */
 public class ArithmeticsUtilsTest {
-    /**
-     * Exact direct multiplication implementation to test against
-     */
-    private long factorial(int n) {
-        long result = 1;
-        for (int i = 2; i <= n; i++) {
-            result *= i;
-        }
-        return result;
+
+    /** cached binomial coefficients */
+    private static final List<Map<Integer, Long>> binomialCache = new ArrayList<Map<Integer, Long>>();
+
+    /** Verify that b(0,0) = 1 */
+    @Test
+    public void test0Choose0() {
+        Assert.assertEquals(ArithmeticsUtils.binomialCoefficientDouble(0, 0), 1d, 0);
+        Assert.assertEquals(ArithmeticsUtils.binomialCoefficientLog(0, 0), 0d, 0);
+        Assert.assertEquals(ArithmeticsUtils.binomialCoefficient(0, 0), 1);
     }
 
     @Test
@@ -58,7 +62,6 @@ public class ArithmeticsUtilsTest {
         }
     }
 
-
     @Test
     public void testAddAndCheckLong() {
         long max = Long.MAX_VALUE;
@@ -77,69 +80,170 @@ public class ArithmeticsUtilsTest {
         testAddAndCheckLongFailure(-1L, min);
     }
 
-    private void testAddAndCheckLongFailure(long a, long b) {
-        try {
-            ArithmeticsUtils.addAndCheck(a, b);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-            // success
+
+    @Test
+    public void testBinomialCoefficient() {
+        long[] bcoef5 = {
+            1,
+            5,
+            10,
+            10,
+            5,
+            1 };
+        long[] bcoef6 = {
+            1,
+            6,
+            15,
+            20,
+            15,
+            6,
+            1 };
+        for (int i = 0; i < 6; i++) {
+            Assert.assertEquals("5 choose " + i, bcoef5[i], ArithmeticsUtils.binomialCoefficient(5, i));
+        }
+        for (int i = 0; i < 7; i++) {
+            Assert.assertEquals("6 choose " + i, bcoef6[i], ArithmeticsUtils.binomialCoefficient(6, i));
+        }
+
+        for (int n = 1; n < 10; n++) {
+            for (int k = 0; k <= n; k++) {
+                Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), ArithmeticsUtils.binomialCoefficient(n, k));
+                Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), ArithmeticsUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE);
+                Assert.assertEquals(n + " choose " + k, FastMath.log(binomialCoefficient(n, k)), ArithmeticsUtils.binomialCoefficientLog(n, k), 10E-12);
+            }
+        }
+
+        int[] n = { 34, 66, 100, 1500, 1500 };
+        int[] k = { 17, 33, 10, 1500 - 4, 4 };
+        for (int i = 0; i < n.length; i++) {
+            long expected = binomialCoefficient(n[i], k[i]);
+            Assert.assertEquals(n[i] + " choose " + k[i], expected,
+                ArithmeticsUtils.binomialCoefficient(n[i], k[i]));
+            Assert.assertEquals(n[i] + " choose " + k[i], expected,
+                ArithmeticsUtils.binomialCoefficientDouble(n[i], k[i]), 0.0);
+            Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", FastMath.log(expected),
+                ArithmeticsUtils.binomialCoefficientLog(n[i], k[i]), 0.0);
         }
     }
 
     @Test
-    public void testSubAndCheck() {
-        int big = Integer.MAX_VALUE;
-        int bigNeg = Integer.MIN_VALUE;
-        Assert.assertEquals(big, ArithmeticsUtils.subAndCheck(big, 0));
-        Assert.assertEquals(bigNeg + 1, ArithmeticsUtils.subAndCheck(bigNeg, -1));
-        Assert.assertEquals(-1, ArithmeticsUtils.subAndCheck(bigNeg, -big));
+    public void testBinomialCoefficientFail() {
         try {
-            ArithmeticsUtils.subAndCheck(big, -1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
+            ArithmeticsUtils.binomialCoefficient(4, 5);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
         }
+
         try {
-            ArithmeticsUtils.subAndCheck(bigNeg, 1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
+            ArithmeticsUtils.binomialCoefficientDouble(4, 5);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
         }
-    }
 
-    @Test
-    public void testSubAndCheckErrorMessage() {
-        int big = Integer.MAX_VALUE;
         try {
-            ArithmeticsUtils.subAndCheck(big, -1);
-            Assert.fail("Expecting MathArithmeticException");
+            ArithmeticsUtils.binomialCoefficientLog(4, 5);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
+        }
+
+        try {
+            ArithmeticsUtils.binomialCoefficient(-1, -2);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
+        }
+        try {
+            ArithmeticsUtils.binomialCoefficientDouble(-1, -2);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
+        }
+        try {
+            ArithmeticsUtils.binomialCoefficientLog(-1, -2);
+            Assert.fail("expecting MathIllegalArgumentException");
+        } catch (MathIllegalArgumentException ex) {
+            // ignored
+        }
+
+        try {
+            ArithmeticsUtils.binomialCoefficient(67, 30);
+            Assert.fail("expecting MathArithmeticException");
         } catch (MathArithmeticException ex) {
-            Assert.assertTrue(ex.getMessage().length() > 1);
+            // ignored
         }
+        try {
+            ArithmeticsUtils.binomialCoefficient(67, 34);
+            Assert.fail("expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+            // ignored
+        }
+        double x = ArithmeticsUtils.binomialCoefficientDouble(1030, 515);
+        Assert.assertTrue("expecting infinite binomial coefficient", Double
+            .isInfinite(x));
     }
 
+    /**
+     * Tests correctness for large n and sharpness of upper bound in API doc
+     * JIRA: MATH-241
+     */
     @Test
-    public void testSubAndCheckLong() {
-        long max = Long.MAX_VALUE;
-        long min = Long.MIN_VALUE;
-        Assert.assertEquals(max, ArithmeticsUtils.subAndCheck(max, 0));
-        Assert.assertEquals(min, ArithmeticsUtils.subAndCheck(min, 0));
-        Assert.assertEquals(-max, ArithmeticsUtils.subAndCheck(0, max));
-        Assert.assertEquals(min + 1, ArithmeticsUtils.subAndCheck(min, -1));
-        // min == -1-max
-        Assert.assertEquals(-1, ArithmeticsUtils.subAndCheck(-max - 1, -max));
-        Assert.assertEquals(max, ArithmeticsUtils.subAndCheck(-1, -1 - max));
-        testSubAndCheckLongFailure(0L, min);
-        testSubAndCheckLongFailure(max, -1L);
-        testSubAndCheckLongFailure(min, 1L);
-    }
+    public void testBinomialCoefficientLarge() throws Exception {
+        // This tests all legal and illegal values for n <= 200.
+        for (int n = 0; n <= 200; n++) {
+            for (int k = 0; k <= n; k++) {
+                long ourResult = -1;
+                long exactResult = -1;
+                boolean shouldThrow = false;
+                boolean didThrow = false;
+                try {
+                    ourResult = ArithmeticsUtils.binomialCoefficient(n, k);
+                } catch (MathArithmeticException ex) {
+                    didThrow = true;
+                }
+                try {
+                    exactResult = binomialCoefficient(n, k);
+                } catch (MathArithmeticException ex) {
+                    shouldThrow = true;
+                }
+                Assert.assertEquals(n + " choose " + k, exactResult, ourResult);
+                Assert.assertEquals(n + " choose " + k, shouldThrow, didThrow);
+                Assert.assertTrue(n + " choose " + k, (n > 66 || !didThrow));
+
+                if (!shouldThrow && exactResult > 1) {
+                    Assert.assertEquals(n + " choose " + k, 1.,
+                        ArithmeticsUtils.binomialCoefficientDouble(n, k) / exactResult, 1e-10);
+                    Assert.assertEquals(n + " choose " + k, 1,
+                        ArithmeticsUtils.binomialCoefficientLog(n, k) / FastMath.log(exactResult), 1e-10);
+                }
+            }
+        }
+
+        long ourResult = ArithmeticsUtils.binomialCoefficient(300, 3);
+        long exactResult = binomialCoefficient(300, 3);
+        Assert.assertEquals(exactResult, ourResult);
+
+        ourResult = ArithmeticsUtils.binomialCoefficient(700, 697);
+        exactResult = binomialCoefficient(700, 697);
+        Assert.assertEquals(exactResult, ourResult);
 
-    private void testSubAndCheckLongFailure(long a, long b) {
+        // This one should throw
         try {
-            ArithmeticsUtils.subAndCheck(a, b);
+            ArithmeticsUtils.binomialCoefficient(700, 300);
             Assert.fail("Expecting MathArithmeticException");
         } catch (MathArithmeticException ex) {
-            // success
+            // Expected
         }
 
+        int n = 10000;
+        ourResult = ArithmeticsUtils.binomialCoefficient(n, 3);
+        exactResult = binomialCoefficient(n, 3);
+        Assert.assertEquals(exactResult, ourResult);
+        Assert.assertEquals(1, ArithmeticsUtils.binomialCoefficientDouble(n, 3) / exactResult, 1e-10);
+        Assert.assertEquals(1, ArithmeticsUtils.binomialCoefficientLog(n, 3) / FastMath.log(exactResult), 1e-10);
+
     }
 
     @Test
@@ -184,7 +288,6 @@ public class ArithmeticsUtilsTest {
         Assert.assertTrue("expecting infinite factorial value", Double.isInfinite(ArithmeticsUtils.factorialDouble(171)));
     }
 
-
     @Test
     public void testGcd() {
         int a = 30;
@@ -237,6 +340,30 @@ public class ArithmeticsUtilsTest {
     }
 
     @Test
+    public void testGcdConsistency() {
+        int[] primeList = {19, 23, 53, 67, 73, 79, 101, 103, 111, 131};
+        ArrayList<Integer> primes = new ArrayList<Integer>();
+        for (int i = 0; i < primeList.length; i++) {
+            primes.add(Integer.valueOf(primeList[i]));
+        }
+        RandomDataImpl randomData = new RandomDataImpl();
+        for (int i = 0; i < 20; i++) {
+            Object[] sample = randomData.nextSample(primes, 4);
+            int p1 = ((Integer) sample[0]).intValue();
+            int p2 = ((Integer) sample[1]).intValue();
+            int p3 = ((Integer) sample[2]).intValue();
+            int p4 = ((Integer) sample[3]).intValue();
+            int i1 = p1 * p2 * p3;
+            int i2 = p1 * p2 * p4;
+            int gcd = p1 * p2;
+            Assert.assertEquals(gcd, ArithmeticsUtils.gcd(i1, i2));
+            long l1 = i1;
+            long l2 = i2;
+            Assert.assertEquals(gcd, ArithmeticsUtils.gcd(l1, l2));
+        }
+    }
+
+    @Test
     public void  testGcdLong(){
         long a = 30;
         long b = 50;
@@ -289,27 +416,262 @@ public class ArithmeticsUtilsTest {
         }
     }
 
+
     @Test
-    public void testGcdConsistency() {
-        int[] primeList = {19, 23, 53, 67, 73, 79, 101, 103, 111, 131};
-        ArrayList<Integer> primes = new ArrayList<Integer>();
-        for (int i = 0; i < primeList.length; i++) {
-            primes.add(Integer.valueOf(primeList[i]));
+    public void testLcm() {
+        int a = 30;
+        int b = 50;
+        int c = 77;
+
+        Assert.assertEquals(0, ArithmeticsUtils.lcm(0, b));
+        Assert.assertEquals(0, ArithmeticsUtils.lcm(a, 0));
+        Assert.assertEquals(b, ArithmeticsUtils.lcm(1, b));
+        Assert.assertEquals(a, ArithmeticsUtils.lcm(a, 1));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(a, b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(-a, b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(a, -b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(-a, -b));
+        Assert.assertEquals(2310, ArithmeticsUtils.lcm(a, c));
+
+        // Assert that no intermediate value overflows:
+        // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
+        Assert.assertEquals((1<<20)*15, ArithmeticsUtils.lcm((1<<20)*3, (1<<20)*5));
+
+        // Special case
+        Assert.assertEquals(0, ArithmeticsUtils.lcm(0, 0));
+
+        try {
+            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+            ArithmeticsUtils.lcm(Integer.MIN_VALUE, 1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
         }
-        RandomDataImpl randomData = new RandomDataImpl();
-        for (int i = 0; i < 20; i++) {
-            Object[] sample = randomData.nextSample(primes, 4);
-            int p1 = ((Integer) sample[0]).intValue();
-            int p2 = ((Integer) sample[1]).intValue();
-            int p3 = ((Integer) sample[2]).intValue();
-            int p4 = ((Integer) sample[3]).intValue();
-            int i1 = p1 * p2 * p3;
-            int i2 = p1 * p2 * p4;
-            int gcd = p1 * p2;
-            Assert.assertEquals(gcd, ArithmeticsUtils.gcd(i1, i2));
-            long l1 = i1;
-            long l2 = i2;
-            Assert.assertEquals(gcd, ArithmeticsUtils.gcd(l1, l2));
+
+        try {
+            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+            ArithmeticsUtils.lcm(Integer.MIN_VALUE, 1<<20);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
+        }
+
+        try {
+            ArithmeticsUtils.lcm(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
+        }
+    }
+
+    @Test
+    public void testLcmLong() {
+        long a = 30;
+        long b = 50;
+        long c = 77;
+
+        Assert.assertEquals(0, ArithmeticsUtils.lcm(0, b));
+        Assert.assertEquals(0, ArithmeticsUtils.lcm(a, 0));
+        Assert.assertEquals(b, ArithmeticsUtils.lcm(1, b));
+        Assert.assertEquals(a, ArithmeticsUtils.lcm(a, 1));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(a, b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(-a, b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(a, -b));
+        Assert.assertEquals(150, ArithmeticsUtils.lcm(-a, -b));
+        Assert.assertEquals(2310, ArithmeticsUtils.lcm(a, c));
+
+        Assert.assertEquals(Long.MAX_VALUE, ArithmeticsUtils.lcm(60247241209L, 153092023L));
+
+        // Assert that no intermediate value overflows:
+        // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
+        Assert.assertEquals((1L<<50)*15, ArithmeticsUtils.lcm((1L<<45)*3, (1L<<50)*5));
+
+        // Special case
+        Assert.assertEquals(0L, ArithmeticsUtils.lcm(0L, 0L));
+
+        try {
+            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+            ArithmeticsUtils.lcm(Long.MIN_VALUE, 1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
+        }
+
+        try {
+            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+            ArithmeticsUtils.lcm(Long.MIN_VALUE, 1<<20);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
+        }
+
+        Assert.assertEquals((long) Integer.MAX_VALUE * (Integer.MAX_VALUE - 1),
+            ArithmeticsUtils.lcm((long)Integer.MAX_VALUE, Integer.MAX_VALUE - 1));
+        try {
+            ArithmeticsUtils.lcm(Long.MAX_VALUE, Long.MAX_VALUE - 1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException expected) {
+            // expected
+        }
+    }
+
+    @Test
+    public void testMulAndCheck() {
+        int big = Integer.MAX_VALUE;
+        int bigNeg = Integer.MIN_VALUE;
+        Assert.assertEquals(big, ArithmeticsUtils.mulAndCheck(big, 1));
+        try {
+            ArithmeticsUtils.mulAndCheck(big, 2);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+        }
+        try {
+            ArithmeticsUtils.mulAndCheck(bigNeg, 2);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+        }
+    }
+
+    @Test
+    public void testMulAndCheckLong() {
+        long max = Long.MAX_VALUE;
+        long min = Long.MIN_VALUE;
+        Assert.assertEquals(max, ArithmeticsUtils.mulAndCheck(max, 1L));
+        Assert.assertEquals(min, ArithmeticsUtils.mulAndCheck(min, 1L));
+        Assert.assertEquals(0L, ArithmeticsUtils.mulAndCheck(max, 0L));
+        Assert.assertEquals(0L, ArithmeticsUtils.mulAndCheck(min, 0L));
+        Assert.assertEquals(max, ArithmeticsUtils.mulAndCheck(1L, max));
+        Assert.assertEquals(min, ArithmeticsUtils.mulAndCheck(1L, min));
+        Assert.assertEquals(0L, ArithmeticsUtils.mulAndCheck(0L, max));
+        Assert.assertEquals(0L, ArithmeticsUtils.mulAndCheck(0L, min));
+        Assert.assertEquals(1L, ArithmeticsUtils.mulAndCheck(-1L, -1L));
+        Assert.assertEquals(min, ArithmeticsUtils.mulAndCheck(min / 2, 2));
+        testMulAndCheckLongFailure(max, 2L);
+        testMulAndCheckLongFailure(2L, max);
+        testMulAndCheckLongFailure(min, 2L);
+        testMulAndCheckLongFailure(2L, min);
+        testMulAndCheckLongFailure(min, -1L);
+        testMulAndCheckLongFailure(-1L, min);
+    }
+
+    @Test
+    public void testSubAndCheck() {
+        int big = Integer.MAX_VALUE;
+        int bigNeg = Integer.MIN_VALUE;
+        Assert.assertEquals(big, ArithmeticsUtils.subAndCheck(big, 0));
+        Assert.assertEquals(bigNeg + 1, ArithmeticsUtils.subAndCheck(bigNeg, -1));
+        Assert.assertEquals(-1, ArithmeticsUtils.subAndCheck(bigNeg, -big));
+        try {
+            ArithmeticsUtils.subAndCheck(big, -1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+        }
+        try {
+            ArithmeticsUtils.subAndCheck(bigNeg, 1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+        }
+    }
+
+    @Test
+    public void testSubAndCheckErrorMessage() {
+        int big = Integer.MAX_VALUE;
+        try {
+            ArithmeticsUtils.subAndCheck(big, -1);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+            Assert.assertTrue(ex.getMessage().length() > 1);
+        }
+    }
+
+    @Test
+    public void testSubAndCheckLong() {
+        long max = Long.MAX_VALUE;
+        long min = Long.MIN_VALUE;
+        Assert.assertEquals(max, ArithmeticsUtils.subAndCheck(max, 0));
+        Assert.assertEquals(min, ArithmeticsUtils.subAndCheck(min, 0));
+        Assert.assertEquals(-max, ArithmeticsUtils.subAndCheck(0, max));
+        Assert.assertEquals(min + 1, ArithmeticsUtils.subAndCheck(min, -1));
+        // min == -1-max
+        Assert.assertEquals(-1, ArithmeticsUtils.subAndCheck(-max - 1, -max));
+        Assert.assertEquals(max, ArithmeticsUtils.subAndCheck(-1, -1 - max));
+        testSubAndCheckLongFailure(0L, min);
+        testSubAndCheckLongFailure(max, -1L);
+        testSubAndCheckLongFailure(min, 1L);
+    }
+
+    /**
+     * Exact (caching) recursive implementation to test against
+     */
+    private long binomialCoefficient(int n, int k) throws MathArithmeticException {
+        if (binomialCache.size() > n) {
+            Long cachedResult = binomialCache.get(n).get(Integer.valueOf(k));
+            if (cachedResult != null) {
+                return cachedResult.longValue();
+            }
+        }
+        long result = -1;
+        if ((n == k) || (k == 0)) {
+            result = 1;
+        } else if ((k == 1) || (k == n - 1)) {
+            result = n;
+        } else {
+            // Reduce stack depth for larger values of n
+            if (k < n - 100) {
+                binomialCoefficient(n - 100, k);
+            }
+            if (k > 100) {
+                binomialCoefficient(n - 100, k - 100);
+            }
+            result = ArithmeticsUtils.addAndCheck(binomialCoefficient(n - 1, k - 1),
+                binomialCoefficient(n - 1, k));
+        }
+        if (result == -1) {
+            throw new MathArithmeticException();
+        }
+        for (int i = binomialCache.size(); i < n + 1; i++) {
+            binomialCache.add(new HashMap<Integer, Long>());
+        }
+        binomialCache.get(n).put(Integer.valueOf(k), Long.valueOf(result));
+        return result;
+    }
+
+    /**
+     * Exact direct multiplication implementation to test against
+     */
+    private long factorial(int n) {
+        long result = 1;
+        for (int i = 2; i <= n; i++) {
+            result *= i;
         }
+        return result;
+    }
+
+    private void testAddAndCheckLongFailure(long a, long b) {
+        try {
+            ArithmeticsUtils.addAndCheck(a, b);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+            // success
+        }
+    }
+
+    private void testMulAndCheckLongFailure(long a, long b) {
+        try {
+            ArithmeticsUtils.mulAndCheck(a, b);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+            // success
+        }
+    }
+
+    private void testSubAndCheckLongFailure(long a, long b) {
+        try {
+            ArithmeticsUtils.subAndCheck(a, b);
+            Assert.fail("Expecting MathArithmeticException");
+        } catch (MathArithmeticException ex) {
+            // success
+        }
+
     }
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java?rev=1182658&r1=1182657&r2=1182658&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java Thu Oct 13 05:29:28 2011
@@ -15,11 +15,6 @@ package org.apache.commons.math.util;
 
 import java.math.BigDecimal;
 import java.math.BigInteger;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
 
 
 import org.apache.commons.math.TestUtils;
@@ -38,219 +33,6 @@ import org.junit.Test;
  *          2007) $
  */
 public final class MathUtilsTest {
-
-    /** cached binomial coefficients */
-    private static final List<Map<Integer, Long>> binomialCache = new ArrayList<Map<Integer, Long>>();
-
-    /**
-     * Exact (caching) recursive implementation to test against
-     */
-    private long binomialCoefficient(int n, int k) throws MathArithmeticException {
-        if (binomialCache.size() > n) {
-            Long cachedResult = binomialCache.get(n).get(Integer.valueOf(k));
-            if (cachedResult != null) {
-                return cachedResult.longValue();
-            }
-        }
-        long result = -1;
-        if ((n == k) || (k == 0)) {
-            result = 1;
-        } else if ((k == 1) || (k == n - 1)) {
-            result = n;
-        } else {
-            // Reduce stack depth for larger values of n
-            if (k < n - 100) {
-                binomialCoefficient(n - 100, k);
-            }
-            if (k > 100) {
-                binomialCoefficient(n - 100, k - 100);
-            }
-            result = ArithmeticsUtils.addAndCheck(binomialCoefficient(n - 1, k - 1),
-                binomialCoefficient(n - 1, k));
-        }
-        if (result == -1) {
-            throw new MathArithmeticException();
-        }
-        for (int i = binomialCache.size(); i < n + 1; i++) {
-            binomialCache.add(new HashMap<Integer, Long>());
-        }
-        binomialCache.get(n).put(Integer.valueOf(k), Long.valueOf(result));
-        return result;
-    }
-
-    /** Verify that b(0,0) = 1 */
-    @Test
-    public void test0Choose0() {
-        Assert.assertEquals(MathUtils.binomialCoefficientDouble(0, 0), 1d, 0);
-        Assert.assertEquals(MathUtils.binomialCoefficientLog(0, 0), 0d, 0);
-        Assert.assertEquals(MathUtils.binomialCoefficient(0, 0), 1);
-    }
-
-    @Test
-    public void testBinomialCoefficient() {
-        long[] bcoef5 = {
-            1,
-            5,
-            10,
-            10,
-            5,
-            1 };
-        long[] bcoef6 = {
-            1,
-            6,
-            15,
-            20,
-            15,
-            6,
-            1 };
-        for (int i = 0; i < 6; i++) {
-            Assert.assertEquals("5 choose " + i, bcoef5[i], MathUtils.binomialCoefficient(5, i));
-        }
-        for (int i = 0; i < 7; i++) {
-            Assert.assertEquals("6 choose " + i, bcoef6[i], MathUtils.binomialCoefficient(6, i));
-        }
-
-        for (int n = 1; n < 10; n++) {
-            for (int k = 0; k <= n; k++) {
-                Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), MathUtils.binomialCoefficient(n, k));
-                Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), MathUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE);
-                Assert.assertEquals(n + " choose " + k, FastMath.log(binomialCoefficient(n, k)), MathUtils.binomialCoefficientLog(n, k), 10E-12);
-            }
-        }
-
-        int[] n = { 34, 66, 100, 1500, 1500 };
-        int[] k = { 17, 33, 10, 1500 - 4, 4 };
-        for (int i = 0; i < n.length; i++) {
-            long expected = binomialCoefficient(n[i], k[i]);
-            Assert.assertEquals(n[i] + " choose " + k[i], expected,
-                MathUtils.binomialCoefficient(n[i], k[i]));
-            Assert.assertEquals(n[i] + " choose " + k[i], expected,
-                MathUtils.binomialCoefficientDouble(n[i], k[i]), 0.0);
-            Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", FastMath.log(expected),
-                MathUtils.binomialCoefficientLog(n[i], k[i]), 0.0);
-        }
-    }
-
-    /**
-     * Tests correctness for large n and sharpness of upper bound in API doc
-     * JIRA: MATH-241
-     */
-    @Test
-    public void testBinomialCoefficientLarge() throws Exception {
-        // This tests all legal and illegal values for n <= 200.
-        for (int n = 0; n <= 200; n++) {
-            for (int k = 0; k <= n; k++) {
-                long ourResult = -1;
-                long exactResult = -1;
-                boolean shouldThrow = false;
-                boolean didThrow = false;
-                try {
-                    ourResult = MathUtils.binomialCoefficient(n, k);
-                } catch (MathArithmeticException ex) {
-                    didThrow = true;
-                }
-                try {
-                    exactResult = binomialCoefficient(n, k);
-                } catch (MathArithmeticException ex) {
-                    shouldThrow = true;
-                }
-                Assert.assertEquals(n + " choose " + k, exactResult, ourResult);
-                Assert.assertEquals(n + " choose " + k, shouldThrow, didThrow);
-                Assert.assertTrue(n + " choose " + k, (n > 66 || !didThrow));
-
-                if (!shouldThrow && exactResult > 1) {
-                    Assert.assertEquals(n + " choose " + k, 1.,
-                        MathUtils.binomialCoefficientDouble(n, k) / exactResult, 1e-10);
-                    Assert.assertEquals(n + " choose " + k, 1,
-                        MathUtils.binomialCoefficientLog(n, k) / FastMath.log(exactResult), 1e-10);
-                }
-            }
-        }
-
-        long ourResult = MathUtils.binomialCoefficient(300, 3);
-        long exactResult = binomialCoefficient(300, 3);
-        Assert.assertEquals(exactResult, ourResult);
-
-        ourResult = MathUtils.binomialCoefficient(700, 697);
-        exactResult = binomialCoefficient(700, 697);
-        Assert.assertEquals(exactResult, ourResult);
-
-        // This one should throw
-        try {
-            MathUtils.binomialCoefficient(700, 300);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-            // Expected
-        }
-
-        int n = 10000;
-        ourResult = MathUtils.binomialCoefficient(n, 3);
-        exactResult = binomialCoefficient(n, 3);
-        Assert.assertEquals(exactResult, ourResult);
-        Assert.assertEquals(1, MathUtils.binomialCoefficientDouble(n, 3) / exactResult, 1e-10);
-        Assert.assertEquals(1, MathUtils.binomialCoefficientLog(n, 3) / FastMath.log(exactResult), 1e-10);
-
-    }
-
-    @Test
-    public void testBinomialCoefficientFail() {
-        try {
-            MathUtils.binomialCoefficient(4, 5);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-
-        try {
-            MathUtils.binomialCoefficientDouble(4, 5);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-
-        try {
-            MathUtils.binomialCoefficientLog(4, 5);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-
-        try {
-            MathUtils.binomialCoefficient(-1, -2);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-        try {
-            MathUtils.binomialCoefficientDouble(-1, -2);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-        try {
-            MathUtils.binomialCoefficientLog(-1, -2);
-            Assert.fail("expecting MathIllegalArgumentException");
-        } catch (MathIllegalArgumentException ex) {
-            // ignored
-        }
-
-        try {
-            MathUtils.binomialCoefficient(67, 30);
-            Assert.fail("expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-            // ignored
-        }
-        try {
-            MathUtils.binomialCoefficient(67, 34);
-            Assert.fail("expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-            // ignored
-        }
-        double x = MathUtils.binomialCoefficientDouble(1030, 515);
-        Assert.assertTrue("expecting infinite binomial coefficient", Double
-            .isInfinite(x));
-    }
-
     @Test
     public void testCosh() {
         double x = 3.0;
@@ -381,104 +163,6 @@ public final class MathUtilsTest {
     }
 
     @Test
-    public void testLcm() {
-        int a = 30;
-        int b = 50;
-        int c = 77;
-
-        Assert.assertEquals(0, MathUtils.lcm(0, b));
-        Assert.assertEquals(0, MathUtils.lcm(a, 0));
-        Assert.assertEquals(b, MathUtils.lcm(1, b));
-        Assert.assertEquals(a, MathUtils.lcm(a, 1));
-        Assert.assertEquals(150, MathUtils.lcm(a, b));
-        Assert.assertEquals(150, MathUtils.lcm(-a, b));
-        Assert.assertEquals(150, MathUtils.lcm(a, -b));
-        Assert.assertEquals(150, MathUtils.lcm(-a, -b));
-        Assert.assertEquals(2310, MathUtils.lcm(a, c));
-
-        // Assert that no intermediate value overflows:
-        // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
-        Assert.assertEquals((1<<20)*15, MathUtils.lcm((1<<20)*3, (1<<20)*5));
-
-        // Special case
-        Assert.assertEquals(0, MathUtils.lcm(0, 0));
-
-        try {
-            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
-            MathUtils.lcm(Integer.MIN_VALUE, 1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-
-        try {
-            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
-            MathUtils.lcm(Integer.MIN_VALUE, 1<<20);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-
-        try {
-            MathUtils.lcm(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-    }
-
-    @Test
-    public void testLcmLong() {
-        long a = 30;
-        long b = 50;
-        long c = 77;
-
-        Assert.assertEquals(0, MathUtils.lcm(0, b));
-        Assert.assertEquals(0, MathUtils.lcm(a, 0));
-        Assert.assertEquals(b, MathUtils.lcm(1, b));
-        Assert.assertEquals(a, MathUtils.lcm(a, 1));
-        Assert.assertEquals(150, MathUtils.lcm(a, b));
-        Assert.assertEquals(150, MathUtils.lcm(-a, b));
-        Assert.assertEquals(150, MathUtils.lcm(a, -b));
-        Assert.assertEquals(150, MathUtils.lcm(-a, -b));
-        Assert.assertEquals(2310, MathUtils.lcm(a, c));
-
-        Assert.assertEquals(Long.MAX_VALUE, MathUtils.lcm(60247241209L, 153092023L));
-
-        // Assert that no intermediate value overflows:
-        // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
-        Assert.assertEquals((1L<<50)*15, MathUtils.lcm((1L<<45)*3, (1L<<50)*5));
-
-        // Special case
-        Assert.assertEquals(0L, MathUtils.lcm(0L, 0L));
-
-        try {
-            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
-            MathUtils.lcm(Long.MIN_VALUE, 1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-
-        try {
-            // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
-            MathUtils.lcm(Long.MIN_VALUE, 1<<20);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-
-        Assert.assertEquals((long) Integer.MAX_VALUE * (Integer.MAX_VALUE - 1),
-            MathUtils.lcm((long)Integer.MAX_VALUE, Integer.MAX_VALUE - 1));
-        try {
-            MathUtils.lcm(Long.MAX_VALUE, Long.MAX_VALUE - 1);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException expected) {
-            // expected
-        }
-    }
-
-    @Test
     public void testLog() {
         Assert.assertEquals(2.0, MathUtils.log(2, 4), 0);
         Assert.assertEquals(3.0, MathUtils.log(2, 8), 0);
@@ -490,54 +174,6 @@ public final class MathUtilsTest {
     }
 
     @Test
-    public void testMulAndCheck() {
-        int big = Integer.MAX_VALUE;
-        int bigNeg = Integer.MIN_VALUE;
-        Assert.assertEquals(big, MathUtils.mulAndCheck(big, 1));
-        try {
-            MathUtils.mulAndCheck(big, 2);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-        }
-        try {
-            MathUtils.mulAndCheck(bigNeg, 2);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-        }
-    }
-
-    @Test
-    public void testMulAndCheckLong() {
-        long max = Long.MAX_VALUE;
-        long min = Long.MIN_VALUE;
-        Assert.assertEquals(max, MathUtils.mulAndCheck(max, 1L));
-        Assert.assertEquals(min, MathUtils.mulAndCheck(min, 1L));
-        Assert.assertEquals(0L, MathUtils.mulAndCheck(max, 0L));
-        Assert.assertEquals(0L, MathUtils.mulAndCheck(min, 0L));
-        Assert.assertEquals(max, MathUtils.mulAndCheck(1L, max));
-        Assert.assertEquals(min, MathUtils.mulAndCheck(1L, min));
-        Assert.assertEquals(0L, MathUtils.mulAndCheck(0L, max));
-        Assert.assertEquals(0L, MathUtils.mulAndCheck(0L, min));
-        Assert.assertEquals(1L, MathUtils.mulAndCheck(-1L, -1L));
-        Assert.assertEquals(min, MathUtils.mulAndCheck(min / 2, 2));
-        testMulAndCheckLongFailure(max, 2L);
-        testMulAndCheckLongFailure(2L, max);
-        testMulAndCheckLongFailure(min, 2L);
-        testMulAndCheckLongFailure(2L, min);
-        testMulAndCheckLongFailure(min, -1L);
-        testMulAndCheckLongFailure(-1L, min);
-    }
-
-    private void testMulAndCheckLongFailure(long a, long b) {
-        try {
-            MathUtils.mulAndCheck(a, b);
-            Assert.fail("Expecting MathArithmeticException");
-        } catch (MathArithmeticException ex) {
-            // success
-        }
-    }
-
-    @Test
     public void testNormalizeAngle() {
         for (double a = -15.0; a <= 15.0; a += 0.1) {
             for (double b = -15.0; b <= 15.0; b += 0.2) {



Mime
View raw message