[lmi-commits] [lmi] master 83a7960 5/8: Eliminate a side-effect guarantee [280]

[Greg Chicares]

branch: master
commit 83a79602039dbb0dd99cd5436b2400cd3131d11a
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Eliminate a side-effect guarantee [280]
    
    Expunged this feature, resolving a marked defect.
    
    UL solves generate a complete set of ledger values for each iterand.
    The last two iterands are the best upper and lower bounds, to within
    the precision specified by the 'decimals' argument. One of those is
    selected according to the 'root_bias' argument, each approximately
    half the time, so it had been hoped that the ledger values produced by
    the last iteration could be used, saving about half an iteration per
    solve. However, that hope was in vain, as the AccountValue::Solving
    flag has side effects.
---
 ihs_avsolve.cpp | 11 ++++-------
 solve.cpp       | 11 ++++-------
 zero.hpp        | 49 ++++++-------------------------------------------
 zero_test.cpp   | 36 +++++++++++++++++++++++-------------
 4 files changed, 37 insertions(+), 70 deletions(-)

diff --git a/ihs_avsolve.cpp b/ihs_avsolve.cpp
index 3adca83..81ae801 100644
--- a/ihs_avsolve.cpp
+++ b/ihs_avsolve.cpp
@@ -439,7 +439,6 @@ currency AccountValue::Solve
         ,bias
         ,decimals
         ,solve_helper
-        ,false
         ,os_trace
         );
 
@@ -455,12 +454,10 @@ currency AccountValue::Solve
         }
 
     // The account and ledger values set as a side effect of solving
-    // aren't necessarily what we need, for two reasons:
-    //   - find_root() need not return the last iterand tested; and
-    //   - the 'Solving' flag has side effects.
-    // The first issue could be overcome easily enough in find_root(),
-    // but the second cannot. Therefore, the final solve parameters
-    // are stored now, and values are regenerated downstream.
+    // aren't generally the same as those shown on the illustration
+    // because the 'Solving' flag has side effects. Therefore, the
+    // final solve parameters are stored now, and actual values are
+    // freshly generated downstream.
 
     Solving = false;
     currency const solution_cents = round_minutiae().c(solution.first);
diff --git a/solve.cpp b/solve.cpp
index 3216232..53fbe74 100644
--- a/solve.cpp
+++ b/solve.cpp
@@ -328,7 +328,6 @@ currency AccountValue::Solve()
         ,Bias
         ,Decimals
         ,SolveFn
-        ,false
         ,status()
         );
     if(root_not_bracketed == Solution.second)
@@ -338,12 +337,10 @@ currency AccountValue::Solve()
         }
 
     // The account and ledger values set as a side effect of solving
-    // aren't necessarily what we need, for two reasons:
-    //   - find_root() need not return the last iterand tested; and
-    //   - the 'Solving' flag has side effects.
-    // The first issue could be overcome easily enough in find_root(),
-    // but the second cannot. Therefore, the final solve parameters
-    // are stored now, and values are regenerated downstream.
+    // aren't generally the same as those shown on the illustration
+    // because the 'Solving' flag has side effects. Therefore, the
+    // final solve parameters are stored now, and actual values are
+    // freshly generated downstream.
 
     Solving = false;
 
diff --git a/zero.hpp b/zero.hpp
index 2495894..53321cb 100644
--- a/zero.hpp
+++ b/zero.hpp
@@ -126,22 +126,6 @@ typedef std::pair<double,root_validity> root_type;
 /// hypothetical unrounded return value r, f(r) and f(round(r)) might
 /// easily have different signs.
 ///
-/// Often the function f is expensive to evaluate and has important
-/// side effects. For instance, solving for level premium to endow
-/// produces yearly account values as a side effect. With the original
-/// algorithm, those values may correspond either to the upper or the
-/// lower bound, and thus not necessarily to the zero returned. To
-/// obtain the correct side effects, the caller would have to evaluate
-/// the function again--unconditionally, because it doesn't know which
-/// final bound was returned. Whenever guarantee_side_effects is set to
-/// a non-default value of true, this implementation guarantees correct
-/// side effects by reevaluating the function iff necessary.
-///
-/// TODO ?? Expunge this feature?
-/// However, at least with our current implementation of iterative
-/// solves, 'guaranteed' side effects are invalidated by our use of the
-/// 'Solving' mode flag.
-///
 /// Brent states a requirement that the ordinates corresponding to the
 /// a priori bounds (abscissa arguments) have different signs, but his
 /// algorithm does not test that requirement. This implementation does
@@ -160,17 +144,7 @@ typedef std::pair<double,root_validity> root_type;
 /// the main loop is executed on the first pass, so that the branches
 /// in the algol original can be rewritten in a structured way.
 ///
-/// Note 1. In order to guarantee side effects, the value of the last
-/// evaluated iterand is stored. It must equal either b or c, depending
-/// on whether b and c were swapped. It might be triflingly faster to
-/// maintain a 'swapped' flag, but that would make it harder to see at
-/// a glance whether the code is correct because the initialization
-/// logic would have to be considered as well as the evaluation at the
-/// end of the loop. Alternatively, one might preserve distinct copies
-/// of external state embodying side effects for each of b and c, but
-/// that seems wasteful of space and wouldn't work with singletons.
-///
-/// Note 2. Here, Brent observes that one might return 0.5 * (b + c),
+/// Note 1. Here, Brent observes that one might return 0.5 * (b + c),
 /// equivalent to b + m, but that b is probably a much better
 /// approximation, so he returns b as soon as the condition
 ///   !(0.0 != fb && std::fabs(m) <= tol)
