1965

Bresenham

Bresenham published this in the IBM Systems Journal in 1965, for a plotter that could move to any of eight neighbouring points on a mesh and nothing in between. The paper's own claim is the interesting one: it can be programmed without multiplication or division. One integer carries how far the line has drifted from the pixels chosen so far, and comparing it against zero decides the next step.

A straight line, decided by adding

Drag the end point. The grey line is where the real one goes; the filled squares are what a grid can actually offer. At every column the choice is between two squares, and the error term is what decides.

AcrossUp

step	x	y	error before	stepped up

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.

Each claim, whether it held, and the values behind it
claim	held	measured
the stepping uses no multiplication and no division	yes	0 multiply, 0 divide, 3 shift(s)
every pixel is within half a square of the real line	yes	worst 0.500 of a square over 23820 pixels, at 2x1
one pixel per column, and both ends are on the line	yes	18 pixels from (0,0) to (17,6)
a flat line never steps up	yes	13 pixels, all on the same row
and a forty-five degree line steps up every time	yes	10 pixels, every one on the diagonal

What is real here, and what is not

The claim about multiplication is checked, not repeated

The paper says the algorithm can be programmed without multiplication or division instructions. This page reads its own source at load, counts the multiply and divide operators inside the loop, and prints the count. The two initial doublings are shifts and are counted as such; if a multiply ever appears in there the table says so rather than the page continuing to claim otherwise.

One octant, mirrored

The arithmetic here handles a line going right and up, no steeper than forty-five degrees, and every other direction is the same line with the axes swapped or the sign flipped. The plotter in the paper had all eight movements and the paper handles them; this page mirrors rather than repeating the derivation, which is a presentation choice and not a different algorithm.

Integers throughout, and that is the whole point

No floating point is used anywhere in the stepping. The error term is an integer, the comparison is against zero, and the updates are additions of two constants computed once. A version using fractions would draw exactly the same pixels and would be a different machine.

Pixels, not ink

A plotter drawing this puts down a pen and moves it, so a diagonal step draws a longer stroke than a straight one and the line is very slightly darker where it steps. Nothing here models that. The squares are all the same weight.

No sound

Nothing here has a duration to hear.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1971-1995 Line ModeYou could telnet to port 80 and be the browser, and then you could not.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Flip-Flop, Punch Cards, Interlace, Bitwise, The Adder, Stored Program, Two's Complement, Trigger, Bit, Nibble, Byte, Transistor, Score Reel, Hamming, Huffman, Core Memory, Hash Table, The Interrupt, CORDIC, Garbage, CRC, The Pipeline, Round Robin, Page Fault, Context Switch, ASCII, Bresenham, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Zero Address, Fringes, LZ77, Signature, Z-Characters, Merkle Proof, Branch Prediction, Write-Ahead Log, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, Longest Chain, JPEG, UTF-8, Masking, PageRank, Merge Collapse, Merkle DAG, Count Distinct.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.