[lmi-commits] [lmi] odd/brent b07c9d3 03/11: Experimentally suppress secant technique

[Greg Chicares]

branch: odd/brent
commit b07c9d3710dddb9cabbbcf839ae7412df998d568
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Experimentally suppress secant technique
    
    Using bisection whenever the secant technique would have been used,
    causing Brent's method to take the same number of iterations as
    Chandrupatla's, for the (x-1.7)^17 example. This is not an improvement
    in the general case; it simply demonstrates that a preference for
    bisection underlies the ostensible superiority of Chandrupatla's method
    in the last graph here:
      https://www.embeddedrelated.com/showarticle/855.php
    and in Scherer's Fig. 6.12 (which, comparably, finds a zero of x^25).
    For Scherer's Fig. 6.11, this distortion of Brent's method takes even
    fewer iterations that Chandrupatla's, which uses IQI a few times.
    
    Thus, for two of Scherer's three graphs, bisection is optimal, while for
    the third, Brent's method is faster. His conclusion (page 97) that
    | Chandrupatlas’s method is more efficient than Dekker’s and Brent’s,
    | especially for higher order roots (Figs.6.10,6.11,6.12)
    is not strongly supported by the evidence he gives.
    
    This experimental change does not transform Brent's into Chandrupatla's
    method. Chandrupatla uses only {bisection, IQI} and always retains three
    points so that IQI can always be attempted. Brent maintains up to three
    distinct points:
      b, the current best approximation
      c, such that f(c) and f(b) have opposite sign (if nonzero)
      a, generally the previous value of b
    but when b and c must be swapped to maintain those invariants, he sets
    a = c, in effect discarding the old a, and uses the secant technique.
    It is impractical to make one last incremental change to Brent's method
    that would retain the old a value, because breaking the invariants above
    causes it to stop working correctly due to his careful arrangement of
    dependent local variables to avoid numerical errors.
---
 zero.hpp | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/zero.hpp b/zero.hpp
index f7b8525..1df6d75 100644
--- a/zero.hpp
+++ b/zero.hpp
@@ -373,9 +373,6 @@ root_type decimal_root
                 technique = interpolate_linear;
                 p = 2.0 * m * s;
                 q = 1.0 - s;
-                // NEVER USE SECANT ?
-//                  technique = interpolate_bisection1;
-//                  d = e = m;
                 }
             else
                 {
@@ -449,6 +446,11 @@ os_trace << " chandrupatla..." << std::endl;
                 {
 //std::cout << cond_c << cond_b << cond_0 << std::endl;
                 d = p / q;
+                if(interpolate_linear == technique) // Suppress secant 
technique
+                    {
+                    technique = interpolate_bisection1;
+                    d = e = m;
+                    }
                 if(interpolate_inverse_quadratic == technique && !cond_c)
                     {
 #if 1
@@ -615,6 +617,11 @@ int j = 0;
                     {
                     d = p / q;
                     }
+                if(interpolate_linear == technique) // Suppress secant 
technique
+                    {
+                    technique = interpolate_bisection1;
+                    d = e = m;
+                    }
                 }
             else
                 {