You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ps...@apache.org on 2013/08/24 23:55:36 UTC
svn commit: r1517203 [1/2] - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/analysis/differentiation/
main/java/org/apache/commons/math3/analysis/interpolation/
main/java/org/apache/commons/math3/analysis/polynomials/ ma...
Author: psteitz
Date: Sat Aug 24 21:55:35 2013
New Revision: 1517203
URL: http://svn.apache.org/r1517203
Log:
Added CombinatoricsUtils to the util package, moving binomial
coefficients, factorials and Stirling numbers there and adding
a combinations iterator.
JIRA: MATH-1025
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/CombinatoricsUtilsTest.java
Modified:
commons/proper/math/trunk/src/changes/changes.xml
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/differentiation/DSCompiler.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/ExponentialDistribution.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PascalDistribution.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PoissonDistribution.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DSCompilerTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DerivativeStructureTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtilsTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/InverseHilbertMatrix.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/ArithmeticUtilsTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/MathArraysTest.java
Modified: commons/proper/math/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Sat Aug 24 21:55:35 2013
@@ -51,6 +51,11 @@ If the output is not quite correct, chec
</properties>
<body>
<release version="x.y" date="TBD" description="TBD">
+ <action dev="psteitz" type="add" issue="MATH-1025">
+ Added CombinatoricsUtils to the util package, moving binomial
+ coefficients, factorials and Stirling numbers there and adding
+ a combinations iterator.
+ </action>
<action dev="erans" type="add" issue="MATH-991">
"PolynomialSplineFunction": added method "isValidPoint" that
checks whether a point is within the interpolation range.
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/differentiation/DSCompiler.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/differentiation/DSCompiler.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/differentiation/DSCompiler.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/differentiation/DSCompiler.java Sat Aug 24 21:55:35 2013
@@ -26,7 +26,7 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.MathInternalError;
import org.apache.commons.math3.exception.NotPositiveException;
import org.apache.commons.math3.exception.NumberIsTooLargeException;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.util.MathArrays;
@@ -1752,7 +1752,7 @@ public class DSCompiler {
if (orders[k] > 0) {
try {
term *= FastMath.pow(delta[k], orders[k]) /
- ArithmeticUtils.factorial(orders[k]);
+ CombinatoricsUtils.factorial(orders[k]);
} catch (NotPositiveException e) {
// this cannot happen
throw new MathInternalError(e);
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/interpolation/HermiteInterpolator.java Sat Aug 24 21:55:35 2013
@@ -27,7 +27,7 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.NoDataException;
import org.apache.commons.math3.exception.ZeroException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
/** Polynomial interpolator using both sample values and sample derivatives.
* <p>
@@ -91,7 +91,7 @@ public class HermiteInterpolator impleme
final double[] y = value[i].clone();
if (i > 1) {
- double inv = 1.0 / ArithmeticUtils.factorial(i);
+ double inv = 1.0 / CombinatoricsUtils.factorial(i);
for (int j = 0; j < y.length; ++j) {
y[j] *= inv;
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java Sat Aug 24 21:55:35 2013
@@ -22,7 +22,7 @@ import java.util.List;
import java.util.Map;
import org.apache.commons.math3.fraction.BigFraction;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
/**
@@ -328,7 +328,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) ArithmeticUtils.binomialCoefficient(i, j);
+ coeff[i][j] = (int) CombinatoricsUtils.binomialCoefficient(i, j);
}
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/ExponentialDistribution.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/ExponentialDistribution.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/ExponentialDistribution.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/ExponentialDistribution.java Sat Aug 24 21:55:35 2013
@@ -19,8 +19,8 @@ package org.apache.commons.math3.distrib
import org.apache.commons.math3.exception.NotStrictlyPositiveException;
import org.apache.commons.math3.exception.OutOfRangeException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
-import org.apache.commons.math3.util.ArithmeticUtils;
import org.apache.commons.math3.util.ResizableDoubleArray;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well19937c;
@@ -80,7 +80,7 @@ public class ExponentialDistribution ext
final ResizableDoubleArray ra = new ResizableDoubleArray(20);
while (qi < 1) {
- qi += FastMath.pow(LN2, i) / ArithmeticUtils.factorial(i);
+ qi += FastMath.pow(LN2, i) / CombinatoricsUtils.factorial(i);
ra.addElement(qi);
++i;
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PascalDistribution.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PascalDistribution.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PascalDistribution.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PascalDistribution.java Sat Aug 24 21:55:35 2013
@@ -20,7 +20,7 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.OutOfRangeException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
import org.apache.commons.math3.special.Beta;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well19937c;
@@ -138,7 +138,7 @@ public class PascalDistribution extends
if (x < 0) {
ret = 0.0;
} else {
- ret = ArithmeticUtils.binomialCoefficientDouble(x +
+ ret = CombinatoricsUtils.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/math3/distribution/PoissonDistribution.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PoissonDistribution.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PoissonDistribution.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/distribution/PoissonDistribution.java Sat Aug 24 21:55:35 2013
@@ -19,8 +19,8 @@ package org.apache.commons.math3.distrib
import org.apache.commons.math3.exception.NotStrictlyPositiveException;
import org.apache.commons.math3.exception.util.LocalizedFormats;
import org.apache.commons.math3.special.Gamma;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.MathUtils;
-import org.apache.commons.math3.util.ArithmeticUtils;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well19937c;
@@ -309,7 +309,7 @@ public class PoissonDistribution extends
final double lambda = FastMath.floor(meanPoisson);
final double lambdaFractional = meanPoisson - lambda;
final double logLambda = FastMath.log(lambda);
- final double logLambdaFactorial = ArithmeticUtils.factorialLog((int) lambda);
+ final double logLambdaFactorial = CombinatoricsUtils.factorialLog((int) lambda);
final long y2 = lambdaFractional < Double.MIN_VALUE ? 0 : nextPoisson(lambdaFractional);
final double delta = FastMath.sqrt(lambda * FastMath.log(32 * lambda / FastMath.PI + 1));
final double halfDelta = delta / 2;
@@ -364,7 +364,7 @@ public class PoissonDistribution extends
if (v > qr) {
continue;
}
- if (v < y * logLambda - ArithmeticUtils.factorialLog((int) (y + lambda)) + logLambdaFactorial) {
+ if (v < y * logLambda - CombinatoricsUtils.factorialLog((int) (y + lambda)) + logLambdaFactorial) {
y = lambda + y;
break;
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java Sat Aug 24 21:55:35 2013
@@ -17,7 +17,6 @@
package org.apache.commons.math3.util;
import java.math.BigInteger;
-import java.util.concurrent.atomic.AtomicReference;
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.exception.NotPositiveException;
@@ -33,19 +32,6 @@ import org.apache.commons.math3.exceptio
*/
public final class ArithmeticUtils {
- /** All long-representable factorials */
- static final long[] FACTORIALS = new long[] {
- 1l, 1l, 2l,
- 6l, 24l, 120l,
- 720l, 5040l, 40320l,
- 362880l, 3628800l, 39916800l,
- 479001600l, 6227020800l, 87178291200l,
- 1307674368000l, 20922789888000l, 355687428096000l,
- 6402373705728000l, 121645100408832000l, 2432902008176640000l };
-
- /** Stirling numbers of the second kind. */
- static final AtomicReference<long[][]> STIRLING_S2 = new AtomicReference<long[][]> (null);
-
/** Private constructor. */
private ArithmeticUtils() {
super();
@@ -109,61 +95,11 @@ public final class ArithmeticUtils {
* @throws NumberIsTooLargeException if {@code k > n}.
* @throws MathArithmeticException if the result is too large to be
* represented by a long integer.
+ * @deprecated use {@link CombinatoricsUtils#binomialCoefficient(int, int)}
*/
public static long binomialCoefficient(final int n, final int k)
throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
- ArithmeticUtils.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 {
- // 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 result;
+ return CombinatoricsUtils.binomialCoefficient(n, k);
}
/**
@@ -190,29 +126,11 @@ public final class ArithmeticUtils {
* @throws NumberIsTooLargeException if {@code k > n}.
* @throws MathArithmeticException if the result is too large to be
* represented by a long integer.
+ * @deprecated use {@link CombinatoricsUtils#binomialCoefficientDouble(int, int)}
*/
public static double binomialCoefficientDouble(final int n, final int k)
throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
- ArithmeticUtils.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);
+ return CombinatoricsUtils.binomialCoefficientDouble(n, k);
}
/**
@@ -235,53 +153,11 @@ public final class ArithmeticUtils {
* @throws NumberIsTooLargeException if {@code k > n}.
* @throws MathArithmeticException if the result is too large to be
* represented by a long integer.
+ * @deprecated use {@link CombinatoricsUtils#binomialCoefficientLog(int, int)}
*/
public static double binomialCoefficientLog(final int n, final int k)
throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
- ArithmeticUtils.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;
+ return CombinatoricsUtils.binomialCoefficientLog(n, k);
}
/**
@@ -307,16 +183,10 @@ public final class ArithmeticUtils {
* @throws NotPositiveException if {@code n < 0}.
* @throws MathArithmeticException if {@code n > 20}: The factorial value is too
* large to fit in a {@code long}.
+ * @deprecated use {@link CombinatoricsUtils#factorial(int)}
*/
public static long factorial(final int n) throws NotPositiveException, MathArithmeticException {
- if (n < 0) {
- throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
- n);
- }
- if (n > 20) {
- throw new MathArithmeticException();
- }
- return FACTORIALS[n];
+ return CombinatoricsUtils.factorial(n);
}
/**
@@ -331,16 +201,10 @@ public final class ArithmeticUtils {
* @param n Argument.
* @return {@code n!}
* @throws NotPositiveException if {@code n < 0}.
+ * @deprecated use {@link CombinatoricsUtils#factorialDouble(int)}
*/
public static double factorialDouble(final int n) throws NotPositiveException {
- if (n < 0) {
- throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
- n);
- }
- if (n < 21) {
- return FACTORIALS[n];
- }
- return FastMath.floor(FastMath.exp(ArithmeticUtils.factorialLog(n)) + 0.5);
+ return CombinatoricsUtils.factorialDouble(n);
}
/**
@@ -349,20 +213,10 @@ public final class ArithmeticUtils {
* @param n Argument.
* @return {@code n!}
* @throws NotPositiveException if {@code n < 0}.
+ * @deprecated use {@link CombinatoricsUtils#factorialLog(int)}
*/
public static double factorialLog(final int n) throws NotPositiveException {
- if (n < 0) {
- throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
- n);
- }
- if (n < 21) {
- return FastMath.log(FACTORIALS[n]);
- }
- double logSum = 0;
- for (int i = 2; i <= n; i++) {
- logSum += FastMath.log(i);
- }
- return logSum;
+ return CombinatoricsUtils.factorialLog(n);
}
/**
@@ -968,71 +822,11 @@ public final class ArithmeticUtils {
* @throws MathArithmeticException if some overflow happens, typically for n exceeding 25 and
* k between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow)
* @since 3.1
+ * @deprecated use {@link CombinatoricsUtils#stirlingS2(int, int)}
*/
public static long stirlingS2(final int n, final int k)
throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
- if (k < 0) {
- throw new NotPositiveException(k);
- }
- if (k > n) {
- throw new NumberIsTooLargeException(k, n, true);
- }
-
- long[][] stirlingS2 = STIRLING_S2.get();
-
- if (stirlingS2 == null) {
- // the cache has never been initialized, compute the first numbers
- // by direct recurrence relation
-
- // as S(26,9) = 11201516780955125625 is larger than Long.MAX_VALUE
- // we must stop computation at row 26
- final int maxIndex = 26;
- stirlingS2 = new long[maxIndex][];
- stirlingS2[0] = new long[] { 1l };
- for (int i = 1; i < stirlingS2.length; ++i) {
- stirlingS2[i] = new long[i + 1];
- stirlingS2[i][0] = 0;
- stirlingS2[i][1] = 1;
- stirlingS2[i][i] = 1;
- for (int j = 2; j < i; ++j) {
- stirlingS2[i][j] = j * stirlingS2[i - 1][j] + stirlingS2[i - 1][j - 1];
- }
- }
-
- // atomically save the cache
- STIRLING_S2.compareAndSet(null, stirlingS2);
-
- }
-
- if (n < stirlingS2.length) {
- // the number is in the small cache
- return stirlingS2[n][k];
- } else {
- // use explicit formula to compute the number without caching it
- if (k == 0) {
- return 0;
- } else if (k == 1 || k == n) {
- return 1;
- } else if (k == 2) {
- return (1l << (n - 1)) - 1l;
- } else if (k == n - 1) {
- return binomialCoefficient(n, 2);
- } else {
- // definition formula: note that this may trigger some overflow
- long sum = 0;
- long sign = ((k & 0x1) == 0) ? 1 : -1;
- for (int j = 1; j <= k; ++j) {
- sign = -sign;
- sum += sign * binomialCoefficient(k, j) * pow(j, n);
- if (sum < 0) {
- // there was an overflow somewhere
- throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN,
- n, 0, stirlingS2.length - 1);
- }
- }
- return sum / factorial(k);
- }
- }
+ return CombinatoricsUtils.stirlingS2(n, k);
}
@@ -1083,24 +877,6 @@ public final class ArithmeticUtils {
}
/**
- * 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) throws NumberIsTooLargeException, NotPositiveException {
- 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 true if the argument is a power of two.
*
* @param n the number to test
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java?rev=1517203&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/CombinatoricsUtils.java Sat Aug 24 21:55:35 2013
@@ -0,0 +1,637 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math3.util;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicReference;
+
+import org.apache.commons.math3.exception.MathArithmeticException;
+import org.apache.commons.math3.exception.NotPositiveException;
+import org.apache.commons.math3.exception.NumberIsTooLargeException;
+import org.apache.commons.math3.exception.util.LocalizedFormats;
+
+/**
+ * Combinatorial utilities.
+ *
+ * @version $Id$
+ * @since 3.3
+ */
+public final class CombinatoricsUtils {
+
+ /** All long-representable factorials */
+ static final long[] FACTORIALS = new long[] {
+ 1l, 1l, 2l,
+ 6l, 24l, 120l,
+ 720l, 5040l, 40320l,
+ 362880l, 3628800l, 39916800l,
+ 479001600l, 6227020800l, 87178291200l,
+ 1307674368000l, 20922789888000l, 355687428096000l,
+ 6402373705728000l, 121645100408832000l, 2432902008176640000l };
+
+ /** Stirling numbers of the second kind. */
+ static final AtomicReference<long[][]> STIRLING_S2 = new AtomicReference<long[][]> (null);
+
+ /** Private constructor. */
+ private CombinatoricsUtils() {
+ super();
+ }
+
+
+ /**
+ * 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 NotPositiveException if {@code n < 0}.
+ * @throws NumberIsTooLargeException if {@code k > n}.
+ * @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)
+ throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
+ CombinatoricsUtils.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 = ArithmeticUtils.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 = ArithmeticUtils.gcd(i, j);
+ result = ArithmeticUtils.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 NotPositiveException if {@code n < 0}.
+ * @throws NumberIsTooLargeException if {@code k > n}.
+ * @throws MathArithmeticException if the result is too large to be
+ * represented by a long integer.
+ */
+ public static double binomialCoefficientDouble(final int n, final int k)
+ throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
+ CombinatoricsUtils.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 NotPositiveException if {@code n < 0}.
+ * @throws NumberIsTooLargeException if {@code k > n}.
+ * @throws MathArithmeticException if the result is too large to be
+ * represented by a long integer.
+ */
+ public static double binomialCoefficientLog(final int n, final int k)
+ throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
+ CombinatoricsUtils.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;
+ }
+
+ /**
+ * Returns n!. Shorthand for {@code n} <a
+ * href="http://mathworld.wolfram.com/Factorial.html"> Factorial</a>, the
+ * product of the numbers {@code 1,...,n}.
+ * <p>
+ * <Strong>Preconditions</strong>:
+ * <ul>
+ * <li> {@code n >= 0} (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 {@code n!} <
+ * Long.MAX_VALUE} is 20. If the computed value exceeds {@code Long.MAX_VALUE}
+ * an {@code ArithMeticException } is thrown.</li>
+ * </ul>
+ * </p>
+ *
+ * @param n argument
+ * @return {@code n!}
+ * @throws MathArithmeticException if the result is too large to be represented
+ * by a {@code long}.
+ * @throws NotPositiveException if {@code n < 0}.
+ * @throws MathArithmeticException if {@code n > 20}: The factorial value is too
+ * large to fit in a {@code long}.
+ */
+ public static long factorial(final int n) throws NotPositiveException, MathArithmeticException {
+ if (n < 0) {
+ throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
+ n);
+ }
+ if (n > 20) {
+ throw new MathArithmeticException();
+ }
+ return FACTORIALS[n];
+ }
+
+ /**
+ * Compute n!, the<a href="http://mathworld.wolfram.com/Factorial.html">
+ * factorial</a> of {@code n} (the product of the numbers 1 to n), as a
+ * {@code double}.
+ * The result should be small enough to fit into a {@code double}: The
+ * largest {@code n} for which {@code n! < Double.MAX_VALUE} is 170.
+ * If the computed value exceeds {@code Double.MAX_VALUE},
+ * {@code Double.POSITIVE_INFINITY} is returned.
+ *
+ * @param n Argument.
+ * @return {@code n!}
+ * @throws NotPositiveException if {@code n < 0}.
+ */
+ public static double factorialDouble(final int n) throws NotPositiveException {
+ if (n < 0) {
+ throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
+ n);
+ }
+ if (n < 21) {
+ return FACTORIALS[n];
+ }
+ return FastMath.floor(FastMath.exp(CombinatoricsUtils.factorialLog(n)) + 0.5);
+ }
+
+ /**
+ * Compute the natural logarithm of the factorial of {@code n}.
+ *
+ * @param n Argument.
+ * @return {@code n!}
+ * @throws NotPositiveException if {@code n < 0}.
+ */
+ public static double factorialLog(final int n) throws NotPositiveException {
+ if (n < 0) {
+ throw new NotPositiveException(LocalizedFormats.FACTORIAL_NEGATIVE_PARAMETER,
+ n);
+ }
+ if (n < 21) {
+ return FastMath.log(FACTORIALS[n]);
+ }
+ double logSum = 0;
+ for (int i = 2; i <= n; i++) {
+ logSum += FastMath.log(i);
+ }
+ return logSum;
+ }
+
+ /**
+ * Returns the <a
+ * href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html">
+ * Stirling number of the second kind</a>, "{@code S(n,k)}", the number of
+ * ways of partitioning an {@code n}-element set into {@code k} non-empty
+ * subsets.
+ * <p>
+ * The preconditions are {@code 0 <= k <= n } (otherwise
+ * {@code NotPositiveException} is thrown)
+ * </p>
+ * @param n the size of the set
+ * @param k the number of non-empty subsets
+ * @return {@code S(n,k)}
+ * @throws NotPositiveException if {@code k < 0}.
+ * @throws NumberIsTooLargeException if {@code k > n}.
+ * @throws MathArithmeticException if some overflow happens, typically for n exceeding 25 and
+ * k between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow)
+ * @since 3.1
+ */
+ public static long stirlingS2(final int n, final int k)
+ throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException {
+ if (k < 0) {
+ throw new NotPositiveException(k);
+ }
+ if (k > n) {
+ throw new NumberIsTooLargeException(k, n, true);
+ }
+
+ long[][] stirlingS2 = STIRLING_S2.get();
+
+ if (stirlingS2 == null) {
+ // the cache has never been initialized, compute the first numbers
+ // by direct recurrence relation
+
+ // as S(26,9) = 11201516780955125625 is larger than Long.MAX_VALUE
+ // we must stop computation at row 26
+ final int maxIndex = 26;
+ stirlingS2 = new long[maxIndex][];
+ stirlingS2[0] = new long[] { 1l };
+ for (int i = 1; i < stirlingS2.length; ++i) {
+ stirlingS2[i] = new long[i + 1];
+ stirlingS2[i][0] = 0;
+ stirlingS2[i][1] = 1;
+ stirlingS2[i][i] = 1;
+ for (int j = 2; j < i; ++j) {
+ stirlingS2[i][j] = j * stirlingS2[i - 1][j] + stirlingS2[i - 1][j - 1];
+ }
+ }
+
+ // atomically save the cache
+ STIRLING_S2.compareAndSet(null, stirlingS2);
+
+ }
+
+ if (n < stirlingS2.length) {
+ // the number is in the small cache
+ return stirlingS2[n][k];
+ } else {
+ // use explicit formula to compute the number without caching it
+ if (k == 0) {
+ return 0;
+ } else if (k == 1 || k == n) {
+ return 1;
+ } else if (k == 2) {
+ return (1l << (n - 1)) - 1l;
+ } else if (k == n - 1) {
+ return binomialCoefficient(n, 2);
+ } else {
+ // definition formula: note that this may trigger some overflow
+ long sum = 0;
+ long sign = ((k & 0x1) == 0) ? 1 : -1;
+ for (int j = 1; j <= k; ++j) {
+ sign = -sign;
+ sum += sign * binomialCoefficient(k, j) * ArithmeticUtils.pow(j, n);
+ if (sum < 0) {
+ // there was an overflow somewhere
+ throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN,
+ n, 0, stirlingS2.length - 1);
+ }
+ }
+ return sum / factorial(k);
+ }
+ }
+
+ }
+
+ /**
+ * Returns an Iterator whose range is the k-element subsets of {0, ..., n - 1}
+ * represented as {@code int[]} arrays.
+ * <p>
+ * The arrays returned by the iterator are sorted in descending order and
+ * they are visited in lexicographic order with significance from right to
+ * left. For example, combinationsIterator(4, 2) returns an Iterator that
+ * will generate the following sequence of arrays on successive calls to
+ * {@code next()}:<br/>
+ * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]}
+ * </p>
+ * If {@code k == 0} an Iterator containing an empty array is returned and
+ * if {@code k == n} an Iterator containing [0, ..., n -1] is returned.
+ *
+ * @param n size of the set from which subsets are selected
+ * @param k size of the subsets to be enumerated
+ * @return an Iterator over the k-sets in n
+ * @throws NotPositiveException if {@code n < 0}.
+ * @throws NumberIsTooLargeException if {@code k > n}.
+ */
+ public static Iterator<int[]> combinationsIterator(int n, int k) {
+ checkBinomial(n, k);
+ if (k == 0) {
+ return new SingletonIterator(new int[]{});
+ }
+ if (k == n) {
+ // TODO: once getNatural is extracted from RandomDataGenerator, use it
+ final int[] natural = new int[n];
+ for (int i = 0; i < n; i++) {
+ natural[i] = i;
+ }
+ return new SingletonIterator(natural);
+ }
+ return new LexicographicCombinationIterator(n, k);
+ }
+
+ /**
+ * Lexicographic combinations iterator.
+ * <p>
+ * Implementation follows Algorithm T in <i>The Art of Computer Programming</i>
+ * Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All
+ * Combinations</a>, D. Knuth, 2004.</p>
+ * <p>
+ * The degenerate cases {@code k == 0} and {@code k == n} are NOT handled by this
+ * implementation. If constructor arguments satisfy {@code k == 0}
+ * or {@code k >= n}, no exception is generated, but the iterator is empty.
+ * </p>
+ *
+ */
+ private static class LexicographicCombinationIterator implements Iterator<int[]> {
+
+ /** Size of subsets returned by the iterator */
+ private final int k;
+
+ /**
+ * c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are
+ * sentinels.
+ * <p>
+ * Note that c[0] is "wasted" but this makes it a little easier to
+ * follow the code.
+ * </p>
+ */
+ private final int[] c;
+
+ /** Return value for {@link #hasNext()} */
+ private boolean more = true;
+
+ /** Marker: smallest index such that c[j + 1] > j */
+ private int j;
+
+ /**
+ * Construct a CombinationIterator to enumerate k-sets from n.
+ * <p>
+ * NOTE: If {@code k === 0} or {@code k >= n}, the Iterator will be empty
+ * (that is, {@link #hasNext()} will return {@code false} immediately.
+ * </p>
+ *
+ * @param n size of the set from which subsets are enumerated
+ * @param k size of the subsets to enumerate
+ */
+ public LexicographicCombinationIterator(int n, int k) {
+ this.k = k;
+ c = new int[k + 3];
+ if (k == 0 || k >= n) {
+ more = false;
+ return;
+ }
+ // Initialize c to start with lexicographically first k-set
+ for (int i = 1; i <= k; i++) {
+ c[i] = i - 1;
+ }
+ // Initialize sentinels
+ c[k + 1] = n;
+ c[k + 2] = 0;
+ j = k; // Set up invariant: j is smallest index such that c[j + 1] > j
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasNext() {
+ return more;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int[] next() {
+ if (!more) {
+ throw new NoSuchElementException();
+ }
+ // Copy return value (prepared by last activation)
+ final int[] ret = new int[k];
+ System.arraycopy(c, 1, ret, 0, k);
+ //final int[] ret = MathArrays.copyOf(c, k + 1);
+
+ // Prepare next iteration
+ // T2 and T6 loop
+ int x = 0;
+ if (j > 0) {
+ x = j;
+ c[j] = x;
+ j--;
+ return ret;
+ }
+ // T3
+ if (c[1] + 1 < c[2]) {
+ c[1] = c[1] + 1;
+ return ret;
+ } else {
+ j = 2;
+ }
+ // T4
+ boolean stepDone = false;
+ while (!stepDone) {
+ c[j - 1] = j - 2;
+ x = c[j] + 1;
+ if (x == c[j + 1]) {
+ j++;
+ } else {
+ stepDone = true;
+ }
+ }
+ // T5
+ if (j > k) {
+ more = false;
+ return ret;
+ }
+ // T6
+ c[j] = x;
+ j--;
+ return ret;
+ }
+
+ /**
+ * Not supported.
+ */
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * Iterator with just one element to handle degenerate cases (full array,
+ * empty array) for combination iterator.
+ */
+ private static class SingletonIterator implements Iterator<int[]> {
+ /** Singleton array */
+ private final int[] singleton;
+ /** True on initialization, false after first call to next */
+ private boolean more = true;
+ /**
+ * Create a singleton iterator providing the given array.
+ * @param singleton array returned by the iterator
+ */
+ public SingletonIterator(final int[] singleton) {
+ this.singleton = singleton;
+ }
+ /** @return True until next is called the first time, then false */
+ public boolean hasNext() {
+ return more;
+ }
+ /** @return the singleton in first activation; throws NSEE thereafter */
+ public int[] next() {
+ if (more) {
+ more = false;
+ return singleton;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+ /** Not supported */
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * 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) throws NumberIsTooLargeException, NotPositiveException {
+ 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/test/java/org/apache/commons/math3/analysis/differentiation/DSCompilerTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DSCompilerTest.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DSCompilerTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DSCompilerTest.java Sat Aug 24 21:55:35 2013
@@ -22,7 +22,7 @@ import java.util.HashMap;
import java.util.Map;
import org.apache.commons.math3.exception.DimensionMismatchException;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.junit.Assert;
import org.junit.Test;
@@ -36,7 +36,7 @@ public class DSCompilerTest {
public void testSize() {
for (int i = 0; i < 6; ++i) {
for (int j = 0; j < 6; ++j) {
- long expected = ArithmeticUtils.binomialCoefficient(i + j, i);
+ long expected = CombinatoricsUtils.binomialCoefficient(i + j, i);
Assert.assertEquals(expected, DSCompiler.getCompiler(i, j).getSize());
Assert.assertEquals(expected, DSCompiler.getCompiler(j, i).getSize());
}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DerivativeStructureTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DerivativeStructureTest.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DerivativeStructureTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/differentiation/DerivativeStructureTest.java Sat Aug 24 21:55:35 2013
@@ -27,6 +27,7 @@ import org.apache.commons.math3.exceptio
import org.apache.commons.math3.exception.NumberIsTooLargeException;
import org.apache.commons.math3.random.Well1024a;
import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
import org.junit.Assert;
import org.junit.Test;
@@ -175,7 +176,7 @@ public class DerivativeStructureTest ext
DerivativeStructure r = new DerivativeStructure(1, 6, 0, x).reciprocal();
Assert.assertEquals(1 / x, r.getValue(), 1.0e-15);
for (int i = 1; i < r.getOrder(); ++i) {
- double expected = ArithmeticUtils.pow(-1, i) * ArithmeticUtils.factorial(i) /
+ double expected = ArithmeticUtils.pow(-1, i) * CombinatoricsUtils.factorial(i) /
FastMath.pow(x, i + 1);
Assert.assertEquals(expected, r.getPartialDerivative(i), 1.0e-15 * FastMath.abs(expected));
}
@@ -651,7 +652,7 @@ public class DerivativeStructureTest ext
DerivativeStructure log = new DerivativeStructure(1, maxOrder, 0, x).log();
Assert.assertEquals(FastMath.log(x), log.getValue(), epsilon[0]);
for (int n = 1; n <= maxOrder; ++n) {
- double refDer = -ArithmeticUtils.factorial(n - 1) / FastMath.pow(-x, n);
+ double refDer = -CombinatoricsUtils.factorial(n - 1) / FastMath.pow(-x, n);
Assert.assertEquals(refDer, log.getPartialDerivative(n), epsilon[n]);
}
}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtilsTest.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtilsTest.java Sat Aug 24 21:55:35 2013
@@ -18,7 +18,7 @@ package org.apache.commons.math3.analysi
import org.apache.commons.math3.analysis.UnivariateFunction;
import org.apache.commons.math3.analysis.integration.IterativeLegendreGaussIntegrator;
-import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.util.Precision;
import org.junit.Assert;
@@ -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 = ArithmeticUtils.binomialCoefficient(v + i, i);
+ double binomial = CombinatoricsUtils.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/math3/linear/InverseHilbertMatrix.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/InverseHilbertMatrix.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/InverseHilbertMatrix.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/linear/InverseHilbertMatrix.java Sat Aug 24 21:55:35 2013
@@ -18,6 +18,7 @@ package org.apache.commons.math3.linear;
import org.apache.commons.math3.exception.DimensionMismatchException;
import org.apache.commons.math3.util.ArithmeticUtils;
+import org.apache.commons.math3.util.CombinatoricsUtils;
/**
* This class implements inverses of Hilbert Matrices as
@@ -54,11 +55,11 @@ public class InverseHilbertMatrix
*/
public long getEntry(final int i, final int j) {
long val = i + j + 1;
- long aux = ArithmeticUtils.binomialCoefficient(n + i, n - j - 1);
+ long aux = CombinatoricsUtils.binomialCoefficient(n + i, n - j - 1);
val = ArithmeticUtils.mulAndCheck(val, aux);
- aux = ArithmeticUtils.binomialCoefficient(n + j, n - i - 1);
+ aux = CombinatoricsUtils.binomialCoefficient(n + j, n - i - 1);
val = ArithmeticUtils.mulAndCheck(val, aux);
- aux = ArithmeticUtils.binomialCoefficient(i + j, i);
+ aux = CombinatoricsUtils.binomialCoefficient(i + j, i);
val = ArithmeticUtils.mulAndCheck(val, aux);
val = ArithmeticUtils.mulAndCheck(val, aux);
return ((i + j) & 1) == 0 ? val : -val;
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/ArithmeticUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/ArithmeticUtilsTest.java?rev=1517203&r1=1517202&r2=1517203&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/ArithmeticUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/util/ArithmeticUtilsTest.java Sat Aug 24 21:55:35 2013
@@ -18,16 +18,11 @@ package org.apache.commons.math3.util;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
import java.math.BigInteger;
import org.apache.commons.math3.exception.MathArithmeticException;
import org.apache.commons.math3.exception.MathIllegalArgumentException;
-import org.apache.commons.math3.exception.NotPositiveException;
-import org.apache.commons.math3.exception.NumberIsTooLargeException;
-import org.apache.commons.math3.random.RandomDataImpl;
+import org.apache.commons.math3.random.RandomDataGenerator;
import org.junit.Assert;
import org.junit.Test;
@@ -38,17 +33,6 @@ import org.junit.Test;
*/
public class ArithmeticUtilsTest {
- /** 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(ArithmeticUtils.binomialCoefficientDouble(0, 0), 1d, 0);
- Assert.assertEquals(ArithmeticUtils.binomialCoefficientLog(0, 0), 0d, 0);
- Assert.assertEquals(ArithmeticUtils.binomialCoefficient(0, 0), 1);
- }
-
@Test
public void testAddAndCheck() {
int big = Integer.MAX_VALUE;
@@ -84,214 +68,6 @@ public class ArithmeticUtilsTest {
testAddAndCheckLongFailure(-1L, min);
}
-
- @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], ArithmeticUtils.binomialCoefficient(5, i));
- }
- for (int i = 0; i < 7; i++) {
- Assert.assertEquals("6 choose " + i, bcoef6[i], ArithmeticUtils.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), ArithmeticUtils.binomialCoefficient(n, k));
- Assert.assertEquals(n + " choose " + k, binomialCoefficient(n, k), ArithmeticUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE);
- Assert.assertEquals(n + " choose " + k, FastMath.log(binomialCoefficient(n, k)), ArithmeticUtils.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,
- ArithmeticUtils.binomialCoefficient(n[i], k[i]));
- Assert.assertEquals(n[i] + " choose " + k[i], expected,
- ArithmeticUtils.binomialCoefficientDouble(n[i], k[i]), 0.0);
- Assert.assertEquals("log(" + n[i] + " choose " + k[i] + ")", FastMath.log(expected),
- ArithmeticUtils.binomialCoefficientLog(n[i], k[i]), 0.0);
- }
- }
-
- @Test
- public void testBinomialCoefficientFail() {
- try {
- ArithmeticUtils.binomialCoefficient(4, 5);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
-
- try {
- ArithmeticUtils.binomialCoefficientDouble(4, 5);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
-
- try {
- ArithmeticUtils.binomialCoefficientLog(4, 5);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
-
- try {
- ArithmeticUtils.binomialCoefficient(-1, -2);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.binomialCoefficientDouble(-1, -2);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.binomialCoefficientLog(-1, -2);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
-
- try {
- ArithmeticUtils.binomialCoefficient(67, 30);
- Assert.fail("expecting MathArithmeticException");
- } catch (MathArithmeticException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.binomialCoefficient(67, 34);
- Assert.fail("expecting MathArithmeticException");
- } catch (MathArithmeticException ex) {
- // ignored
- }
- double x = ArithmeticUtils.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 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 = ArithmeticUtils.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.,
- ArithmeticUtils.binomialCoefficientDouble(n, k) / exactResult, 1e-10);
- Assert.assertEquals(n + " choose " + k, 1,
- ArithmeticUtils.binomialCoefficientLog(n, k) / FastMath.log(exactResult), 1e-10);
- }
- }
- }
-
- long ourResult = ArithmeticUtils.binomialCoefficient(300, 3);
- long exactResult = binomialCoefficient(300, 3);
- Assert.assertEquals(exactResult, ourResult);
-
- ourResult = ArithmeticUtils.binomialCoefficient(700, 697);
- exactResult = binomialCoefficient(700, 697);
- Assert.assertEquals(exactResult, ourResult);
-
- // This one should throw
- try {
- ArithmeticUtils.binomialCoefficient(700, 300);
- Assert.fail("Expecting MathArithmeticException");
- } catch (MathArithmeticException ex) {
- // Expected
- }
-
- int n = 10000;
- ourResult = ArithmeticUtils.binomialCoefficient(n, 3);
- exactResult = binomialCoefficient(n, 3);
- Assert.assertEquals(exactResult, ourResult);
- Assert.assertEquals(1, ArithmeticUtils.binomialCoefficientDouble(n, 3) / exactResult, 1e-10);
- Assert.assertEquals(1, ArithmeticUtils.binomialCoefficientLog(n, 3) / FastMath.log(exactResult), 1e-10);
-
- }
-
- @Test
- public void testFactorial() {
- for (int i = 1; i < 21; i++) {
- Assert.assertEquals(i + "! ", factorial(i), ArithmeticUtils.factorial(i));
- Assert.assertEquals(i + "! ", factorial(i), ArithmeticUtils.factorialDouble(i), Double.MIN_VALUE);
- Assert.assertEquals(i + "! ", FastMath.log(factorial(i)), ArithmeticUtils.factorialLog(i), 10E-12);
- }
-
- Assert.assertEquals("0", 1, ArithmeticUtils.factorial(0));
- Assert.assertEquals("0", 1.0d, ArithmeticUtils.factorialDouble(0), 1E-14);
- Assert.assertEquals("0", 0.0d, ArithmeticUtils.factorialLog(0), 1E-14);
- }
-
- @Test
- public void testFactorialFail() {
- try {
- ArithmeticUtils.factorial(-1);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.factorialDouble(-1);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.factorialLog(-1);
- Assert.fail("expecting MathIllegalArgumentException");
- } catch (MathIllegalArgumentException ex) {
- // ignored
- }
- try {
- ArithmeticUtils.factorial(21);
- Assert.fail("expecting MathArithmeticException");
- } catch (MathArithmeticException ex) {
- // ignored
- }
- Assert.assertTrue("expecting infinite factorial value", Double.isInfinite(ArithmeticUtils.factorialDouble(171)));
- }
-
@Test
public void testGcd() {
int a = 30;
@@ -350,7 +126,7 @@ public class ArithmeticUtilsTest {
for (int i = 0; i < primeList.length; i++) {
primes.add(Integer.valueOf(primeList[i]));
}
- RandomDataImpl randomData = new RandomDataImpl();
+ RandomDataGenerator randomData = new RandomDataGenerator();
for (int i = 0; i < 20; i++) {
Object[] sample = randomData.nextSample(primes, 4);
int p1 = ((Integer) sample[0]).intValue();
@@ -695,110 +471,6 @@ public class ArithmeticUtilsTest {
}
}
- @Test
- public void testStirlingS2() {
-
- Assert.assertEquals(1, ArithmeticUtils.stirlingS2(0, 0));
-
- for (int n = 1; n < 30; ++n) {
- Assert.assertEquals(0, ArithmeticUtils.stirlingS2(n, 0));
- Assert.assertEquals(1, ArithmeticUtils.stirlingS2(n, 1));
- if (n > 2) {
- Assert.assertEquals((1l << (n - 1)) - 1l, ArithmeticUtils.stirlingS2(n, 2));
- Assert.assertEquals(ArithmeticUtils.binomialCoefficient(n, 2),
- ArithmeticUtils.stirlingS2(n, n - 1));
- }
- Assert.assertEquals(1, ArithmeticUtils.stirlingS2(n, n));
- }
- Assert.assertEquals(536870911l, ArithmeticUtils.stirlingS2(30, 2));
- Assert.assertEquals(576460752303423487l, ArithmeticUtils.stirlingS2(60, 2));
-
- Assert.assertEquals( 25, ArithmeticUtils.stirlingS2( 5, 3));
- Assert.assertEquals( 90, ArithmeticUtils.stirlingS2( 6, 3));
- Assert.assertEquals( 65, ArithmeticUtils.stirlingS2( 6, 4));
- Assert.assertEquals( 301, ArithmeticUtils.stirlingS2( 7, 3));
- Assert.assertEquals( 350, ArithmeticUtils.stirlingS2( 7, 4));
- Assert.assertEquals( 140, ArithmeticUtils.stirlingS2( 7, 5));
- Assert.assertEquals( 966, ArithmeticUtils.stirlingS2( 8, 3));
- Assert.assertEquals( 1701, ArithmeticUtils.stirlingS2( 8, 4));
- Assert.assertEquals( 1050, ArithmeticUtils.stirlingS2( 8, 5));
- Assert.assertEquals( 266, ArithmeticUtils.stirlingS2( 8, 6));
- Assert.assertEquals( 3025, ArithmeticUtils.stirlingS2( 9, 3));
- Assert.assertEquals( 7770, ArithmeticUtils.stirlingS2( 9, 4));
- Assert.assertEquals( 6951, ArithmeticUtils.stirlingS2( 9, 5));
- Assert.assertEquals( 2646, ArithmeticUtils.stirlingS2( 9, 6));
- Assert.assertEquals( 462, ArithmeticUtils.stirlingS2( 9, 7));
- Assert.assertEquals( 9330, ArithmeticUtils.stirlingS2(10, 3));
- Assert.assertEquals(34105, ArithmeticUtils.stirlingS2(10, 4));
- Assert.assertEquals(42525, ArithmeticUtils.stirlingS2(10, 5));
- Assert.assertEquals(22827, ArithmeticUtils.stirlingS2(10, 6));
- Assert.assertEquals( 5880, ArithmeticUtils.stirlingS2(10, 7));
- Assert.assertEquals( 750, ArithmeticUtils.stirlingS2(10, 8));
-
- }
-
- @Test(expected=NotPositiveException.class)
- public void testStirlingS2NegativeN() {
- ArithmeticUtils.stirlingS2(3, -1);
- }
-
- @Test(expected=NumberIsTooLargeException.class)
- public void testStirlingS2LargeK() {
- ArithmeticUtils.stirlingS2(3, 4);
- }
-
- @Test(expected=MathArithmeticException.class)
- public void testStirlingS2Overflow() {
- ArithmeticUtils.stirlingS2(26, 9);
- }
-
- /**
- * 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 = ArithmeticUtils.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 {
ArithmeticUtils.addAndCheck(a, b);