Free42 SOLVE: Better sign reversal detection

[Thomas Okken]

I didn't have anything planned today and so I decided to finally try to do something about the eternally open issue of SOLVE in Free42 failing to identify sign reversals.

To recap: the issue is with functions, like 1/x, where the solver may end up converging on a point where the function is always positive on one side of the point and always negative on the other, but is actually not continuous across that point. As long as the function always returns without error, SOLVE will return the value where the sign changes, as if it were a root, never reporting Sign Reversal.

I implemented logic to try to identify such sign reversals by keeping track of the difference between f(x1) and f(x2) as x1 and x2 approach the point where the function changes sign. If the difference between f(x1) and f(x2) gets larger three consecutive times right before x1 becomes equal to x2, Sign Reversal is reported.

(Of course none of this applies if SOLVE actually finds an x where the function returns exactly 0; this issue is to tell the difference between cases where the function never returns exactly 0 because of finite precision, and cases where the function actually has a vertical asymptote.)

The change will be in the next releases of Free42 and Plus42, but for now, I uploaded test builds of Free42 for Windows in case anyone is interested in checking out this fix, here.

[Albert Chan]

What is Free42 algorithm for solving for roots?

I guessed SIGN-REVERSAL meant no root between x1 and x2 ... is it right?
Is there an example, where test-build catch SIGN-REVERSAL, but old release did not ?

[Thomas Okken]

Free42 / Plus42 SOLVE uses Ridders' method, falling back on the secant method or bisection if necessary.

The old code would only report Sign Reversal if the function returned errors that prevented narrowing down the search interval any further.

One test case that shows the difference between not having the latest change and having it is x/(x^2-6)-1 with starting values 2.3 and 2.7. This is an example from the HP-42S Programming Examples and Techniques book (page 116), specifically to demonstrate SOLVE returning Sign Reversal.

[Thomas Okken]

The reason this is tricky is that you don't want to show Sign Reversal for functions that never return exactly 0 because of finite precision, without actually being discontinuous, like

00 { 22-Byte Prgm }
01▸LBL "LIN"
02 MVAR "X"
03 RCL "X"
04 2
05 ×
06 3
07 ENTER
08 1/X
09 ×
10 -
11 END

[johanw]

The commit is now 10 days old, is any further testing required before 3.0.16 that we can help with?

[Thomas Okken]

More testing is always better, of course!

I'll probably release 3.0.16 sometime in November. I'm still debating whether to do any further improvements before then. I don't have any open bugs at the moment but there's a long list of possible improvements, some small, some not so small...