Or: the story of a bug that turned out to be more correct than the correct code
Boot sequence
Year: somewhere between 1983 and 1987.
Iron: a custom board — Motorola 68000 (32-bit. Pure luxury. The team argued about it for a week.)
and a Texas Instruments TMS34010, one of the first programmable graphics chips on the planet.
VRAM: 256 kilobytes. That's not a typo.
Mass storage: 20 megabytes. Total. OS included.
Mission: rasterize A0 architectural drawings at 400 dpi.
RTFM and do the math:
A0 = 841 × 1189 mm
At 400 dpi → ~13,300 × 18,700 pixels
1 bit per pixel → ~30 MB
The output bitmap did not fit on the disk.
The disk that also held the OS, the FAT, the filesystem driver,
the application, and the quadtree-compressed source drawing.
Every byte was hand-negotiated. Every cycle was audited.
The entire stack — OS, filesystem, elevator disk scheduler, swap system — was written
from scratch, in assembly or C, by some people with a logic analyzer and too much coffee.
This is the environment in which one needed to DTFC.
The textbook solution (a.k.a. the one that doesn't run)
The clean approach: place a point on the circle, then rotate it step by step around the origin.
Standard rotation matrix, angle a = 2π/N for N steps:
| cos(a) -sin(a) | applied to | x |
| sin(a) cos(a) | | y |
In code:
float x = r, y = 0;
for (int i = 0; i < N; i++) {
plot(x, y);
float nx = x*cos(a) - y*sin(a);
float ny = x*sin(a) + y*cos(a);
x = nx; y = ny;
}
Mathematically perfect. Beautiful.
Totally unrunnable on 8-bit era hardware.
- No FPU. Not even close.
-
cos()andsin()? Lookup tables eat precious RAM. Computing them costs dozens of cycles each, on a CPU where the budget per pixel was counted on fingers. - Four multiplications per step. On a 68000, a 16×16 multiply was a luxury instruction. You felt it in the profiler. (There was no profiler. You felt it in your soul.)
Abort. Reboot. Think harder.
Patch #1 — Nuke the trig
For a small angle a, Taylor says:
cos(a) ≈ 1
sin(a) ≈ a
Plug that into the rotation matrix:
| 1 -a |
| a 1 |
The loop becomes:
float nx = x - y*a;
float ny = y + x*a;
x = nx; y = ny;
Zero trig. Two multiplications by a constant a. Progress.
Ship it? Not yet. Those two multiplications still hurt.
Patch #2 — Nuke the multiplications
If a = 1/2^n... multiplications become right bit shifts.
And dropping the temp variables is EZ PZ:
x = x - (y >> n);
y = y + (x >> n);
Zero multiplications. Shifts and adds only.
In 16-bit fixed-point (8.8 format), this is 3-4 cycles per point.
At 8 MHz: tens of thousands of circle points per second.
The plotter can't even keep up.
One ran it.
The circle closed perfectly.
Ship it.
Wait. There's a bug here.
Look at that code again. Really look at it.
x = x - (y >> n); /* x is modified HERE... */
y = y + (x >> n); /* ...NEW x is reused here. OOPS. */
That's not the same as the clean version with a temp variable.
That's an in-place update bug — the classic freshman mistake,
the thing that gets you a raised eyebrow in code review.
And there's worse. Look at the approximation matrix in the maths above:
| 1 -a | det = 1×1 − (−a)×a = 1 + a²
| a 1 |
Determinant greater than 1. Every step should expand the radius slightly.
After N iterations, the spiral should drift outward. The circle should not close.
And yet. No drift. No spiral. Closed.
How.
POST-MORTEM — what the "bug" actually computes
Let's expand what that broken code actually does, algebraically:
x' = x - y*a
y' = y + x'*a
= y + (x - y*a)*a
= y + x*a - y*a²
The implicit transformation matrix is:
| 1 -a |
| a 1-a² |
Determinant:
1×(1−a²) − (−a)×a
= 1 − a² + a²
= 1
Exactly 1.
Not approximately. Not "close enough for graphics work".
Exactly, algebraically, provably 1 — for 'any' value of a.
The "buggy" in-place update doesn't just compensate for the spiral drift.
It perfectly cancels it — the +a² from the approximation error and
the −a² from the in-place reuse cancel each other out, identically.
The bug fixed the bug.
DTFC — final, shipped, still running
/*
** DTFC - Draw The F***ing Circle
**
** Radius r, centered at origin.
** N steps for a full revolution.
** shift = bit precision (e.g. shift=6 means a ≈ 1/64)
**
** No sin(). No cos(). No multiply. No temp variable.
** Just shifts, adds, and one algebraically perfect "mistake".
**
** Determinant = 1. Circle closes. Every time.
*/
int x = r, y = 0;
for (int i = 0; i < N; i++) {
plot(x, y);
x = x - (y >> shift); /* wrong order. keep it. */
y = y + (x >> shift); /* new x. intentional. */
}
Runs on a Z80. Runs on a 6809. Runs on a TMS34010.
Runs on your Arduino right now.
Three lines of logic. Zero trig. Zero multiply.
One preserved determinant hiding in plain sight.
Why this never shipped in a textbook
This trick sits at the junction of:
- Numerical analysis — linearization of transcendental functions
- Linear algebra — determinant as area-preservation invariant
- Hardware archaeology — shift-only fixed-point arithmetic
- Accidental correctness — the bug that was righter than the fix
It was never written down, to anyone's knowledge.
It lived in the fingertips of engineers at Benson, Schlumberger Graphics, OCE —
people who built A0 plotters and raster engines when RAM was rationed
and every cycle had a name.
One colleague — fresh from Sun Microsystems, where he had just taped out
the first hardware triangle rasterizer ever built in silicon —
kept Graphics Gems on his desk, beside Knuth's bibles.
This trick deserved a page in it.
It didn't get one.
Consider this that page.
Halt and catch fire
Sometimes the bug is smarter than the programmer.
Sometimes the constraint is the algorithm.
And sometimes, at 8 MHz with 256k of VRAM and a plotter
spooling A0 drawings for architects who will never know,
one accidentally writes something that is more correct
than the correct version.
The circle closed. It always closed.
— Recovered from memory, ~40 years post-silicon. Still compiles. Still works.
P.S. — Yes, it works with floating point too. The algebra doesn't care about your type system.
Tags: #8bit #retrocomputing #graphics #fixedpoint #TMS34010 #68000
#circledrawing #linearlgebra #determinant #GraphicsGems #accidentalgenius