The machine does arithmetic

Chapter 29 ended with the full adder, a part made of nine NAND gates that adds three bits: one from each number and a carry. But Iskra-8’s registers are eight bits wide. Its instruction ADD R0, R1 has to add numbers from 0 to 255, SUB has to subtract, CMP has to compare, and along the way they must report whether the result is zero and whether there was a carry. We have no subtractor, and no multiplier either. This chapter is a factory where everything a processor can compute is assembled from one kind of part.

The factory is run by the book. Work begins with a specification, the spec of Iskra-8. Each shop makes one unit, and before a unit goes into the machine, the quality control department checks it against the spec on every input there is. At the end of the chapter QC takes on a defect from history: one that passed all of Intel’s tests, spread to computers around the world and came to light only in 1994.

The specification

The unit that computes is called the arithmetic logic unit, or ALU. It receives two bytes and an opcode, a number that says what to do with them, and puts out a result byte and several flags, one-bit marks that tell how the result came out. Here is an extract from the Iskra-8 spec (you will need all of it in Chapter 32):

There are three flags. Z (zero) is 1 if the result is zero. N (negative) is a copy of the top bit of the result: if you read the byte as a signed number in the two’s complement of Chapter 28, this bit is the sign. C (carry) is the carry out of the top bit in an addition, the borrow in a subtraction, or the bit that falls out in a shift.

QC needs a reference to check against. The reference will be Iskra-8 itself: the sandbox has its emulator, cs.iskra, and in Chapter 32 the same emulator will run your programs. To find out what the ALU must answer for a pair of numbers, give the machine a tiny program: put the numbers in registers, do the operation, stop.

$200 + 100 = 300$, but a byte holds only up to 255: the register keeps $300 - 256 = 44$, and the carry flag goes up. $5 - 7$ gave 254, which is $-2$ in two’s complement, hence N = 1, and the borrow flag is set as well. From here on this function lives in the module cs.alu (from cs.alu import iskra), and QC will call it without rewriting it.

Shop 1. Eight adders in a chain

Column addition from Chapter 29 suggests the design. Put eight full adders in a row, one per bit. Each receives its own bits $a_i$ and $b_i$ and the carry from its neighbor on the right, and passes on the sum bit $s_i$ and a carry to its neighbor on the left. The rightmost adder gets a zero on its carry input, and the carry out of the leftmost one becomes the C flag. This circuit is called a ripple-carry adder: the carry ripples along the chain like a wave.

These sixty-five thousand pairs are every possible input of an eight-bit adder, so this check leaves nothing out: with zero defects, the adder is correct. Remember this luxury, because the Pentium’s divider won’t have it.

The bottleneck: the carry has to run

In the code the loop visits the bits one by one, and you might think that in hardware it all happens at once. But a transistor needs time to switch, and a gate’s output settles only after a delay, a few picoseconds for modern gates. One such delay goes unnoticed, but along a chain they add up. The top bit of the sum can’t be right until the carry has run all the way to it, and the carry out of bit $i$ depends on the carry out of bit $i - 1$. Add one to 11111111: the carry is born in bit 0 and runs through all eight bits, two gates for each.

For eight bits that comes to 16 delays, and for a 64-bit processor to 128. The longest chain in a circuit decides how often it can be fed new numbers, that is, the clock rate we will discuss in Chapter 31. That is why the adders in processors are built more cleverly.

Carry look-ahead

The idea is to predict the carry instead of waiting for it. Consider bit $i$ on its own. If $a_i = b_i = 1$, a carry will come out of it whatever comes in: the bit generates a carry, $g_i = a_i b_i$. If only one of the two bits is 1, the bit propagates the incoming carry onward: $p_i = a_i \oplus b_i$. If both are zero, it kills the carry. Then

$$c_{i+1} = g_i + p_i c_i,$$

