bug#58929: 29.0.50; Calc: finding roots utpn doesn't work as advertised

[Matt Armstrong]

Eli Zaretskii <eliz@gnu.org> writes:

>> Cc: 58929@debbugs.gnu.org
>> From: Mattias Engdegård <mattiase@acm.org>
>> Date: Thu, 3 Nov 2022 09:53:02 +0100
>> 
>> Of course an actual numerical analyst would know immediately what to do. Is 
>> there one in the audience?
>
> I have good experience from using this technique:
>
>   
> https://www.researchgate.net/publication/226830173_On_the_Structure_of_Zero_Finders
>
> It employs a hybrid method that doesn't need derivatives (but is
> almost as fast as Newton).  However, its main advantage (which is a
> huge one in some real-life situations) is that the structure of the
> algorithm allows the caller to make arbitrary modifications to the
> approximations that the algorithm produces, and in general have
> complete control on the iterations' process.  In particular, one can
> easily deal with situations where the root approximation goes out of
> the expected range, or lands in the area where the function doesn't
> behave well enough.

Interesting.  I like how that algorithm attempts to "do its best" when
given a single guess point, then adapts to bisection if it happens to
find an opportunity and need.  Calc's manual suggests that its "root"
function attempts to do the same, opening a window to use this other
approach.

I'm not sure how to expose the root finding "loop" in calc's UI, but
exposing it calc's lisp level interface would be a natural thing to do.

https://en.wikipedia.org/wiki/ITP_method also looks like an interesting
twist on the bisection/secant method.  I have no personal experience
with it, and on Wikipedia I always wonder if pages like this are
reflective of a true utility or merely the ambitions of the paper's
authors!  This function needs function values that are opposite in sign
before it is useful.  It might be possible to incorporate it into the
approach Eli linked to, but that method claims to be almost as fast as
Newton's method in most cases so it may not need the improvement.

I arrived here because I wanted to use calc to compute 95th and 99th
percentile confidence intervals of some benchmarking results using the
Student's t-distribution.  I have figured this out now, but it has been
more difficult than I anticipated, and the manual's over-promise with
respect to "find the root, any guess works" sent me on a long tangent
trying to figure out what I had done wrong.  That said, my background in
this area is weak, so I don't think I am the right person to improve
Emacs' root finding implementation.

The patch I sent previously, with my (hopefully) useful suggestions in
the user manual, is probably the end of my useful contribution here.