Exponential sign bracketing (source code)

= Exponential sign bracketing

<Exponential sign bracketing> finds an <integer interval> with opposite endpoint signs before <sign-bracketing binary search>. Suppose $f$ is defined on nonnegative <integers>, its signs can be evaluated exactly, $f(0)<0$, and $f(k)>0$ for all sufficiently large <integers> $k$. Test $1,2,4,\ldots$. An exact zero can be returned immediately; otherwise stop at the first positive endpoint $2^t$ and retain the preceding negative endpoint, or zero when $t=0$.

Excluding the already known evaluation at zero, this takes $t+1$ endpoint tests. For $t\geq1$, the final <integer interval> is $[2^{t-1},2^t]$, of width $2^{t-1}$. Repeated midpoint tests preserving opposite endpoint signs take $t-1$ further tests to reach adjacent <integers>, unless an exact zero is found earlier. For $t=0$, $[0,1]$ is already adjacent.

No <monotonicity> is needed to preserve opposite endpoint signs, though other crossings may be skipped. Adjacent opposite signs do not imply an <integer root>; for $f(k)=2k-1$, neither endpoint of $[0,1]$ is a root. A real-valued extension requires <continuity> to infer a real root by the <intermediate value theorem>. A machine implementation must handle <integer overflow> and unreliable <floating-point arithmetic>; mathematical termination does not ensure representable endpoints.