@@ -219,11 +193,11 @@ typedef std::pair<double,root_validity> root_type;
 /// original implementation in the bias_none case; to do otherwise
 /// would violate the principle of least astonishment.
 ///
-/// Note 3. Brent points out that this division is safe because
+/// Note 2. 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
+/// Note 3. 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
@@ -237,7 +211,6 @@ root_type decimal_root
     ,root_bias       bias
     ,int             decimals
     ,FunctionalType& f
-    ,bool            guarantee_side_effects = false
     ,std::ostream&   iteration_stream       = null_stream()
     )
 {
@@ -279,7 +252,6 @@ root_type decimal_root
             << std::endl
             ;
         }
-    double last_evaluated_iterand = b; // Note 1.
     if(0.0 == fb)
         {
         return std::make_pair(b, root_is_valid);
@@ -311,7 +283,7 @@ root_type decimal_root
             }
         double tol = 2.0 * epsilon * std::fabs(b) + t;
         double m = 0.5 * (c - b);
-        if(0.0 == fb || std::fabs(m) <= tol) // Note 2.
+        if(0.0 == fb || std::fabs(m) <= tol) // Note 1.
             {
             if
                 (   bias_none   == bias
@@ -319,18 +291,10 @@ root_type decimal_root
                 ||  bias_higher == bias && 0.0 <= fb
                 )
                 {
-                if(guarantee_side_effects && last_evaluated_iterand != b)
-                    {
-                    f(b);
-                    }
                 return std::make_pair(b, root_is_valid);
                 }
             else if(std::fabs(m) <= 2.0 * epsilon * std::fabs(c) + t)
                 {
-                if(guarantee_side_effects && last_evaluated_iterand != c)
-                    {
-                    f(c);
-                    }
                 return std::make_pair(c, root_is_valid);
                 }
             }
@@ -342,7 +306,7 @@ root_type decimal_root
         else
             {
             double p, q;
-            double s = fb / fa; // Note 3.
+            double s = fb / fa; // Note 2.
             if(a == c)
                 {
                 // Linear interpolation.
@@ -395,7 +359,7 @@ root_type decimal_root
             }
         b = round_(b);
 
-        if(b == a) // Note 4.
+        if(b == a) // Note 3.
             {
             fb = fa;
             }
@@ -406,7 +370,6 @@ root_type decimal_root
         else
             {
             fb = static_cast<double>(f(b));
-            last_evaluated_iterand = b;
             if(iteration_stream.good())
                 {
                 iteration_stream
diff --git a/zero_test.cpp b/zero_test.cpp
index c29d0b8..6642ad4 100644
--- a/zero_test.cpp
+++ b/zero_test.cpp
@@ -72,14 +72,22 @@ double e_function(double z)
     return std::log(z) - 1.0;
 }
 
+// A stateful function object.
+//
+// Commented-out tests below would require that the final state equal
+// the root returned by decimal_root(). Those two tests are unlikely
+// both to succeed, because decimal_root() returns an iterand chosen
+// according to its enum root_bias argument rather than the last
+// iterand tested. They exist only for this didactic purpose.
+
 struct e_functor
 {
     double operator()(double z)
         {
-        value = z;
+        e_state = z;
         return std::log(z) - 1.0;
         }
-    double value;
+    double e_state;
 };
 
 struct e_nineteenth
@@ -125,29 +133,31 @@ int test_main(int, char*[])
     r = decimal_root(0.1, 1.0, bias_none, 9, e);
     LMI_TEST(root_not_bracketed == r.second);
 
-    // Test guaranteed side effects.
+    // Test different biases.
 
     // Because the base of natural logarithms is transcendental,
     // Brent's algorithm must terminate with distinct upper and lower
-    // bounds.
+    // bounds: neither can equal the unrepresentable true value.
 
-    r = decimal_root(0.5, 5.0, bias_lower, 9, e, true);
+    r = decimal_root(0.5, 5.0, bias_lower, 9, e);
     LMI_TEST(root_is_valid == r.second);
     double e_or_less = r.first;
-    r = decimal_root(0.5, 5.0, bias_higher, 9, e, true);
+    LMI_TEST(e_or_less < std::exp(1.0));
+//  LMI_TEST(e.e_state < std::exp(1.0)); // Not necessarily true.
+
+    r = decimal_root(0.5, 5.0, bias_higher, 9, e);
     LMI_TEST(root_is_valid == r.second);
     double e_or_more = r.first;
+    LMI_TEST(std::exp(1.0) < e_or_more);
+//  LMI_TEST(std::exp(1.0) < e.e_state); // Not necessarily true.
+
     LMI_TEST(e_or_less < e_or_more);
 
-    r = decimal_root(0.5, 5.0, bias_lower, 9, e, true);
+    r = decimal_root(0.5, 5.0, bias_none, 9, e);
     LMI_TEST(root_is_valid == r.second);
-    LMI_TEST(r.first < std::exp(1.0));
-    LMI_TEST(e.value < std::exp(1.0));
+    double e_more_or_less = r.first;
 
-    r = decimal_root(0.5, 5.0, bias_higher, 9, e, true);
-    LMI_TEST(root_is_valid == r.second);
-    LMI_TEST(std::exp(1.0) < r.first);
-    LMI_TEST(std::exp(1.0) < e.value);
+    LMI_TEST(e_more_or_less == e_or_less || e_more_or_less == e_or_more);
 
     // Various tests--see macro definition.