[
https://issues.apache.org/jira/browse/NUMBERS-211?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18106398#comment-18106398
]
Alex Herbert edited comment on NUMBERS-211 at 8/20/26 6:26 PM:
---------------------------------------------------------------
There are at least two options to fix this issue:
# Add a maximum number of iterations to the Brent solver. The algorithm should
converge within (log2((hi - lo) / tol))^2 iterations (Brent, 2002). Using (hi -
lo) as the full range of a double, and tol as Double.MIN_VALUE the number of
iterations is approximately 2^23. Any iteration beyond this number indicates
incorrectly configured convergence criteria and an exception can be raised.
# Update the convergence test between the two values closest to the root,
named b and c, to always use the maximum of the configured criteria, or 1 ULP
of the current best value. This allows a misconfigured solver (all convergence
accuracies set to zero) to return when the algorithm cannot possibly bring the
two values b and c closer together.
Inspection of the algorithm shows that the convergence test is computed as:
{noformat}
tol = 2 * relAcc * Math.abs(b) + absAcc
m = |0.5 * (c - b)|
test convergence:
m <= tol{noformat}
The tolerance is then used later in the same iteration to update b:
{noformat}
d = interpolation update step
if |d| > tol
b += d
elif m > 0:
b += tol
else:
b -= tol
{noformat}
If the interpolation step (d) is computed as zero then the algorithm can get
stuck where it cannot move b if the tolerance is zero.
Note that a test using:
{noformat}
tol = max(2 * relAcc * Math.abs(b) + absAcc, ulp(b)){noformat}
and the function f( x ) = x*x - 2 will converge in 7 iterations from an initial
bracket of [1, 2]. The alternative solution with throw an exception after 2^23
iterations.
was (Author: alexherbert):
There are at least two options to fix this issue:
# Add a maximum number of iterations to the Brent solver. The algorithm should
converge within (log2((hi - lo) / tol))^2 iterations (Brent, 2002). Using (hi -
lo) as the full range of a double, and tol as Double.MIN_VALUE the number of
iterations is approximately 2^23. Any iteration beyond this number indicates
incorrectly configured convergence criteria and an exception can be raised.
# Update the convergence test between the two values closest to the root,
named b and c, to always use the maximum of the configured criteria, or 1 ULP
of the current best value. This allows a misconfigured solver (all convergence
accuracies set to zero) to return when the algorithm cannot possibly bring the
two values b and c closer together.
Inspection of the algorithm shows that the convergence test is computed as:
{noformat}
tol = 2 * relAcc * Math.abs(b) + absAcc
m = |0.5 * (c - b)|
test convergence:
m <= tol{noformat}
The tolerance is then used later in the same iteration to update b:
{noformat}
d = interpolation update step
if |d| > tol
b += d
elif m > 0:
b += tol
else:
b -= tol
{noformat}
If the interpolation step (d) is computed as zero then the algorithm can get
stuck where it cannot move b if the tolerance is zero.
Note that a test using:
{noformat}
tol = max(2 * relAcc * Math.abs(b) + absAcc, ulp(b)){noformat}
and the function f(x) = x*x - 2 will converge in 7 iterations from an initial
bracket of [1, 2]. The alternative solution with throw an exception after 2^23
iterations.
> BrentSolver infinite loop when convergence is not possible
> ----------------------------------------------------------
>
> Key: NUMBERS-211
> URL: https://issues.apache.org/jira/browse/NUMBERS-211
> Project: Commons Numbers
> Issue Type: Bug
> Components: rootfinder
> Affects Versions: 1.3
> Reporter: Alex Herbert
> Priority: Minor
>
> The BrentSolver can be configured with convergence accuracies that are not
> possible to achieve. This situation occurs when the relative accuracy for the
> values is zero, and the absolute accuracy is smaller than the difference
> between the values at the root.
> An example is the function:
> {noformat}
> f(x) = x^2 - 2{noformat}
> The root is at x = sqrt(2). If the solver is created with a relative accuracy
> of zero and an absolute accuracy below the ULP of sqrt(2), e.g. 1e-30, then
> the convergence criteria cannot be met. The algorithm will infinite loop with
> the bracket at sqrt(2) and sqrt(2) + 1 ULP.
> Issue identified using a security scan.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
