This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new 274818c NUMBERS-178: Tabulate all representable factorials in
FactorialDouble
274818c is described below
commit 274818ccab651e51a47985a1ea54ef069b524adb
Author: aherbert <[email protected]>
AuthorDate: Fri Dec 3 13:47:57 2021 +0000
NUMBERS-178: Tabulate all representable factorials in FactorialDouble
Values are verified using BigInteger computation of n!
This change deprecates the now redundant caching functionality.
---
.../numbers/combinatorics/FactorialDouble.java | 295 ++++++++++++++-------
.../numbers/combinatorics/FactorialDoubleTest.java | 122 ++-------
src/changes/changes.xml | 5 +
3 files changed, 227 insertions(+), 195 deletions(-)
diff --git
a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
index 260a5bb..6b0baf0 100644
---
a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
+++
b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
@@ -20,86 +20,209 @@ package org.apache.commons.numbers.combinatorics;
/**
* Class for computing the natural logarithm of the
* <a href="http://mathworld.wolfram.com/Factorial.html";>factorial of a
number</a>.
- * It allows to allocate a cache of precomputed values.
*/
public final class FactorialDouble {
- /**
- * Size of precomputed factorials.
- * @see Factorial
- */
- private static final int FACTORIALS_LONG_CACHE_SIZE = 21;
- /**
- * Maximum representable factorial. Any factorial above this will overflow
a {@code double}.
- */
- private static final int MAX_FACTORIAL = 170;
- /**
- * Precomputed values of the function: {@code factorialsDouble[i] = i!}.
- */
- private final double[] factorialsDouble;
-
- /**
- * Creates an instance, reusing the already computed values if available.
- *
- * @param numValues Number of values of the function to compute.
- * @param cache Cached values.
- * @throw IllegalArgumentException if {@code n < 0}.
- */
- private FactorialDouble(int numValues,
- double[] cache) {
- if (numValues < 0) {
- throw new CombinatoricsException(CombinatoricsException.NEGATIVE,
numValues);
- }
-
- // Avoid caching values that are infinite
- final int num = Math.min(numValues, MAX_FACTORIAL + 1);
-
- factorialsDouble = new double[num];
- // Initialize first two entries.
- final int max = num < 2 ? num : 2;
- for (int i = 0; i < max; i++) {
- factorialsDouble[i] = 1;
- }
-
- final int beginCopy = 2;
- int endCopy;
- if (cache == null || cache.length <= beginCopy) {
- endCopy = beginCopy;
- } else if (cache.length <= num) {
- endCopy = cache.length;
- } else {
- endCopy = num;
- }
-
- // Copy available values.
- for (int i = beginCopy; i < endCopy; i++) {
- factorialsDouble[i] = cache[i];
- }
-
- // Precompute.
- for (int i = endCopy; i < num; i++) {
- factorialsDouble[i] = i * factorialsDouble[i - 1];
- }
- }
+ /** All factorials that can be represented as a double (values up to
170!). */
+ private static final double[] FACTORIAL = {
+ 1,
+ 1,
+ 2,
+ 6,
+ 24,
+ 120,
+ 720,
+ 5040,
+ 40320,
+ 362880,
+ 3628800,
+ 3.99168E7,
+ 4.790016E8,
+ 6.2270208E9,
+ 8.71782912E10,
+ 1.307674368E12,
+ 2.0922789888E13,
+ 3.55687428096E14,
+ 6.402373705728E15,
+ 1.21645100408832E17,
+ 2.43290200817664E18,
+ 5.109094217170944E19,
+ 1.1240007277776077E21,
+ 2.585201673888498E22,
+ 6.204484017332394E23,
+ 1.5511210043330986E25,
+ 4.0329146112660565E26,
+ 1.0888869450418352E28,
+ 3.0488834461171387E29,
+ 8.841761993739702E30,
+ 2.6525285981219107E32,
+ 8.222838654177922E33,
+ 2.631308369336935E35,
+ 8.683317618811886E36,
+ 2.9523279903960416E38,
+ 1.0333147966386145E40,
+ 3.7199332678990125E41,
+ 1.3763753091226346E43,
+ 5.230226174666011E44,
+ 2.0397882081197444E46,
+ 8.159152832478977E47,
+ 3.345252661316381E49,
+ 1.40500611775288E51,
+ 6.041526306337383E52,
+ 2.658271574788449E54,
+ 1.1962222086548019E56,
+ 5.502622159812089E57,
+ 2.5862324151116818E59,
+ 1.2413915592536073E61,
+ 6.082818640342675E62,
+ 3.0414093201713376E64,
+ 1.5511187532873822E66,
+ 8.065817517094388E67,
+ 4.2748832840600255E69,
+ 2.308436973392414E71,
+ 1.2696403353658276E73,
+ 7.109985878048635E74,
+ 4.0526919504877214E76,
+ 2.3505613312828785E78,
+ 1.3868311854568984E80,
+ 8.32098711274139E81,
+ 5.075802138772248E83,
+ 3.146997326038794E85,
+ 1.98260831540444E87,
+ 1.2688693218588417E89,
+ 8.247650592082472E90,
+ 5.443449390774431E92,
+ 3.647111091818868E94,
+ 2.4800355424368305E96,
+ 1.711224524281413E98,
+ 1.1978571669969892E100,
+ 8.504785885678623E101,
+ 6.1234458376886085E103,
+ 4.4701154615126844E105,
+ 3.307885441519386E107,
+ 2.48091408113954E109,
+ 1.8854947016660504E111,
+ 1.4518309202828587E113,
+ 1.1324281178206297E115,
+ 8.946182130782976E116,
+ 7.156945704626381E118,
+ 5.797126020747368E120,
+ 4.753643337012842E122,
+ 3.945523969720659E124,
+ 3.314240134565353E126,
+ 2.81710411438055E128,
+ 2.4227095383672734E130,
+ 2.107757298379528E132,
+ 1.8548264225739844E134,
+ 1.650795516090846E136,
+ 1.4857159644817615E138,
+ 1.352001527678403E140,
+ 1.2438414054641308E142,
+ 1.1567725070816416E144,
+ 1.087366156656743E146,
+ 1.032997848823906E148,
+ 9.916779348709496E149,
+ 9.619275968248212E151,
+ 9.426890448883248E153,
+ 9.332621544394415E155,
+ 9.332621544394415E157,
+ 9.42594775983836E159,
+ 9.614466715035127E161,
+ 9.90290071648618E163,
+ 1.0299016745145628E166,
+ 1.081396758240291E168,
+ 1.1462805637347084E170,
+ 1.226520203196138E172,
+ 1.324641819451829E174,
+ 1.4438595832024937E176,
+ 1.588245541522743E178,
+ 1.7629525510902446E180,
+ 1.974506857221074E182,
+ 2.2311927486598138E184,
+ 2.5435597334721877E186,
+ 2.925093693493016E188,
+ 3.393108684451898E190,
+ 3.969937160808721E192,
+ 4.684525849754291E194,
+ 5.574585761207606E196,
+ 6.689502913449127E198,
+ 8.094298525273444E200,
+ 9.875044200833601E202,
+ 1.214630436702533E205,
+ 1.506141741511141E207,
+ 1.882677176888926E209,
+ 2.372173242880047E211,
+ 3.0126600184576594E213,
+ 3.856204823625804E215,
+ 4.974504222477287E217,
+ 6.466855489220474E219,
+ 8.47158069087882E221,
+ 1.1182486511960043E224,
+ 1.4872707060906857E226,
+ 1.9929427461615188E228,
+ 2.6904727073180504E230,
+ 3.659042881952549E232,
+ 5.012888748274992E234,
+ 6.917786472619489E236,
+ 9.615723196941089E238,
+ 1.3462012475717526E241,
+ 1.898143759076171E243,
+ 2.695364137888163E245,
+ 3.854370717180073E247,
+ 5.5502938327393044E249,
+ 8.047926057471992E251,
+ 1.1749972043909107E254,
+ 1.727245890454639E256,
+ 2.5563239178728654E258,
+ 3.80892263763057E260,
+ 5.713383956445855E262,
+ 8.62720977423324E264,
+ 1.3113358856834524E267,
+ 2.0063439050956823E269,
+ 3.0897696138473508E271,
+ 4.789142901463394E273,
+ 7.471062926282894E275,
+ 1.1729568794264145E278,
+ 1.853271869493735E280,
+ 2.9467022724950384E282,
+ 4.7147236359920616E284,
+ 7.590705053947219E286,
+ 1.2296942187394494E289,
+ 2.0044015765453026E291,
+ 3.287218585534296E293,
+ 5.423910666131589E295,
+ 9.003691705778438E297,
+ 1.503616514864999E300,
+ 2.5260757449731984E302,
+ 4.269068009004705E304,
+ 7.257415615307999E306
+ };
+
+ /** Single instance. */
+ private static final FactorialDouble INSTANCE = new FactorialDouble();
+
+ /** No public instances. */
+ private FactorialDouble() {}
/**
- * Creates an instance with no precomputed values.
- * @return instance with no precomputed values
+ * Creates an instance.
+ * @return instance
*/
public static FactorialDouble create() {
- return new FactorialDouble(0, null);
+ return INSTANCE;
}
/**
- * Creates an instance with the specified cache size.
+ * @deprecated Since 1.1 the cache size argument is ignored. Use {@link
#create()} to obtain an instance.
+ *
+ * <p>As of Numbers 1.1 all representable factorials up to {@code n=170}
are tabulated.
+ * This method returns a reference to the same object.
*
- * @param cacheSize Number of precomputed values of the function.
- * @return a new instance where {@code cacheSize} values have been
- * precomputed.
- * @throws IllegalArgumentException if {@code cacheSize < 0}.
+ * @param cacheSize Ignored.
+ * @return instance
*/
+ @Deprecated
public FactorialDouble withCache(final int cacheSize) {
- return new FactorialDouble(cacheSize,
- factorialsDouble);
+ return this;
}
/**
@@ -113,38 +236,14 @@ public final class FactorialDouble {
* @return {@code n!}
* @throws IllegalArgumentException if {@code n < 0}.
*/
+ // Note: This must remain an instance method for binary compatibility
public double value(int n) {
- if (n < FACTORIALS_LONG_CACHE_SIZE) {
- return Factorial.value(n);
- }
-
- if (n < factorialsDouble.length) {
- // Use cache of precomputed values.
- return factorialsDouble[n];
- }
-
- return compute(n);
- }
-
- /**
- * @param n Argument.
- * @return {@code n!} (approximated as a {@code double}).
- */
- private double compute(int n) {
- if (n > MAX_FACTORIAL) {
- return Double.POSITIVE_INFINITY;
- }
-
- int start = 2;
- double result = 1;
-
- if (factorialsDouble.length > 2) {
- result = factorialsDouble[factorialsDouble.length - 1];
- start = factorialsDouble.length;
+ if (n < 0) {
+ throw new CombinatoricsException(CombinatoricsException.NEGATIVE,
n);
}
- for (int i = start; i <= n; i++) {
- result *= i;
+ if (n < FACTORIAL.length) {
+ return FACTORIAL[n];
}
- return result;
+ return Double.POSITIVE_INFINITY;
}
}
diff --git
a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java
b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java
index 40a7c00..23bc7b4 100644
---
a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java
+++
b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/FactorialDoubleTest.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.numbers.combinatorics;
+import java.math.BigInteger;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
@@ -23,49 +24,15 @@ import org.junit.jupiter.api.Test;
* Test cases for the {@link FactorialDouble} class.
*/
class FactorialDoubleTest {
+ /** The largest representable factorial (n=170). */
+ private static final int MAX_N = 170;
+
@Test
void testFactorialZero() {
Assertions.assertEquals(1, FactorialDouble.create().value(0), "0!");
}
@Test
- void testFactorialDirect() {
- for (int i = 1; i < 21; i++) {
- Assertions.assertEquals(
- factorialDirect(i), FactorialDouble.create().value(i), i +
"!");
- }
- }
-
- @Test
- void testLargestFactorialDouble() {
- final int n = 170;
- Assertions.assertNotEquals(
- Double.POSITIVE_INFINITY, FactorialDouble.create().value(n), () ->
n + "!");
- }
-
- @Test
- void testFactorialDoubleTooLarge() {
- final int n = 171;
- // Verify the limit. Start at the largest representable factorial as a
long: 20!
- double f = 2432902008176640000L;
- for (int i = 21; i < n; i++) {
- f *= i;
- }
- Assertions.assertTrue(Double.isFinite(f), "170! is finite");
- f *= n;
- Assertions.assertFalse(Double.isFinite(f), "171! is infinite");
- Assertions.assertEquals(
- Double.POSITIVE_INFINITY, FactorialDouble.create().value(n),
() -> n + "!");
- }
-
- @Test
- void testNonPositiveArgumentWithCache() {
- Assertions.assertThrows(IllegalArgumentException.class,
- () -> FactorialDouble.create().withCache(-1)
- );
- }
-
- @Test
void testNonPositiveArgument() {
Assertions.assertThrows(IllegalArgumentException.class,
() -> FactorialDouble.create().value(-1)
@@ -73,76 +40,37 @@ class FactorialDoubleTest {
}
@Test
- void testCompareDirectWithoutCache() {
- // This test shows that delegating to the "Gamma" class will also lead
to a
- // less accurate result.
-
- final int max = 100;
+ void testFactorials() {
final FactorialDouble f = FactorialDouble.create();
-
- for (int i = 0; i < max; i++) {
- final double expected = factorialDirect(i);
- Assertions.assertEquals(
- expected, f.value(i), 100 * Math.ulp(expected), i + "! ");
+ // Start at 0!
+ BigInteger value = BigInteger.ONE;
+ for (int n = 1; n <= MAX_N; n++) {
+ // n! = (n-1)! * n
+ value = value.multiply(BigInteger.valueOf(n));
+ Assertions.assertEquals(value.doubleValue(), f.value(n));
}
}
@Test
- void testCompareDirectWithCache() {
- final int max = 100;
- final FactorialDouble f = FactorialDouble.create().withCache(max);
-
- for (int i = 0; i < max; i++) {
- final double expected = factorialDirect(i);
- Assertions.assertEquals(
- expected, f.value(i), 100 * Math.ulp(expected), i + "! ");
+ void testFactorialDoubleTooLarge() {
+ final FactorialDouble f = FactorialDouble.create();
+ // Long avoids overflow to negative
+ for (long n = MAX_N + 1; n < Integer.MAX_VALUE; n *= 2) {
+ Assertions.assertEquals(Double.POSITIVE_INFINITY, f.value((int)
n));
}
}
- @Test
- void testCacheIncrease() {
- final int max = 100;
- final FactorialDouble f1 = FactorialDouble.create().withCache(max);
- final FactorialDouble f2 = f1.withCache(2 * max);
-
- final int val = max + max / 2;
- Assertions.assertEquals(f1.value(val), f2.value(val));
- }
-
- @Test
- void testZeroCache() {
- // Ensure that no exception is thrown.
- final FactorialDouble f = FactorialDouble.create().withCache(0);
- Assertions.assertEquals(1, f.value(0));
- Assertions.assertEquals(1, f.value(1));
- }
-
- @Test
- void testUselessCache() {
- Assertions.assertDoesNotThrow(() -> {
- LogFactorial.create().withCache(1);
- LogFactorial.create().withCache(2);
- });
- }
-
- @Test
- void testCacheDecrease() {
- final int max = 100;
- final FactorialDouble f1 = FactorialDouble.create().withCache(max);
- final FactorialDouble f2 = f1.withCache(max / 2);
-
- final int val = max / 4;
- Assertions.assertEquals(f1.value(val), f2.value(val));
- }
-
/**
- * Direct multiplication implementation.
+ * Test the {@link FactorialDouble#withCache(int)} method does nothing.
+ * This method was deprecated since 1.1.
+ * It now allows calling the method with an invalid cache size.
*/
- private double factorialDirect(int n) {
- double result = 1;
- for (int i = 2; i <= n; i++) {
- result *= i;
+ @SuppressWarnings("deprecation")
+ @Test
+ void testWithCacheReturnsThis() {
+ final FactorialDouble f = FactorialDouble.create();
+ for (int cacheSize : new int[] {-1, 0, 10000000}) {
+ Assertions.assertSame(f, f.withCache(cacheSize));
}
- return result;
}
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 954c4f3..a0fc286 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -72,6 +72,11 @@ N.B. the Performance testing module requires Java 9+.
(The unit tests require Java 8+)
">
+ <action dev="aherbert" type="update" issue="NUMBERS-178">
+ "FactorialDouble": Tabulate all representable factorials. This change
deprecates the
+ caching of iteratively computed values with exact 64-bit double
representations of
+ n! up to n=170.
+ </action>
<action dev="aherbert" type="update" issue="NUMBERS-176">
"ContinuedFraction": Update to use a shared implementation with
GeneralizedContinuedFraction.
</action>
