How CPUs Do Math(s) - Computerphile

Source: How CPUs Do Math(s) - Computerphile, Computerphile, 19:38, uploaded 2024-01-23, category Mathematics, playlist index 1193.

Matt Godbolt resumes an earlier explanation built around a small robot. The robot has an abacus for arithmetic, an accumulator for the number it is working on, an index that points into memory, and a large set of pigeon holes containing numbered cards. The picture came from a 1980s computer book Godbolt had as a child. It gives a computer a body and a set of props, then asks what those props have to do to run a program.

The earlier episode ends with a useful circular idea: the robot’s instructions can sit in the same pigeon holes as its data. Godbolt had passed over the arithmetic inside that machine. This episode fills in that gap with a decimal model that is small enough to draw on paper.

Finite numbers in a finite machine

The robot has limited resources. Its accumulator cannot hold an arbitrarily large number, and each memory slot has the same limit. Godbolt uses an 8-bit computer as the historical reference. An 8-bit machine handles eight binary digits as a natural unit when it fetches data or performs an operation. For the drawing, he treats that capacity as two decimal digits, so the accumulator and each memory slot can hold values from 0 to 99.

That substitution keeps the arithmetic visible. Binary would make the example harder to follow on the page, whilst the decimal version preserves the problem: a Fibonacci sequence soon grows past the largest value one slot can contain. A larger number therefore has to occupy consecutive slots. Four decimal digits need two of the robot’s two-digit pigeon holes, and a longer number needs more.

People already have a method for this. To add 10 and 33, start at the right and add 0 to 3, then 1 to 3. The result is 43. The same method extends across as much paper as the numbers require. The machine has to turn that method into operations that fit its two-digit accumulator.

The carry flag as a small piece of memory

The limit becomes visible with 99 + 99. The right-hand digits produce 18, so the machine keeps 8 in that column and carries 1 to the next. The next column adds 9, 9, and the carried 1, producing the extra digit. The full result is 198, which no longer fits in one two-digit slot.

Godbolt gives the robot a set of flags. A flag records something about the last arithmetic operation. The carry flag rises when an addition produces a value beyond the accumulator’s width. The zero flag records a zero result. The negative and overflow flags handle other cases, although the decimal drawing leaves their exact behaviour aside. The carry flag is the useful one here because it lets the next operation remember the extra 1.

The robot now has enough state to add numbers stored across several slots. Godbolt writes the instructions in a loose assembly language, the human-readable form of the operations. The example uses four-digit Fibonacci numbers, with two memory slots allocated to each number in the sequence.

Little-endian storage and the addition of 233 and 377

The first choice concerns the order of the slots. The machine needs the least significant part of a number first because that is where addition starts. It can store 233 as 02 followed by 33, with the low part in the first slot. Reading the slots in memory order makes the number look backwards to a person inspecting the memory. Godbolt calls this arrangement little-endian because the little end of the number comes first. Big-endian storage puts the high part first.

The Intel processor in his laptop uses little-endian storage, as do most ARM chips, although ARM can be configured. Historical mainframes often used big-endian storage. The choice changes how memory looks during debugging whilst leaving the numerical value unchanged when the processor reads the parts in its chosen order.

Godbolt then adds 233 and 377. In the decimal model, 233 occupies 33 and 02, while 377 occupies 77 and 03. The robot first clears the carry flag so an earlier operation cannot add an unwanted 1. It loads the first low part, 33, into the accumulator and adds 77 with carry. The sum is 110. The low two digits, 10, go into the first result slot and the carry flag rises.

The high parts come next. The robot loads 02, adds 03 and the raised carry, and gets 06. The result is therefore 06 and 10 in memory, which reads as 610. The carry can only contribute one extra unit at this point. Even 99 + 99 produces a carry of 1 into the next two-digit column, so every larger addition can repeat the same operation across more slots.

Modern machines choose a larger natural width. An 8-bit, 16-bit, 32-bit, or 64-bit processor can handle that many binary digits in one ordinary operation. Larger integers still use the same pattern: add one machine word, store its low part, pass the carry to the next word, and continue.

Overflow as a condition for stopping

The multi-slot version lets the robot keep generating Fibonacci numbers until the result reaches the largest value that its allocated slots can represent. The program advances the index by two slots after each addition because one number occupies two slots. It then loops back to repeat the calculation.

An unconditional loop would eventually write into the pigeon holes containing the program itself. Godbolt adds a conditional branch. After the high parts are added, the program branches back to the start only while the carry remains clear. Once the result needs another slot, the carry rises and the branch falls through to a stop instruction such as RTS or HALT. In the four-digit model, the sequence stops when it reaches the boundary around 10,000.

The same flags can build comparisons from arithmetic. To test whether two numbers are equal, subtract one from the other and branch when the zero flag is set. To test whether one is larger, subtract it from the other and inspect the negative flag. The video keeps the signed-number details brief because its decimal setup does not represent them cleanly. Its point is the control-flow mechanism: arithmetic leaves conditions behind, and branch instructions read those conditions.

A BBC Micro check

Godbolt ends by switching to a BBC Micro running a slightly changed version of the Fibonacci program. The screen shows the instructions alongside the values they produce. The code contains the same load, add, store, increment, and branch operations that the paper robot used. The example has moved from an invented instruction set to a real 1980s computer without changing the basic account of what happens.

The program writes the Fibonacci values into memory that also affects the display, which creates coloured junk near the top of the screen. In the emulator, Godbolt can inspect those memory locations directly. The values appear in hexadecimal, so the first sequence reads as 0, 1, 1, 2, 3, 5, 8, and 13 in another notation. The representation of 610 also appears in the memory when the program reaches it.

The final view makes the machine’s bits explicit. Each bit has a position, from Bit 0 through Bit 31 in the displayed word. The pigeon holes have become memory addresses, the cards have become bit patterns, and the robot has become an emulated BBC Micro running inside a browser. The arithmetic remains a sequence of bounded operations with flags carrying information from one step to the next.

Limits of the model

The source uses decimal slots as a teaching model for binary CPU arithmetic. It explains how a processor can combine fixed-width values into larger numbers, propagate a carry, and use status flags to control a loop. The BBC Micro demonstration supports that operational picture with a real program and visible memory.

The episode leaves the circuitry beneath the instructions outside the frame. It does not build the adders and gates that produce the sums, or give a full account of signed integers, overflow conventions, instruction decoding, or the differences between CPU families. The discussion of negative values and overflow is deliberately brief. The decimal robot therefore proves the shape of the procedure, whilst the details of a particular processor still belong to its binary representation and instruction set.