Well put. Another example is Floyd–Steinberg dithering which is also error-conserving.
My (effectively one-line) implementation above was derived from first-principle:
Given a desired target level 0 <= T <= 1, control the output O in {1,0}, such that O on on average is T. Do this by integrating the error T - O over time and switching O such that the sum of (T - O) is finite.
S = O = 0
loop:
S = S + (T - O)
O = (S >= 0)
In fixed point arithmetic this becomes even simpler (assume N-bit arith) S = Sf * 2^N = Sf << N. As |S| <= 1, N+2 bits is sufficient
S = O = 0
loop:
D = T + (~O + 1) << N === T + (O << N) + (O << (N+1))
S = S + D
O = 1 & ~(S >> (N+1))
Completely agree. I've always considered Floyd-Steinberg dithering to be a 2D version of Sigma-Delta. It's all about diffusing and minimizing error quantities, to trade higher sampling rate for lower sample resolution while conserving total information content.
Another example is Bresenham's algorithm for drawing straight lines on raster displays. The quantity being approximated there is the slope of the line, which is approximated with minimal diffused error as the line is being drawn with only integer adds and subtracts. No divisions and no floating point needed.
These are some of the most subtly beautiful algorithms in computing.
My (effectively one-line) implementation above was derived from first-principle:
Given a desired target level 0 <= T <= 1, control the output O in {1,0}, such that O on on average is T. Do this by integrating the error T - O over time and switching O such that the sum of (T - O) is finite.
In fixed point arithmetic this becomes even simpler (assume N-bit arith) S = Sf * 2^N = Sf << N. As |S| <= 1, N+2 bits is sufficient and that's the Verilog below