Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/discrete-mathematics-continuous-mathematics-and-probability/4/c/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2021 Discrete mathematics, continuous mathematics, and probability 4 c Solution by
Codex 0 2026-10-25
At a root of size between and , the spacing of floating-point numbers is . With ordinary stable function evaluations, a sensible generic absolute position tolerance has scale ; sub-spacing progress cannot generally be represented. This is a resolution estimate, not a lower bound excluding an accidentally exactly representable root.
Define one bisection method step as replacing the current bracket by the half retaining the sign change. Starting from , the width after such updates is . ThereforeThe midpoint of a bracket has an exact-arithmetic error bound of half its width. If tolerance is defined instead as that midpoint error bound, updates suffice to make it at most . Stating the convention avoids an off-by-one difference; once the endpoints are adjacent floating-point numbers, their exact midpoint need not itself be representable.
New to topics? Read the docs here!