An adder (from Digital Logic) adds in one step. Multiplying and dividing are built from many adds, subtracts and shifts.
Shift-and-add multiplication
Long multiplication in binary is easy, because each digit of the multiplier is 0 or 1: either add a shifted copy of the multiplicand or add nothing.
multiplicand, multiplier = 13, 11 # 1101 x 1011
product = 0
for i in range(4):
if (multiplier >> i) & 1:
product += multiplicand << i
print("bit", i, "is 1: add", multiplicand << i, "-> product", product)
else:
print("bit", i, "is 0: add nothing")
print(multiplicand, "x", multiplier, "=", product)For n-bit numbers this takes n steps, each an add and a shift. Faster multipliers add all the partial products at once with a tree of adders (Wallace tree), which is why a modern multiply takes only 3 or 4 cycles.
Booth's algorithm
For signed (two's complement) numbers, Andrew Booth noticed that a run of 1s, such as 0111 = 8 − 1, can be done with one subtract and one add instead of three adds. Look at each multiplier bit together with the bit to its right (start with an imaginary 0 to the right of bit 0):
| Pair (bit i, bit i − 1) | Action at position i |
|---|---|
| 0 0 or 1 1 | nothing |
| 1 0 | subtract the multiplicand × 2ⁱ (a run of 1s starts) |
| 0 1 | add the multiplicand × 2ⁱ (a run of 1s has ended) |
It works for negative multipliers with no extra rules.
def booth(m, q, bits):
product, prev = 0, 0 # prev: the imaginary bit to the right of bit 0
for i in range(bits):
bit = (q >> i) & 1
if (bit, prev) == (1, 0):
product -= m << i
print("i =", i, "pair 10: subtract", m << i)
elif (bit, prev) == (0, 1):
product += m << i
print("i =", i, "pair 01: add", m << i)
prev = bit
return product
q = -3 & 0b1111 # -3 in 4-bit two's complement: 1101
print("7 x -3 =", booth(7, q, 4))Restoring division
Division is long division in binary: for each bit of the quotient, try subtracting the divisor from the partial remainder. If the result is negative, restore it (add the divisor back) and write 0; otherwise write 1.
dividend, divisor = 13, 3
remainder, quotient = 0, 0
for i in range(3, -1, -1): # one quotient bit per step, from the top
remainder = (remainder << 1) | ((dividend >> i) & 1)
remainder -= divisor
if remainder < 0:
remainder += divisor # restore
quotient = quotient << 1
else:
quotient = (quotient << 1) | 1
print("step", 4 - i, ": remainder", remainder, " quotient so far", format(quotient, "b"))
print(dividend, "/", divisor, "=", quotient, "remainder", remainder)Division needs one step per quotient bit, and each step depends on the one before, so it is slow: often 20 to 40 cycles, many times a multiplication. Compilers replace division by a constant with a multiplication and a shift whenever they can.
Common mistakes
- Shifting the multiplicand the wrong way: each step multiplies it by 2 (shift left).
- In Booth's algorithm, forgetting the imaginary 0 to the right of the lowest bit.
- Forgetting to restore after a negative trial subtraction in restoring division.
Quick check
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.