and this formula can be unrolled: $c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0$. There is a carry into bit 2 if bit 1 generated it, or bit 0 generated it and bit 1 passed it on, or it came in from outside and both bits passed it on. All the $g$ and $p$ are computed at the same moment, within one delay, and the unrolled formula is an OR of several ANDs, two levels of gates, as in Chapter 29. The trouble is that the formulas grow for the higher bits. The way out is to compute the carries with a tree: first for pairs of neighboring bits (“the pair generates a carry” and “the pair propagates a carry”), then for groups of four, eight and so on. Such a tree has $\log_2 n$ levels, and a 64-bit carry is ready after about 14 delays instead of 128. Many look-ahead schemes have been invented, but all of them pay for time in gates: the tree is bigger than the chain.

Does the tree compute the same carries as the chain? Both functions below return the list of carries out of every bit. The second works in levels: on the level with stride step, each bit merges its pair $(g, p)$ with the pair of the bit step places to its right, and after $\log_2 8 = 3$ levels all the carries are ready.

Shop 2. Subtraction without a subtractor

In a task for Chapter 29 we built a full subtractor, and it turned out to be an adder with one NOT. But we can do without it altogether. Chapter 28 showed that in two’s complement $-b$ is “flip all the bits and add one.” So

$$a - b = a + \overline{b} + 1 \pmod{256}.$$

Flipping the bits takes eight XOR gates. Each gets the bit $b_i$ on one input and a shared control wire, SUB, on the other. When $\mathrm{SUB} = 0$, the XOR lets $b_i$ through unchanged; when $\mathrm{SUB} = 1$, it flips it. And “add one” costs nothing: the same SUB wire goes to the carry input of the lowest adder, which got a zero there during addition. One adder, eight XORs and a wire, and the ALU can subtract.

That leaves the C flag. In a subtraction the adder puts out a carry of 1 when $a \ge b$: for example, $7 - 5 = 7 + 250 + 1 = 258$, and the ninth bit falls off. Iskra-8’s spec says C holds the borrow, a 1 when $a < b$, so in a subtraction one more gate inverts the adder’s carry. x86 does the same; ARM processors follow the opposite convention, where the flag after a subtraction means “there was no borrow.” This catches out plenty of people who write assembly for more than one kind of machine.

The instruction CMP is the same subtraction, except that the result goes nowhere and only the flags remain. After CMP R0, R1 the Z flag says whether the numbers are equal, and the C flag says whether $R_0$ is less than $R_1$. In Chapter 32 every condition in Iskra-8’s programs will rest on this: “compare, and jump if Z” is machine code for if a == b.

Shop 3. Flags

Flags come cheap. N is a wire from the top bit of the result, without a single gate. C is a wire from the carry of the top adder (through a NOT in a subtraction). Z is a single eight-input NOR gate, which puts out 1 only when every bit of the result is zero. In practice such a wide gate is assembled as a tree of small ones, but the idea stays the same.

Bigger processors have a fourth flag, overflow, V (x86 calls it OF). The carry C signals overflow for unsigned numbers: $200 + 100$ didn’t fit in a byte. But the same byte can be read as a signed number, and then there is a different kind of trouble. $100 + 100 = 200$, and for unsigned numbers all is well: C = 0. As a signed number, though, 200 is $-56$: we added two positive numbers and got a negative one. Signed overflow happens when the two addends have the same sign and the result has the opposite one. It is easy to catch at the level of gates too: there is overflow when the carry into the top bit differs from the carry out of it.

Add 127 and 1 in an eight-bit ALU. Which flags go up, if we count the signed overflow V as well?

only C N and V Z and C none

$127 + 1 = 128 = 10000000_2$. The top bit became 1, so N = 1. Nothing carries out of the top bit, so C = 0, and for unsigned numbers the answer is right. But 127 is the largest signed eight-bit number, and 10000000 read as signed is $-128$: two positive numbers gave a negative one, so V = 1. There was a carry into the top bit and none out of it, and the two didn’t match.

Iskra-8 has no V flag. The machine is meant to be small, and three flags are enough for it to compare unsigned numbers. On Iskra-8, signed comparison has to be put together by hand, from the N flag and the signs of the numbers. And you will write the V flag yourself, in the task “The fourth flag.”

Flags in your code

The idea of one bit per yes-or-no property lives far beyond the processor. File permissions in Unix are nine bits: read, write and execute for the owner, the group and everyone else. Python’s regular expression options are bits as well: re.IGNORECASE | re.MULTILINE combines flags with OR, and the test flags & re.MULTILINE uses AND to ask whether a particular flag is set. These are the ALU’s own operations, applied to Python integers.

