You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2021/11/02 10:55:38 UTC
[commons-numbers] branch master updated (8d87be9 -> 924099e)
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git.
from 8d87be9 Sonar fix: Use assertEquals
new a3370a9 NUMBERS-173: Set minimum bound on continued fraction epsilon
new 924099e Reuse the golden ratio continued fraction implementation.
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../numbers/fraction/ContinuedFraction.java | 12 +-
.../numbers/fraction/ContinuedFractionTest.java | 154 ++++++++++++---------
src/changes/changes.xml | 4 +
3 files changed, 99 insertions(+), 71 deletions(-)
[commons-numbers] 01/02: NUMBERS-173: Set minimum bound on
continued fraction epsilon
Posted by ah...@apache.org.
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
commit a3370a933dcf0c4a6e2f7f2519ea610f92704fe6
Author: aherbert <ah...@apache.org>
AuthorDate: Tue Nov 2 10:48:35 2021 +0000
NUMBERS-173: Set minimum bound on continued fraction epsilon
---
.../numbers/fraction/ContinuedFraction.java | 12 +++++++---
.../numbers/fraction/ContinuedFractionTest.java | 28 ++++++++++++++++++++++
src/changes/changes.xml | 4 ++++
3 files changed, 41 insertions(+), 3 deletions(-)
diff --git a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/ContinuedFraction.java b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/ContinuedFraction.java
index 3db48d6..38d1708 100644
--- a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/ContinuedFraction.java
+++ b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/ContinuedFraction.java
@@ -45,6 +45,8 @@ public abstract class ContinuedFraction {
* eps * |b_n|, e.g., 1e-50".
*/
private static final double SMALL = 1e-50;
+ /** Minimum allowed relative error epsilon. Equal to Math.ulp(1.0). */
+ private static final double MIN_EPSILON = 0x1.0p-52;
/**
* Defines the <a href="https://mathworld.wolfram.com/ContinuedFraction.html">
@@ -70,7 +72,7 @@ public abstract class ContinuedFraction {
* Evaluates the continued fraction.
*
* @param x the evaluation point.
- * @param epsilon Maximum error allowed.
+ * @param epsilon Maximum relative error allowed.
* @return the value of the continued fraction evaluated at {@code x}.
* @throws ArithmeticException if the algorithm fails to converge.
* @throws ArithmeticException if the maximal number of iterations is reached
@@ -100,7 +102,7 @@ public abstract class ContinuedFraction {
* </ul>
*
* @param x Point at which to evaluate the continued fraction.
- * @param epsilon Maximum error allowed.
+ * @param epsilon Maximum relative error allowed.
* @param maxIterations Maximum number of iterations.
* @return the value of the continued fraction evaluated at {@code x}.
* @throws ArithmeticException if the algorithm fails to converge.
@@ -108,6 +110,10 @@ public abstract class ContinuedFraction {
* before the expected convergence is achieved.
*/
public double evaluate(double x, double epsilon, int maxIterations) {
+ // Relative error epsilon must not be zero.
+ // Do not use Math.max as NaN would be returned for a NaN epsilon.
+ final double eps = epsilon > MIN_EPSILON ? epsilon : MIN_EPSILON;
+
double hPrev = updateIfCloseToZero(getB(0, x));
int n = 1;
@@ -131,7 +137,7 @@ public abstract class ContinuedFraction {
"Continued fraction diverged to %s for value %s", hN, x);
}
- if (Math.abs(deltaN - 1) < epsilon) {
+ if (Math.abs(deltaN - 1) < eps) {
return hN;
}
diff --git a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
index caa947c..79bf890 100644
--- a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
+++ b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
@@ -19,11 +19,15 @@ package org.apache.commons.numbers.fraction;
import java.util.Locale;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
/**
* Tests for {@link ContinuedFraction}.
*/
class ContinuedFractionTest {
+ /** Golden ratio constant. */
+ private static final double GOLDEN_RATIO = 1.618033988749894848204586834365638117720309;
@Test
void testGoldenRatio() throws Exception {
@@ -44,6 +48,30 @@ class ContinuedFractionTest {
Assertions.assertEquals(1.61803399, gr, eps);
}
+ /**
+ * Test an invalid epsilon (zero, negative or NaN).
+ * See NUMBERS-173.
+ *
+ * @param epsilon the epsilon
+ */
+ @ParameterizedTest
+ @ValueSource(doubles = {0, -1, Double.NaN})
+ void testGoldenRatioEpsilonZero(double epsilon) {
+ ContinuedFraction cf = new ContinuedFraction() {
+ @Override
+ public double getA(int n, double x) {
+ return 1;
+ }
+
+ @Override
+ public double getB(int n, double x) {
+ return 1;
+ }
+ };
+
+ Assertions.assertEquals(GOLDEN_RATIO, cf.evaluate(0, epsilon), Math.ulp(GOLDEN_RATIO));
+ }
+
@Test
void test415Over93() throws Exception {
// https://en.wikipedia.org/wiki/Continued_fraction
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index f4d27df..d3baf40 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -72,6 +72,10 @@ N.B. the Performance testing module requires Java 9+.
(The unit tests require Java 8+)
">
+ <action dev="aherbert" type="fix" issue="173">
+ "ContinuedFraction": Set a minimum bound on the relative error epsilon. Prevents
+ an infinite loop when the epsilon is zero.
+ </action>
<action dev="aherbert" type="fix">
"FactorialDouble": Prevent caching values that are infinite. The cache will support
factorials up to 170.
[commons-numbers] 02/02: Reuse the golden ratio continued fraction
implementation.
Posted by ah...@apache.org.
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
commit 924099e0c03ad21dce3cff85086142ae6d273f27
Author: aherbert <ah...@apache.org>
AuthorDate: Tue Nov 2 10:54:32 2021 +0000
Reuse the golden ratio continued fraction implementation.
---
.../numbers/fraction/ContinuedFractionTest.java | 154 ++++++++++-----------
1 file changed, 72 insertions(+), 82 deletions(-)
diff --git a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
index 79bf890..b9c21e0 100644
--- a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
+++ b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/ContinuedFractionTest.java
@@ -29,47 +29,67 @@ class ContinuedFractionTest {
/** Golden ratio constant. */
private static final double GOLDEN_RATIO = 1.618033988749894848204586834365638117720309;
+ /**
+ * Evaluates the golden ratio.
+ *
+ * <pre>
+ * 1 + 1
+ * ----------------
+ * 1 + 1
+ * ------------
+ * 1 + 1
+ * -------
+ * 1 + ...
+ * </pre>
+ *
+ * <p>This is used to test various conditions for the {@link ContinuedFraction}.
+ *
+ * @see <a href="https://mathworld.wolfram.com/GoldenRatio.html">MathWorld Golden
+ * Ratio equation 17</a>
+ */
+ private static class GoldenRatio extends ContinuedFraction {
+ private static final GoldenRatio INSTANCE = new GoldenRatio();
+
+ /**
+ * @return single instance of GoldenRatio
+ */
+ static GoldenRatio getInstance() {
+ return INSTANCE;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public double getA(int n, double x) {
+ return 1;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public double getB(int n, double x) {
+ return 1;
+ }
+ }
+
@Test
void testGoldenRatio() throws Exception {
- ContinuedFraction cf = new ContinuedFraction() {
- @Override
- public double getA(int n, double x) {
- return 1;
- }
-
- @Override
- public double getB(int n, double x) {
- return 1;
- }
- };
-
final double eps = 1e-8;
- double gr = cf.evaluate(0, eps);
- Assertions.assertEquals(1.61803399, gr, eps);
+ final double gr = GoldenRatio.getInstance().evaluate(0, eps);
+ Assertions.assertEquals(GOLDEN_RATIO, gr, GOLDEN_RATIO * eps);
}
/**
* Test an invalid epsilon (zero, negative or NaN).
* See NUMBERS-173.
*
- * @param epsilon the epsilon
+ * @param epsilon Epsilon
*/
@ParameterizedTest
@ValueSource(doubles = {0, -1, Double.NaN})
void testGoldenRatioEpsilonZero(double epsilon) {
- ContinuedFraction cf = new ContinuedFraction() {
- @Override
- public double getA(int n, double x) {
- return 1;
- }
-
- @Override
- public double getB(int n, double x) {
- return 1;
- }
- };
-
- Assertions.assertEquals(GOLDEN_RATIO, cf.evaluate(0, epsilon), Math.ulp(GOLDEN_RATIO));
+ // An invalid epsilon is set to the minimum epsilon.
+ // It should converge to 1 ULP.
+ final double tolerance = Math.ulp(GOLDEN_RATIO);
+ Assertions.assertEquals(GOLDEN_RATIO, GoldenRatio.getInstance().evaluate(0, epsilon), tolerance);
}
@Test
@@ -84,7 +104,7 @@ class ContinuedFractionTest {
// 7
// = [4; 2, 6, 7]
- ContinuedFraction cf = new ContinuedFraction() {
+ final ContinuedFraction cf = new ContinuedFraction() {
@Override
public double getA(int n, double x) {
return n <= 3 ? 1 : 0;
@@ -93,45 +113,39 @@ class ContinuedFractionTest {
@Override
public double getB(int n, double x) {
switch (n) {
- case 0: return 4;
- case 1: return 2;
- case 2: return 6;
- case 3: return 7;
- default: return 1;
+ case 0:
+ return 4;
+ case 1:
+ return 2;
+ case 2:
+ return 6;
+ case 3:
+ return 7;
+ default:
+ return 1;
}
}
};
final double eps = 1e-8;
- double gr = cf.evaluate(0, eps, 5);
+ final double gr = cf.evaluate(0, eps, 5);
Assertions.assertEquals(415.0 / 93.0, gr, eps);
}
@Test
void testMaxIterationsThrows() throws Exception {
- ContinuedFraction cf = new ContinuedFraction() {
- @Override
- public double getA(int n, double x) {
- return 1;
- }
-
- @Override
- public double getB(int n, double x) {
- return 1;
- }
- };
+ final ContinuedFraction cf = GoldenRatio.getInstance();
final double eps = 1e-8;
final int maxIterations = 3;
- final Throwable t = Assertions.assertThrows(FractionException.class,
- () -> cf.evaluate(0, eps, maxIterations));
+ final Throwable t = Assertions.assertThrows(FractionException.class, () -> cf.evaluate(0, eps, maxIterations));
assertExceptionMessageContains(t, "max");
}
@Test
void testNaNThrows() throws Exception {
// Create a NaN during the iteration
- ContinuedFraction cf = new ContinuedFraction() {
+ final ContinuedFraction cf = new ContinuedFraction() {
@Override
public double getA(int n, double x) {
return 1;
@@ -144,16 +158,15 @@ class ContinuedFractionTest {
};
final double eps = 1e-8;
- final Throwable t = Assertions.assertThrows(FractionException.class,
- () -> cf.evaluate(0, eps, 5));
+ final Throwable t = Assertions.assertThrows(FractionException.class, () -> cf.evaluate(0, eps, 5));
assertExceptionMessageContains(t, "nan");
}
@Test
void testInfThrows() throws Exception {
// Create an infinity during the iteration:
- // a / cPrev => a_1 / b_0 => Double.MAX_VALUE / 0.5
- ContinuedFraction cf = new ContinuedFraction() {
+ // a / cPrev => a_1 / b_0 => Double.MAX_VALUE / 0.5
+ final ContinuedFraction cf = new ContinuedFraction() {
@Override
public double getA(int n, double x) {
return n == 0 ? 1 : Double.MAX_VALUE;
@@ -166,8 +179,7 @@ class ContinuedFractionTest {
};
final double eps = 1e-8;
- final Throwable t = Assertions.assertThrows(FractionException.class,
- () -> cf.evaluate(0, eps, 5));
+ final Throwable t = Assertions.assertThrows(FractionException.class, () -> cf.evaluate(0, eps, 5));
assertExceptionMessageContains(t, "infinity");
}
@@ -179,40 +191,18 @@ class ContinuedFractionTest {
// NUMBERS-46
@Test
void testOneIteration() {
- ContinuedFraction cf = new ContinuedFraction() {
- @Override
- public double getA(int n, double x) {
- return 1;
- }
-
- @Override
- public double getB(int n, double x) {
- return 1;
- }
- };
-
final double eps = 10;
- double gr = cf.evaluate(0, eps, 1);
- Assertions.assertEquals(1.61, gr, eps);
+ final double gr = GoldenRatio.getInstance().evaluate(0, eps, 1);
+ // Expected: 1 + 1 / 1
+ Assertions.assertEquals(2.0, gr);
}
// NUMBERS-46
@Test
void testTwoIterations() {
- ContinuedFraction cf = new ContinuedFraction() {
- @Override
- public double getA(int n, double x) {
- return 1;
- }
-
- @Override
- public double getB(int n, double x) {
- return 1;
- }
- };
-
final double eps = 0.5;
- double gr = cf.evaluate(0, eps, 2);
+ final double gr = GoldenRatio.getInstance().evaluate(0, eps, 2);
+ // Expected: 1 + 1 / (1 + 1 / 1)
Assertions.assertEquals(1.5, gr);
}
}