Interval arithmetic: how a plotter can prove where a curve is
Most graphing calculators find a curve by looking for places where something changes sign. That works almost always, and fails in a way you can’t see: some curves never change sign at all. Interval arithmetic fixes this by computing with whole ranges of numbers, which turns “probably no curve here” into a proof.
How implicit curves are usually drawn
To draw an equation like x² + y² = 9, a plotter rewrites it as F(x, y) = 0 with F = x² + y² − 9, then evaluates F on a grid of points. Where F is negative at one grid point and positive at its neighbour, the curve must pass between them, and the algorithm (usually a variant of marching squares) draws a short segment there. Join all the segments and you have the circle.
This is fast and it works for the overwhelming majority of equations. But it rests on one assumption: that the curve is where F changes sign.
Curves with no sign change
Square the left side: (x² + y² − 9)² = 0. Mathematically this is the same circle. But F is now never negative. It is zero on the circle and positive everywhere else. There is no sign change for the grid to detect, so a sign-change plotter draws nothing at all, with no warning.
The same blind spot hides isolated points (x² + y² = 0 is just the origin), curves where two branches touch, and very thin features that slip between grid points. These come up in real work: the set where a function has a double root, the boundary in an optimisation problem, or simply an equation someone typed in an unusual form.
Computing with ranges
Interval arithmetic, developed by Ramon Moore in the 1960s, replaces each number with an interval that is guaranteed to contain it, and defines arithmetic on intervals so that the guarantee is preserved:
- [a, b] + [c, d] = [a + c, b + d]
- [a, b] − [c, d] = [a − d, b − c]
- [a, b] × [c, d] = [the smallest, the largest] of ac, ad, bc and bd
- For a function like sin, the interval from its minimum to its maximum over [a, b], taking care of the peaks and troughs inside.
The key property is inclusion: if x is anywhere in X and y anywhere in Y, then F(x, y) is somewhere in the interval F(X, Y). So if F evaluated on a whole rectangle of the screen gives an interval that does not contain zero, then F is not zero anywhere in that rectangle, and the curve certainly does not pass through it. That is a proof, not a guess.
Drawing with proofs
Certified plotting uses this to sort the screen. Start with large blocks and evaluate F on each:
- If the interval excludes zero, the block contains no part of the curve. Discard it.
- Otherwise, split the block into four and repeat.
- Stop when a block is about one pixel. Any pixel still standing might contain the curve, so draw it.
Every pixel that is left blank has been proved empty, so the curve cannot be missing. Squared terms, touching points and thin features all survive, because the method never relies on a sign change. Jeff Tupper’s work on reliable graphing, published at SIGGRAPH in 2001 and behind the program GrafEq, showed how far this idea can be pushed.
The catch: overestimation
Interval arithmetic is always correct, but it can be pessimistic. Evaluate x − x on X = [0, 1] and you get [0 − 1, 1 − 0] = [−1, 1], although the true answer is exactly 0. The arithmetic doesn’t know the two x’s are the same number. This is called the dependency problem. It never produces a wrong answer, only a wider interval than necessary, which means a few extra pixels near the curve are kept that a perfect method would discard.
In practice this shows up as a slightly thick curve in places. Rewriting expressions so each variable appears fewer times, such as (x + 1)² instead of x² + 2x + 1, tightens the intervals, and subdividing further always helps, because the overestimation shrinks as the blocks get smaller.
How this calculator combines the two
Interval arithmetic is slower than sampling, and its curves are drawn pixel by pixel rather than as smooth lines. So the calculator uses both. The fast sign-change tracer draws every curve it can find as a smooth, anti-aliased line. Then, with certified mode on (the default), the interval method checks the whole screen and draws any pixels the tracer missed, which is exactly where the sign-change method was blind. You get smooth curves where they are easy and guaranteed curves where they are hard.
The same machinery shades inequalities exactly. For a region like y < sin(x) + cos(3y), blocks where the inequality certainly holds are filled in one go, blocks where it certainly fails are skipped, and only the boundary pixels are decided individually. Narrow slivers of the region can’t be lost between samples.
Beyond plotting
The same idea is used wherever a computer needs to prove something about a continuous function. Warwick Tucker used interval arithmetic in 2002 to prove that the Lorenz attractor exists, settling one of Stephen Smale’s problems for the 21st century. Thomas Hales’s proof of the Kepler conjecture on sphere packing relied on it too. It is the standard tool for turning floating-point computation into mathematics you can trust.
Try it: type (x^2 + y^2 - 9)^2 = 0 into the calculator, then switch certified curves off in the graph settings and watch the circle disappear.