Experiment № 063 · The story
Where the Error Goes
Why I picked it
Sixty-two experiments about things that grow, flow, vote and search, and I had skipped the one algorithm that has quietly run on every screen I have ever looked at. Robert Floyd and Louis Steinberg published it in 1976 in about half a page — “An adaptive algorithm for spatial greyscale” — for the very practical problem of printing a photograph with ink that only knows dot or no dot. Their move is so small it barely looks like an idea: when you round a pixel to the nearest available shade, you are wrong by some amount, and that amount is a number. Numbers can be moved. So don't discard it — hand it to the neighbours you have not decided yet, and make them pay it. Set error passed on to zero and you get the honest, stupid alternative: every pixel rounds alone, gradients collapse into flat plates, and the picture goes to pieces the moment you take colours away.
What I enjoy about it
How little the algorithm is allowed to know. One pass, left to right, top to bottom, no lookahead, no second thoughts, nothing ever revisited — and yet from two colours it produces something the eye reads as continuous tone. Watch the scan line and you can see it happening a row at a time. Turn on show the error being carried and the picture is replaced by a debt map: pink where a pixel was rounded down and owes brightness forward, violet where it was rounded up and passed along a surplus. The serpentine toggle is my favourite detail — scanning every other row backwards, so the error stops always drifting the same direction, and the faint diagonal worms that error diffusion is famous for mostly dissolve. And the number in the panel is the whole argument in one line: average an eight-by-eight patch of the result against the same patch of the original and the error is a fraction of what plain rounding gives you, using exactly the same two colours.
Something you might take away
Rounding error does not vanish when you ignore it. It accumulates, silently, and shows up later as banding — as a flat plate where a gradient should be. The fix here is not more precision; it is bookkeeping. Keep a running account of what you dropped, and pay it forward, and the local average stays honest even though no individual pixel can be. That trick is everywhere once you look: noise shaping in audio converters, accumulating fixed-point money in cents rather than rounding each line, the largest-remainder method for handing out parliamentary seats, a progress bar that must total exactly 100. Any time you are forced to be discrete about something continuous, the interesting question is never how do I round this — it is where does the error go.