Re: [lmi] [lmi-commits] odd/eraseme_error 69d06e9 10/10: Attempt to find a problem

[Greg Chicares]

On 2021-07-07 13:20, Vadim Zeitlin wrote:
> On Wed, 7 Jul 2021 11:52:14 +0000 Greg Chicares <gchicares@sbcglobal.net> 
> wrote:
> 
> GC> On 2021-07-07 11:17, Vadim Zeitlin wrote:
> GC> > On Wed,  7 Jul 2021 06:22:15 -0400 (EDT) Greg Chicares 
> <gchicares@sbcglobal.net> wrote:
> GC> > 
> GC> > GC> branch: odd/eraseme_error
> GC> [...]
> GC> > GC>     Attempt to find a problem
> GC> [...]
> GC> >  Is this hang reproducible? If so, I could try debugging it.
> GC> 
> GC> It's caused by a NaN.
> 
>  This is perfectly compatible with my almost superstitious fear of NaNs,
> but I wonder how is this possible then the commit message said that the
> function did return...

Mistakenly, I captured only illustration solves, but lmi_root() is also
used for other purposes. One of those other purposes is calculating IRR.
When I wrote a trace of IRR root-finding to a file, the following happened
(the leftmost column is line number in 'less'):

      1 Entering decimal_root()
      2 Entering lmi_root() line 252
      3 #eval            a           fa            b           fb            c  
         fc
      4   2 i           -1         -nan         1000   2.0005e+07            0  
          0
      5   2 j           -1         -nan         1000   2.0005e+07           -1  
       -nan
      6   3 L         1000   2.0005e+07         1000   2.0005e+07           -1  
       -nan
      7   4 Q         1000   2.0005e+07         1000   2.0005e+07           -1  
       -nan
      8   5 Q         1000   2.0005e+07         1000   2.0005e+07           -1  
       -nan
      9   6 Q         1000   2.0005e+07         1000   2.0005e+07           -1  
       -nan
     10   7 Q         1000   2.0005e+07         1000   2.0005e+07           -1  
       -nan
     11   8 Q         1000   2.0005e+07      999.999   2.0005e+07           -1  
       -nan
...ellipses omitted below; only selected lines are shown...
    103 100 Q       999.99  2.00048e+07       999.99  2.00048e+07           -1  
       -nan
   1000 997 Q      999.901   2.0003e+07        999.9   2.0003e+07           -1  
       -nan
  10000 9997 Q      999.001   1.9985e+07          999   1.9985e+07           -1 
        -nan
 100000 99997 Q      990.001   1.9805e+07          990   1.9805e+07           
-1         -nan
1000000 999997 Q      900.001   1.8005e+07          900   1.8005e+07           
-1         -nan
9999999 9999996 Q       0.0007      5016.76       0.0006      5014.76           
-1         -nan
10000000 9999997 Q       0.0006      5014.76       0.0005      5012.76          
 -1         -nan
10000003 10000000 Q       0.0003      5008.76       0.0002      5006.76         
  -1         -nan
10000004 10000001 Q       0.0002      5006.76       0.0001      5004.76         
  -1         -nan
10000005 10000002 Q       0.0001      5004.76            0      5002.76         
  -1         -nan
10000006 10000003 1           -0      5002.76         -0.5     -4997.24         
  -1         -nan
10000007 10000003 j           -0      5002.76         -0.5     -4997.24         
  -0      5002.76
10000008 10000004 L         -0.5     -4997.24      -0.2501         0.76         
  -0      5002.76
10000009 10000004 j         -0.5     -4997.24      -0.2501         0.76         
-0.5     -4997.24
10000010 10000005 L      -0.2501         0.76      -0.2502        -1.24         
-0.5     -4997.24
10000011 10000005 j      -0.2501         0.76      -0.2502        -1.24      
-0.2501         0.76
10000012 10000005 k      -0.2502        -1.24      -0.2501         0.76      
-0.2502        -1.24
10000013 Returning from lmi_root() line 360
10000014 Returning from decimal_root()

So it really does return. Eventually.

On page 48 of AfMWD, Brent constructs a function for which his method
requires 1600 function evaluations while Dekker's requires 10^12, and
comments "our point of view is that 1600 is a reasonable number, but
10^12 is not, for a computer program which attempts to evaluate a
function 10^12 times is almost certain to run out of time". I wanted
to hit Ctrl-C well before reaching 10^7 above.

His ALGOL lacks the defect shown above. How did he avoid it in 1972?
By writing the bisection block last in an if...else-if...else path.
Those old-time programmers were wise.