THE BISECTION METHOD bracket a sign change and halve until it is pinned
If a continuous function is negative at one end of an interval and positive at the other, a root must lie between — the intermediate value theorem guarantees it. Bisection checks the midpoint’s sign, keeps the half that still brackets the sign change, and repeats. Each step halves the uncertainty, so it is slow but cannot fail to converge — the one root-finder that always works.
THE TECHNIQUE one bit of the answer per step
Find √2 as the root of x² − 2 in [1,2]: negative at 1, positive at 2. Each halving fixes one more binary digit. Slide the iteration count and watch the bracket close on 1.41421356…: live demo
HISTORY & CREDIT intermediate value theorem; Bolzano 1817
“Bisection is too primitive to matter.” — no. Its guaranteed convergence and rock-solid robustness are exactly why hybrid solvers (Brent’s method, dart 152’s kin) fall back to it when the fast methods misbehave. It is the safety net under the clever root-finders. cited
ancient · halving-search to trap a value is folklore, older than any name. 1817 · Bernard Bolzano — a rigorous proof of the intermediate value theorem, the guarantee bisection rests on. modern · bisection is the fallback inside robust hybrids — Dekker (1969) and Brent (1973) combine it with the secant/inverse-quadratic methods for speed and safety.
Linear convergence, one bit per step: to pin a root to f64 precision (~52 bits) over a unit interval takes about 52 halvings — slow, but the error bound is known in advance, which the fast methods cannot promise. Bolzano 1817 (IVT)
RECOMMEND FOR I-13 the bracket closes, computed
The interval halving runs on the canonical compiler and closes on √2:
$ i13 run bisect.i13 # root of x^2-2 in [1,2], 40 halvings
root = 1.414213562372879 -- ~ sqrt(2) = 1.41421356237... (one binary digit per step)
Recommend: bisection is LIT and the robust root-finder for I-13 — verified it converges to √2 = 1.4142135624 as the root of x²−2 on [1,2] in 40 native-recursion halvings, each keeping the sign-changed half. It cannot fail where Newton (dart 026) or Halley (171) can diverge, so it is the safe default and the fallback a hybrid solver drops to. Pure f64 comparisons, bounded depth — the simplest thing that always works.