A right shift followed by a mask is the standard way to cut a field of bits out of a number, and OR is how you put a number together from fields. That is also how an Iskra-8 instruction byte gets split into an opcode and register numbers, which we will need in Chapter 32.

Shop 4. The ALU: everyone computes, one result is chosen

The units are ready: an adder that can subtract, eight ANDs, eight ORs, eight XORs, the shifters. What remains is to join them into one device that does whatever the opcode tells it. In a program we would write if op == 'ADD': … elif op == 'SUB': … and compute only one thing. A circuit can’t work that way, because current flows through all its wires at once. So in an ALU all the units compute all the time, on every tick, and at the output sits the multiplexer from Chapter 29, only a wide one. Guided by the opcode, it lets one of the results through to the register, and the others are thrown away. It is wasteful, but gates are cheap and time is expensive: waiting for the switchman to decide what to compute would take longer than computing everything.

On the desk, ADD R0, R1 is the byte 0x51: the top four bits, 0101, are opcode 5, followed by two bits for each register number. These four bits (and for the shifts, INC and DEC, which share opcode A, the bb field as well) go to the control inputs of the ALU’s multiplexer. The machine doesn’t “understand” the opcode; the opcode only opens one of the paths.

Shop 5. Shifts and multiplication

The cheapest unit in the factory contains not a single gate. A left shift is wires soldered one place over: bit $a_i$ goes to output $i + 1$, a zero comes into the lowest bit, and the top bit falls out into the C flag. As a zero written on the right multiplies a decimal number by 10, so a left shift multiplies a binary number by 2. A right shift does integer division by 2, and the lowest bit, the remainder, falls out into the flag. In Python these are the operators << and >>.

Iskra-8 has no multiplication, but it can be built from shifts and additions. Write the multiplier $b$ in binary: $b = \sum b_i 2^i$. Then $a \cdot b = \sum b_i \cdot (a \cdot 2^i)$: take $a$ shifted by $i$ places wherever $b$ has a 1, and add these up. This is the Egyptian multiplication by doubling, known from the Rhind papyrus, which you may have met in our math course: to multiply 13 by 21, a scribe doubled 21 again and again and added up the rows he needed. Thousands of years ago he was computing in binary without suspecting it.

Four steps instead of thirteen additions, one for each bit of the multiplier. For 64-bit numbers that is 64 additions, where adding over and over would take billions of billions. Processors make the multiplier faster still by adding all the shifted copies at once, with a tree of adders. An eight-bit multiplier takes a few dozen full adders, and a 64-bit one takes thousands. Iskra-8 can’t afford such a luxury: in Chapter 32 you will write multiplication as a program built from ADD, SHL, SHR and a conditional jump.

Division is harder. Long division in binary is shifts and subtractions: try subtracting the divisor; if it goes, write 1 in the quotient, if not, write 0, and shift. Each step yields one bit of the quotient, and each needs a full subtraction with all its carry delays. Sixty-four bits of quotient mean 64 slow steps. Processor designers spent decades looking for faster ways to divide, and one of the most successful led to the most notorious defect in the history of arithmetic.

Quality control: the case of the division

The sandbox has a model of the Pentium divider, so you can repeat Coe’s discovery. Python divides correctly; the model divides the way the 1994 processor did.

The error is in the fifth significant digit, a relative error of $6 \cdot 10^{-5}$, when double precision promises $10^{-16}$. Nicely had a harder time: his error hid in the tenth significant digit, and he noticed it only because he compared the results of different machines.

How the Pentium divided

The Pentium’s divider used the SRT method, named after Sweeney, Robertson and Tocher, who came up with it independently of one another in the late 1950s. It produces two bits of the quotient per step instead of one, that is, one digit in base 4. To avoid spending time on a full comparison of the remainder with the divisor, the processor guesses the next digit from a table: the row is picked by the first seven bits of the remainder, the column by the first four bits of the divisor after the binary point. The table has $128 \times 16 = 2048$ cells, of which 1066 are in use.

