This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits 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 a4b3841d NUMBERS-211: Ensure convergence at machine precision
a4b3841d is described below
commit a4b3841d18dab3b0f3e2e6b240c428c9cf4865f9
Author: Alex Herbert <[email protected]>
AuthorDate: Fri Aug 21 08:09:35 2026 +0100
NUMBERS-211: Ensure convergence at machine precision
---
.../commons/numbers/rootfinder/BrentSolver.java | 7 ++++++-
.../commons/numbers/rootfinder/BrentSolverTest.java | 20 ++++++++++++++++++++
src/changes/changes.xml | 10 ++++++++--
3 files changed, 34 insertions(+), 3 deletions(-)
diff --git
a/commons-numbers-rootfinder/src/main/java/org/apache/commons/numbers/rootfinder/BrentSolver.java
b/commons-numbers-rootfinder/src/main/java/org/apache/commons/numbers/rootfinder/BrentSolver.java
index c9c7ffa4..565d5b4d 100644
---
a/commons-numbers-rootfinder/src/main/java/org/apache/commons/numbers/rootfinder/BrentSolver.java
+++
b/commons-numbers-rootfinder/src/main/java/org/apache/commons/numbers/rootfinder/BrentSolver.java
@@ -222,9 +222,14 @@ public class BrentSolver {
fc = fa;
}
- final double tol = 2 * eps * Math.abs(b) + t;
+ // NUMBERS-211: Allow convergence at machine tolerance
+ final double tol = Math.max(2 * eps * Math.abs(b) + t,
Math.ulp(b));
final double m = 0.5 * (c - b);
+ // |fb| <= |fc| and they have opposite signs (bracket the root).
+ // If a line is drawn between them, the midpoint will be
+ // of the opposite sign (or zero). If the distance to the midpoint
is
+ // less than the tolerance, b is within tolerance to the root.
if (Math.abs(m) <= tol ||
equalsZero(fb)) {
return b;
diff --git
a/commons-numbers-rootfinder/src/test/java/org/apache/commons/numbers/rootfinder/BrentSolverTest.java
b/commons-numbers-rootfinder/src/test/java/org/apache/commons/numbers/rootfinder/BrentSolverTest.java
index 504af762..981edad2 100644
---
a/commons-numbers-rootfinder/src/test/java/org/apache/commons/numbers/rootfinder/BrentSolverTest.java
+++
b/commons-numbers-rootfinder/src/test/java/org/apache/commons/numbers/rootfinder/BrentSolverTest.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.numbers.rootfinder;
+import java.time.Duration;
import java.util.Locale;
import java.util.function.DoubleUnaryOperator;
@@ -392,4 +393,23 @@ class BrentSolverTest {
() -> solver.findRoot(func1, lo, hi));
Assertions.assertEquals(String.format(SolverException.TOO_LARGE, lo,
hi), ex2.getMessage());
}
+
+ /**
+ * Test that the algorithm terminates when further iteration is not
possible as the
+ * bracket is within machine accuracy of the root.
+ * See NUMBERS-211.
+ */
+ @Test
+ void testConvergenceToMachineAccuracy() {
+ // Degenerate accuracies below the resolution of double: the bracket
+ // shrinks to the adjacent doubles around sqrt(2) and can then never
+ // satisfy |0.5 * (c - b)| <= tol with tol = 1e-30. The solver must
+ // detect this and return instead of iterating forever.
+ final BrentSolver solver = new BrentSolver(0, 1e-30, 0);
+ final DoubleUnaryOperator f = x -> x * x - 2;
+ final double x =
Assertions.assertTimeoutPreemptively(Duration.ofMillis(500),
+ () -> solver.findRoot(f, 1, 2), "Iterated too long");
+ final double expected = Math.sqrt(2.0);
+ Assertions.assertEquals(expected, x, Math.ulp(expected));
+ }
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index b1eb79ff..2b9c2d5f 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -56,11 +56,17 @@ If the output is not quite correct, check for invisible
trailing spaces!
<release version="1.4" date="TBD" description="
New features, updates and bug fixes.
">
+ <action dev="aherbert" type="fix" due-to="Security scan, Alex Herbert"
issue="NUMBERS-211">
+ "BrentSolver": Modifies the convergence tolerance to at least 1 unit
in the last
+ place (ULP) of the current best solution. Avoids an infinite loop when
the
+ relative accuracy is zero and the configured absolute accuracy cannot
be achieved
+ due to machine precision.
+ </action>
<action dev="aherbert" type="fix" due-to="Security scan, Alex Herbert"
issue="NUMBERS-210">
"BrentSolver": Avoid non-convergence by validating the convergence
accuracies
are positive and finite. Throw an exception if a function evaluation
is NaN
- as this invalidates the bracket update step. Vaidate the initial
bracket [min, max]
- has finite values.
+ as this invalidates the bracket update step. Vaidate the initial
bracket
+ [min, max] has finite values.
</action>
<action dev="aherbert" type="fix" due-to="Security scan, Alex Herbert"
issue="NUMBERS-209">
"Trigamma": Avoid an infinite loop on large negative arguments. All
negative
