_Bisect
Description
_Bisect finds a root of a function between two points where the function has opposite signs, by repeatedly halving the interval (100 times by default, far past full precision).
Used by: PolyInv
Source Code
_Bisect = LAMBDA(
fn, // LAMBDA(x): function whose sign changes between lo and hi
lo, // one end of the bracket
hi, // the other end of the bracket
[iters], // number of halvings (default 100)
LET(
iters, IF(ISOMITTED(iters), 100, iters),
s_lo, SIGN(INDEX(fn(lo), 1, 1)),
ends, REDUCE(
HSTACK(lo, hi),
SEQUENCE(iters),
LAMBDA(acc, i_,
LET(
a_, INDEX(acc, 1, 1),
b_, INDEX(acc, 1, 2),
m_, (a_ + b_) / 2,
IF(SIGN(INDEX(fn(m_), 1, 1)) = s_lo, HSTACK(m_, b_), HSTACK(a_, m_))
)
)
),
(INDEX(ends, 1, 1) + INDEX(ends, 1, 2)) / 2
)
);