Bit-serial arithmetic

[This is part of a series of expository, rather than anecdotal, notes, but it provides background for my discussion of the Bendix G-15 architecture. Skip it if you're interested only in my stories.]

With the "embarrassing parallelism" of today's microcircuits, where the challenge is to keep many of the millions of available transistors busy at the same time, it is easy to forget just how little hardware is needed to mechanize binary arithmetic, performed serially. [1]

The basic algorithms are closely akin to those for multi-digit arithmetic that I was taught in elementary school. (For brevity, I will abbreviate "as in grade school arithmetic" to "AIGSA".) However, the algorithms are much simpler for binary, because of the small size of the addition and multiplication tables (0 times 0 is 0, 0 times 1 is 0, 1 times 0 is 0, 1 times 1 is 1) and their ease of translation into binary logic (x times y, is just x and y).

Number Representation

Today's computers almost universally represent negative numbers in "two's-complement" form (the result of subtracting the number's magnitude from zero and ignoring the underflow). But in the 50s and 60s other binary representations were common, notably sign-magnitude and one's-complement. The G-15 used two's-complement for addition and subtraction, and sign-magnitude for multiplication and division. It was the responsibility of the programmer to keep track of which form a value was in. The sign-magnitude form was commonly used for I/O and storage in main memory.

Fortunately, bit-at-a-time conversion between the two forms is easy working right-to-left (least significant bit first) and requires only two extra bits of memory (flip-flops):

• If the sign is positive, pass all the bits unchanged.
• If the sign is negative, pass all bits up to and including the first 1 bit unchanged; thereafter, complement each bit--replacing 0 by 1 and 1 by 0. [2]

The two's complement operation is also self-inverse--the complement of the complement of x is x.

The G-15 processed all numbers right-to-left (least significant bit first). [3] However, the sign bit preceded all the other bits, to enable complementation on the fly when needed.

The Binary Point, Scaling, and Shifting

Fixed point arithmetic is not restricted to integers. Many pocket calculators, for example, allow the user to choose the number of digits to display after the decimal point (typically two for "dollars and cents" calculations). This is even more important for a machine without floating point arithmetic.

In the G-15, a value's "binary point," unlike its sign, had no explicit internal representation. It was up to the programmer to keep track of the binary points of all values throughout the course of a computation. Values were often treated as integers (binary point 0, i.e., immediately following the least significant digit) or fractions (binary point 28 or 57, i.e., immediately preceding the most significant digit), but this was entirely the programmer's choice.

To align the binary points of scaled numbers (or to change their scaling for other reasons) it is necessary to shift them left or right--equivalent to doubling or halving them, respectively. The G-15 provided two double-precision shift registers, one for each direction. [4][5]

Unsigned Addition

AIGSA, operate one digit (bit) at a time, from the right. One extra flip-flop is needed to propagate a carry to the digit to the left (the next "bit time"). At each bit time there are three bits of input--the two operands and the carry bit. The result bit is the xor or "parity" of those three bits--0 if the number of 1s is even, 1 if it is odd. The carry bit is 0 if none or one of them is 1, and 1 if two or three are. That's it. Proceed to the next bit.

A carry bit of 1 following calculation of the last (most significant) bit indicates overflow.

AIGSA, it is necessary to align the binary points of operands before adding them. E.g.,
100.01
+10.
110.01
rather than
100.01
+0010.
100.11
The binary point of the result is the same as that of the two aligned operands.

Signed Addition

Use two's-complement form for negative numbers, but add them as above.

If both operands have the same sign, that is the sign of the result. A final carry bit that is different from the sign indicates overflow.

If the operands have opposite signs, no overflow can occur, and the final carry bit indicates the sign of the result. [6]

Subtraction

To subtract a number, change its sign then add it (complementing if negative).

Multiplication and Division

Addition and subtraction can be done in a single serial "pass," doing complementation as needed "on the fly."

Multiplication and division can more easily be done AIGSA with simple iterative processes using the sign-magnitude representation. The processes involve three registers (two for the operands and one for the result): an accumulator to which values can be added or subtracted, and two shift registers, as mentioned previously.

For either multiplication or division, the sign of the result is the xor of the signs of the two operands. It was computed and stored in the IP flip-flop as the operands were loaded, and inserted in the result when it was stored.

Multiplication

Initially zero the accumulator, place the multiplier in the right-shifting register, and the multiplicand in the left-shifting register.

AIGSA, work from right-to-left, performing a series of multiplications of the multiplicand by a single digit of the multiplier, and summing the partial products. Since the single digits can only be 0 or 1, each partial product is either 0 or the shifted multiplicand. Rather than forming all the partial products and then adding them, add them as they are formed. I.e., at each step, test the least significant bit of the multiplier register, and if it is 1, add the multiplicand register to the product register. Repeat with the registers shifted, until the entire product has been formed.

The binary point of the result is the sum of the binary points of the operands.

Division

Initially place the numerator in the accumulator register and the denominator in the right-shifting register. Zero the left-shifting register.

AIGSA, work from left to right. Subtract the "trial divisor" times the denominator from the numerator and observe the sign. (In binary arithmetic, 1 is the only interesting trial divisor.) If the sign is negative, the trial divisor "did not go"; the product should be added back, and a smaller divisor tried (in binary, this can only be 0). If the sign is positive, the trial divisor "did go," and is the next digit of the result. Insert it as the low-order bit of the developing quotient in the left-shifting register. Shift the denominator to the right to continue generating digits of the quotient.

The G-15 used a simple identity to simplify the implementation of the iteration described above. If the trial divisor of 1 did not go, rather than adding the product back, and then in the next iteration subtracting the product of the next trial divisor (which would be exactly half of the previous product), it did not do the "add back," but simply added the shifted denominator at the next step.

The binary point of the result is the difference between the binary points of the operands.

Notes:
[1] Most serial binary machines must have used algorithms similar to those I describe here, but I had personal experience only with the G-15. I shall describe what I know.
[2] The proof of this is left as an exercise for the reader, as will be various other simple properties of binary arithmetic.
[3] Bendix hardware engineers used special Tektronix oscilloscopes that swept from right-to-left, rather than left-to-right, to make numbers more readable on the scope.
[4] A single register that could be shifted in either direction would suffice for this purpose, but these registers had additional uses, as we shall see presently.
[5] It should be obvious that only a single extra flip-flop is needed to shift to the left (delay by one bit time), but it may be less obvious how to shift to the right using a single extra flip-flop. No, it does not require the mythical if gate that emits a pulse one bit time before receiving it.
[6] "But the sign preceded the least significant bit!" Yes, and fortunately, with a recirculating accumulator, it is available again at just the right time. Technically, this is the first bit-time of the next word-time, but the programmer cannot detect the late substitution. "The hardware must cheat, but it must not get caught."