TVM solve for interest rate, revisited

[Albert Chan]

Testing for f = 0 (or changed sign), with *guaranteed* root, is good to have.
However, it is possible eps too small to change iterated rate.
This cause f unable to improve (toward 0), giving false negative result.

lua> find_rate(300,-1000,0,10002) -- ???
nil
lua> g = iter_i(300,-1000,0,10002) -- to see what's under the hood
lua> for i=1,9 do print(g()) end

Code:

0.005469683722009796    0.005469683722009796    30.006666666666668
0.007458966325604198    0.001989282603594402    6.432723957167589
0.007702303993544976    0.00024333766794077768  0.636567520936282
0.007705485339429362    3.1813458843856375e-006 0.008111326572127986
0.007705485872366111    5.329367491485611e-010  1.3583484603785223e-006
0.007705485872366127    1.5332655972388135e-017 3.907985046680551e-014
0.007705485872366127    3.484694539179127e-019  8.881784197001252e-016
0.007705485872366127    3.484694539179127e-019  8.881784197001252e-016

(i + eps) rounding errors caused iteration not to advance, f unable to change sign.

For above example, relative to i, 1/2 ULP = 0x1p-61 ≈ 4.337e-19 ≈ 1.25 eps
(that's in a perfect world; i uncertainty is likely > 1/2 ULP)

It is not a guarantee, but if rate converged, we should also consider solution found.

Revised find_rate

Code:

function find_rate(n,pv,pmt,fv,BEGIN,i0)
    if BEGIN then pv, fv = pv+pmt, fv-pmt end
    local g = iter_i(n,pv,pmt,fv,i0)
    if i0 then g() end  -- throw away iteration
    local i,eps,f = g() -- 1-sided convergence
    repeat
        local f0 = f
        i,eps,f = g()
        if f*f0 <= 0 then return i,eps end
    until not (abs(f0) > abs(f))
    return i-eps, (i == i-eps*0.01)
end

Code assumed about 15 digits matched "converged".
Last iteration, with |f| not improving, throw away.

lua> find_rate(300,-1000,0,10002) -- revised version
0.007705485872366127      true