Interval Arithmetic

EveryEvery number a computer stores as a float is, in general, already an approximation — Binary Representation and Computer Arithmetic covers why 0.1 has no exact binary representation at all. Interval arithmetic takes that fact seriously instead of hoping it doesn't matter: rather than track a single approximate number, track a guaranteed range — a lower and upper bound the true value is certain to fall within — and define arithmetic so the guarantee survives every operation, not just the input. Moore's original formulation, developed in the 1960s specifically to put rigorous error bounds around floating-point computation, remains the standard the field is built on¹ — this site's own geometric algebra material covers the core arithmetic definition and its extension to rigorous error analysis in more depth, in service of a different application (representing uncertainty as geometric objects called blades) than the more general computer-science uses covered here².

The Core Guarantee

AnAn interval [a, b] represents "the true value is somewhere in here, guaranteed" — not a probability distribution, not a best guess, an actual guarantee, provided the interval arithmetic itself is implemented correctly (which in practice means rounding the lower bound down and the upper bound up at every single operation, so accumulated floating-point error can only ever widen an interval, never silently shift it past a true bound). The basic operations are defined to preserve that guarantee automatically:

[a,b] + [c,d] = [a+c, b+d]
[a,b] - [c,d] = [a-d, b-c]
[a,b] * [c,d] = [min(ac,ad,bc,bd), max(ac,ad,bc,bd)]

Multiplication needs all four cross-products checked (rather than just a·c and b·d) because the sign of a or c can flip which combination actually produces the extreme value — [-2, 3] * [-1, 4], for instance, has its minimum at (-2)(4) = -8, not at any pairing of same-position endpoints.

Robust Root-Finding: Bisection versus Newton-Raphson

CalculusCalculus and Optimization covers Newton-Raphson's central weakness directly: near a function with more than one root, which root a given starting point converges to is chaotic — a fractal, unpredictable dependence on the starting point, not a smooth one. Interval bisection is the robust answer to the same root-finding problem, trading Newton-Raphson's speed for a genuine guarantee: given a starting interval known to contain a sign change (f(a) and f(b) have opposite signs, so by the intermediate value theorem a root lies somewhere between them), repeatedly bisect the interval and keep whichever half still contains a sign change.

f(x) = x^2 - 2, starting interval [1, 2]  (f(1)=-1, f(2)=2, sign change confirmed)
Bisect: midpoint 1.5, f(1.5)=0.25  ->  sign change is now in [1, 1.5]
Bisect: midpoint 1.25, f(1.25)=-0.4375  ->  sign change is now in [1.25, 1.5]
Bisect: midpoint 1.375, f(1.375)=-0.109  ->  sign change is now in [1.375, 1.5]
... halving the interval every step, until the midpoint itself can no longer
    be distinguished from either endpoint in double-precision floating point.
    Run for real, in genuine double-precision arithmetic: 52 bisections,
    terminating at the exact interval [1.414213562373095, 1.4142135623730951]
    -- a width of 2.220446049250313e-16, one ULP (unit in the last place)
    at this magnitude, and the two endpoints are adjacent representable
    doubles with nothing else expressible between them.

Unlike Newton-Raphson, bisection never diverges and never jumps to a different root — the sign-change invariant is checked and maintained at every step, so the interval can only ever shrink toward a genuine root, monotonically, at the cost of a fixed, much slower rate (one more correct binary digit per step, rather than roughly doubling correct digits per step). This is the same speed-versus-guaranteed-correctness trade-off that shows up constantly in numerical computing: a method with a certificate of correctness at every step is usually the slower method, and the right choice depends on whether an occasional catastrophic failure is an acceptable cost for the average-case speed-up.

What each method actually hands back at the end is a difference in kind, not just accuracy. Newton-Raphson solving for √2 returns a single float, and that number is already an approximation for two independent reasons: the iteration itself was stopped at some finite step rather than run forever, and the float type storing the answer can't represent √2 exactly regardless (see Binary Representation and Computer Arithmetic on why). Nothing about that returned float carries any indication of which of those two error sources dominates, or how large the true error actually is — it's a single point, presented with a false air of exactness. Interval bisection's natural output is different in kind: not a point but the narrowest interval the arithmetic can still guarantee contains the true root, shrunk until its width bottoms out at the smallest gap the machine's floating-point representation can express between two adjacent values. The worked run above shows exactly what that looks like in practice — [1.414213562373095, 1.4142135623730951] after 52 bisections, a one-ULP-wide interval that is a rigorous error bound, not an approximation with an error bound left to guess at separately. It's also a genuine cross-check on the method itself: the interval's upper endpoint is bit-for-bit identical to what Python's own built-in math.sqrt(2) — backed by the hardware's correctly-rounded square-root instruction — returns, so bisection's independently-derived guarantee and the hardware's own direct computation land on exactly the same answer.

Interval Trees: Searching a Collection of Intervals

AA different problem entirely: given a large collection of intervals (booked meeting-room time slots, genomic regions, valid ranges for a sensor reading), find every interval that overlaps a given query point or query interval — a stabbing query. Checking every stored interval one at a time is O(n) per query; an interval tree answers it in O(log n + k), where k is the number of results actually found, by augmenting a balanced binary search tree (organised by each interval's low endpoint) with an extra piece of information at every node: the maximum high endpoint anywhere in that node's whole subtree.

That augmentation is what makes the search fast: at any node, if the query point is greater than the node's subtree-max-high-endpoint, the entire subtree can be skipped — nothing in it could possibly overlap the query — without checking a single interval inside it individually. This is the same augmented-BST idea behind order-statistics trees and much of the rest of practical computational geometry: take an ordinary balanced tree (covered in general on Trees, Heaps, and Graphs) and store one extra summary value per node that lets whole subtrees be ruled out cheaply, rather than exhaustively searched³.

Querying point 27 against this tree: at the root, 27 < 30 (the root's own subtree max), so the right child must still be checked — [25,30] overlaps 27, a match. Descending left instead, at node L, 27 < 30 still holds only because of what's stored at L, but checking L's own children directly against 27 shows LL's max-high is 3 (27 > 3, entire LL subtree ruled out without touching it) while LR's max-high is 25 (27 > 25, ruled out too) — the whole left branch below L is eliminated in two cheap comparisons, with not one of its individual intervals ever examined.

Bounding Volumes in Ray Tracing and Collision Detection

TheThe same "rule out the impossible cheaply" idea reappears directly in computer graphics. Before testing whether a ray actually intersects a detailed 3D model's thousands of individual triangles, real-time and offline renderers first test the ray against a much cheaper enclosing shape — an axis-aligned bounding box is, precisely, three independent interval-arithmetic range checks, one per axis — and only descend into the expensive per-triangle test if the cheap box test passes. Organising a whole scene's bounding boxes into a tree (a bounding volume hierarchy) turns "does this ray hit anything in a scene of a million triangles" from a million individual tests into a small number of box tests followed by a handful of real ones — the exact same subtree-elimination principle an interval tree uses for stabbing queries, applied to 3D space instead of a 1D timeline. The transform pipeline these bounding boxes sit inside is covered on Computer Graphics and Transforms.

References