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:39 UTC
[commons-numbers] 01/02: NUMBERS-173: Set minimum bound on
continued fraction epsilon
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.