[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lmi-commits] [lmi] master d2dcbf8 15/23: Reduce complexity
From: |
Greg Chicares |
Subject: |
[lmi-commits] [lmi] master d2dcbf8 15/23: Reduce complexity |
Date: |
Tue, 27 Jul 2021 21:59:53 -0400 (EDT) |
branch: master
commit d2dcbf860619f49ca4cba294c1820c26346cdc38
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>
Reduce complexity
When rounding was performed inside the root-finding function, successive
iterates were sometimes identical (after rounding), in which case it was
possible to avoid some redundant evaluations. That benefit doesn't
justify the extra complexity (which has already been removed), though it
may be possible to avoid redundant evaluations in a less obtrusive way.
The system-test suite (which includes some proprietary products) has
388 solves, summarized as follows:
evaluations max mean sample-std-dev commit date
7212 63 18.6 6.94 d6bd8029e 20210718T1630Z
7501 75 19.3 7.36 this today
so these simplifications make all measures slightly worse.
---
zero.hpp | 50 +++++++++++---------------------------------------
1 file changed, 11 insertions(+), 39 deletions(-)
diff --git a/zero.hpp b/zero.hpp
index 133154a..6349598 100644
--- a/zero.hpp
+++ b/zero.hpp
@@ -193,7 +193,7 @@ inline double binary64_midpoint(double d0, double d1)
/// Return a zero z of a function f within input bounds [a,b].
///
-/// Preconditions: bounds are distinct after rounding; and either
+/// Preconditions: bounds are distinct; and either
/// 0.0 == f(a), or
/// 0.0 == f(b), or
/// f(a) and f(b) have opposite signs;
@@ -260,15 +260,6 @@ inline double binary64_midpoint(double d0, double d1)
///
/// GWC modifications
///
-/// Brent's original algorithm returns unrounded values. To support
-/// financial applications that traffic in rounded currency values,
-/// iterands are optionally rounded before each function evaluation.
-/// Rounding must be performed within the root-finding algorithm: for
-/// an unrounded return value r, f(r) and f(round(r)) might easily
-/// have different signs. The default rounding function returns its
-/// argument unchanged, so this implementation remains suitable for
-/// the unrounded case.
-///
/// Brent's original algorithm strives to return the closest value to
/// a true root (within a given tolerance). Especially for currency
/// values, it may be necessary to find the least or greatest value
@@ -351,13 +342,6 @@ inline double binary64_midpoint(double d0, double d1)
/// Note 3. Brent points out that this division is safe because
/// 0 < |f(b)| <= |f(a)|
/// whenever this line is executed.
-///
-/// Note 4. Each iterand is rounded, so it might equal an iterand that
-/// has already been evaluated. In that case, the known value is used,
-/// because evaluation is assumed to be costly, and in practice one
-/// bound stays fixed to within rounding (for instance, at the edge of
-/// a discontinuity) often enough that it is worthwhile to avoid
-/// superfluous reevaluation.
template<typename FunctionalType>
root_type lmi_root
@@ -593,37 +577,25 @@ root_type lmi_root
b -= tol;
}
- if(b == a) // Note 4.
- {
- fb = fa;
- }
- else if(b == c)
- {
- fb = fc;
- }
- else
- {
- fb = static_cast<double>(f(b));
- ++n_eval;
- expatiate();
- }
+ fb = static_cast<double>(f(b));
+ ++n_eval;
+ expatiate();
}
}
/// Return a rounded zero z of a function f within input bounds [a,b].
///
-/// Brent's original algorithm returns a zero z of the function f in
+/// Brent's algorithm returns a zero z of the function f in
/// [bound0 bound1]
/// (a,b) to within a tolerance
/// 6ϵ|z| + 2t
-/// where t is an argument. For financial applications, the tolerance
-/// is often one-sided, so that f(z) must be strictly greater than or
-/// less than zero, and the tolerance is more conveniently expressed
-/// as a number of decimals. An adjustment is made for the constant
-/// factor in Brent's t term, so that this implementation's tolerance
-/// becomes
+/// where t is an argument. For financial applications that traffic in
+/// rounded currency values, the tolerance is often one-sided, so that
+/// f(z) must be strictly greater than or less than zero; and the
+/// tolerance is a function of the number of decimals to which values
+/// are rounded. Thus, the tolerance becomes
/// 6ϵ|z| + 10^(-decimals)
-/// instead.
+/// for this overload.
template<typename FunctionalType>
root_type decimal_root
- [lmi-commits] [lmi] master e59df26 14/23: Refactor, (continued)
- [lmi-commits] [lmi] master e59df26 14/23: Refactor, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 8f2f355 19/23: Augment unit tests; record some observations, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master a259cb6 05/23: Calculate maximum possible number of iterations, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master d0a65c2 04/23: Demonstrate that Brent's δ can be almost arbitrarily small, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 548f9ab 06/23: Document known shortcomings of a unit-testing helper, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 19a4a3a 03/23: For now at least, trace solves in regression test, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 04c58eb 09/23: Count iterations and evaluations separately, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master bbf2517 10/23: Use signum() where a signum function is wanted, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master e08be34 12/23: Improve a unit test, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 02dde17 13/23: Avoid catastrophic cancellation, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master d2dcbf8 15/23: Reduce complexity,
Greg Chicares <=
- [lmi-commits] [lmi] master e93ca8f 17/23: Demonstration, for immediate reversion, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 4500338 22/23: Simplify, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 2ad4944 20/23: Record some more observations--no files changed, Greg Chicares, 2021/07/27
- [lmi-commits] [lmi] master 028b454 23/23: Find any root with only 64 function evaluations, Greg Chicares, 2021/07/27