The clever part of SRT is its set of digits: the quotient is made up of $-2, -1, 0, 1, 2$ instead of 0, 1, 2, 3. With negative digits available, a guess that came out slightly too high can be corrected at the next step, so the table can make do with rough, truncated values of the remainder. But this freedom has a limit: the remainder must stay within $\pm\frac{8}{3}$ of the divisor. As long as it stays there, every wrong guess can be put right. Once the remainder flies past that limit, the following digits can never bring it back.

The table was generated by a program. In 1994 Intel blamed the defect on a mistake in a script. In 2024 the engineer and computer historian Ken Shirriff photographed a Pentium chip under a microscope, read the table from the layout of its transistors and concluded that the mistake lay deeper, in the mathematics: the program drew the boundary of the region for the digit 2 in the wrong place. Sixteen cells were left empty. The remainder can never reach eleven of them, but five of them, one at the top of each of five columns, are reachable. Instead of the digit 2 they gave 0, the remainder flew far past $\frac{8}{3}$ of the divisor, and every digit of the quotient after that was garbage.

Break a cell in the middle of the band for the digit 1 or −1 in any column of the widget, and a check of five thousand divisions will find about a hundred errors. The Pentium’s defect passed every test because its five cells sit right at the edge, where the remainder almost never wanders. Tim Coe and Peter Tang proved that it can get there only with a divisor whose bits five through ten after the binary point are all ones, and on top of that the remainder has to creep up on the boundary for several steps in a row. Byte magazine estimated that about one random division in nine billion goes wrong. Random tests can’t catch a defect like that, and the experiment below shows it.

Zero and zero. Even aiming at the risky divisors misses, because the dividend also has to lead the remainder to the edge. Coe found his pair by reasoning: he reconstructed the design of the divider and calculated which numbers would bring the remainder into a bad cell. His divisor is in the last line of the output: after the leading 1 comes 0111, a bad column, and then nothing but ones.

QC checked the adder on every input, all 65,536 of them. A double-precision divider has $2^{128}$ inputs, far too many to try, and a random sample misses the rare paths. Units like this need a proof, an argument that covers all inputs at once. After the Pentium affair Intel began to verify the arithmetic units of its processors with formal proofs whose correctness is checked by a program. During the development of the Pentium 4 such proofs found bugs that could have led to a similar recall. For the reader the lesson is simpler: if your code contains a table generated by a program, check both the program and the table, above all at the edges.

Tasks

Four orders for the assembly shop. The checker compares your units with Iskra-8 and with Python on thousands of inputs, and where a task says “without plus,” it reads your code too.

Write add(a, b), the sum of two non-negative integers of any size, without using + or -: only &, |, ^, ~, shifts, comparisons, if and loops. The catch is size. On numbers of four hundred thousand bits the function must finish within a second, and the adder from Shop 1, walking through the bits one after another, won’t make it in time. Then write sub8(a, b), the difference of two bytes modulo 256 as the SUB instruction computes it, again without plus or minus (you may call your own add).

Work on all the bits at once. a ^ b is the sum without carries: each bit holds what XOR gives. a & b marks the bits where a carry was born, and (a & b) << 1 marks where it has to arrive.

So $a + b = (a \oplus b) + ((a \mathbin{\&} b) \ll 1)$, which is again a sum of two numbers. Repeat until the carries run out. Each pass handles all the bits at once, and there are as many passes as the longest chain of carries, which is short for random numbers.

For sub8, remember Shop 2: $a - b = a + \overline{b} + 1$. “Flip eight bits” is ~b & 0xFF or b ^ 0xFF, and at the end & 0xFF cuts off the extra ninth bit.

The loop in add is an adder in which all the bits work at once, as they do in hardware, and the passes of the loop are waves of carries. The worst case is the same long chain as in the ripple-carry adder: $2^n - 1 + 1$ takes $n + 1$ passes. For random numbers, chains of carries are rarely longer than a few dozen bits, so there are few passes, and each is a handful of operations on the whole number at once.

