You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ce...@apache.org on 2011/10/13 07:29:28 UTC
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...
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) {