Finite-budget interval isolation for smooth scalar roots

Input a $C^1$ function $f:U\to \mathbb{R}$ on an open interval $U$, a nonempty finite dyadic interval $X_0\subset U$, valid interval range and derivative enclosures on every queried subinterval, an exactly represented rational minimum width $\eta >0$, and a nonnegative integer box budget $B\ge 0$. The two enclosure evaluators must contain $f(I)$ and $f^{\mathrm{\prime }}(I)$, respectively; non-finite results cannot certify a root or its absence.

Initialize a queue with $X_0$. While the queue is nonempty and fewer than $B$ boxes have been processed, remove its first interval $I$ and call Finite-budget scalar interval Newton root certification on $I$ with update budget $2$ and the supplied evaluators. If it returns "root-free", record $I$ as excluded. If it returns "unique-root", record $I$ as a certified box. Otherwise, if the width of $I$ exceeds $\eta$, bisect at its midpoint and append the two closed halves to the queue. If the width is at most $\eta$, record $I$ as unresolved. When the box budget is exhausted, append every remaining queued interval to the unresolved list.

Return the excluded boxes, certified boxes, unresolved boxes, and processed-box count. The status is "complete" exactly when the unresolved list is empty; otherwise it is "inconclusive". Certified boxes may share a bisection endpoint. A strict interval-Newton inclusion places its root in the interior of the scalar call's box. The scalar procedure can also certify after contracting to an exact singleton; in that case the smooth isolator records the original processed interval, whose root may be at an endpoint. Unresolved boxes prevent any all-roots conclusion.