Write alu(op, a, b), a software model of Iskra-8’s arithmetic logic unit. op is one of the strings 'ADD', 'SUB', 'AND', 'OR', 'XOR', 'SHL', 'SHR', 'INC', 'DEC', 'CMP'; a and b are bytes (the shifts, INC and DEC ignore the second operand). The function returns (result, z, n, c), with each flag 0 or 1, strictly by the table in the specification. For CMP the result is a, unchanged. For an unknown operation the function must raise ValueError, the way the machine stops at an unknown instruction. The checker will compare your ALU with the emulator on every operation and hundreds of pairs.

First compute the “raw” result, which may be above 255 or below zero, and the C flag while the ninth bit is still visible. Then cut the result down to a byte with & 0xFF and compute Z and N from the byte.

The edge cases QC will check: INC of 255 gives 0 and C = 1, DEC of 0 gives 255 and C = 1 (a borrow), SHL sends the top bit into C and SHR the lowest one, and for AND, OR and XOR the C flag is always 0.

Watch the order: the C flag comes from the raw result, while Z and N come from the trimmed byte. CMP sets the same flags as SUB, but nothing is written to the register. In hardware all of this is computed at once and a multiplexer makes the choice; in a program it is easier to branch, and for the speed of the model it makes no difference.

Here Iskra-8 gets a flag it lacks. Write add_flags(a, b) and sub_flags(a, b) for bytes a and b (0–255). Each returns a dictionary with the four flags of the result, {'Z': …, 'N': …, 'C': …, 'V': …}, with values 0 or 1. Z, N and C are as for Iskra-8’s ADD and SUB (in a subtraction C is the borrow). V is signed overflow: 1 if the result, read as a signed number from $-128$ to 127, isn’t equal to the exact sum or difference of the signed numbers. For example, for $127 + 1$: Z = 0, N = 1, C = 0, V = 1.

The direct route: turn the bytes into signed numbers (x - 256 if x >= 128), add or subtract them, and check whether the answer lands between $-128$ and 127.

The route through bits, as in hardware: an addition overflows when the addends have the same sign and the result has a different one. The sign is bit 7, and the check fits in one expression, (a ^ r) & (b ^ r) & 0x80, where r is the result byte.

Subtraction has a twist: $a - b$ overflows when a and b have different signs and the sign of the result doesn’t match the sign of a. For example, $-128 - 1$: in bytes, sub_flags(128, 1) gives the result 127 and V = 1.

The flags C and V answer the same question (“did the answer fit?”) for two readings of one byte: unsigned and signed. The processor doesn’t know which reading the programmer had in mind, so it computes both, and the program looks at the flag it needs. On x86, after comparing unsigned numbers you test the carry, and for signed numbers a combination of N and V (there they are called SF and OF): $a < b$ when $N \ne V$.

Write multiply(a, b), the product of two integers, negative ones included, without *, /, //, % and **: only addition, subtraction, shifts and bitwise operations (plus comparisons, if, loops and abs). The product of two thousand-digit numbers must take less than a second, so adding a to a total b times won’t do. Careful with negative numbers: check what -1 >> 1 gives in Python.

The Egyptian method from Shop 5: while the multiplier isn’t zero, check its low bit (b & 1); if it is 1, add a to the total; then a <<= 1, b >>= 1.

Python’s negative numbers behave as if their two’s complement were infinitely wide, and a right shift rounds down: -1 >> 1 equals $-1$, so the loop while b never ends for a negative b. Remember the sign, multiply the absolute values, and put the sign back at the end.

There are no more additions than the multiplier has bits: about 3,300 for a thousand-digit number, rather than $10^{1000}$. The sign of the product is the XOR of the signs of the factors, which is what the first line says. Processors do it differently: they can multiply two’s complement numbers directly, with a correction for the top bit, but in Python absolute values are simpler.

What next

The factory has turned out Iskra-8’s ALU. QC has checked it on every input and found out along the way why a divider can’t be checked like that.

But our ALU has no memory. Put 200 and 100 on its inputs, and 44 appears at the output; take the inputs away, and the answer vanishes. To add up ten numbers, the running total has to be kept somewhere until the next step, and the circuit forgets its result at once. Computing step by step takes memory and time: a wire that holds a bit after the inputs are gone, and a metronome that says when to take the next step. Both, oddly enough, can also be built from NAND. All they need is a loop, the thing we banned in the workshop of Chapter 29. That is the work of Chapter 31.