The idea: one adder, one shifting register, one cycle per bit
An adder gives its answer in one clock cycle. A simple multiplier or divider does not: it uses the same adder again and again, once per bit of the word. Each clock cycle does one small step of the long multiplication or long division you learned at school, in base 2. A 32-bit MIPS word needs 32 cycles. The page uses 4-bit words, so every run takes four cycles and every bit fits on screen.
The parts, as drawn on the canvas:
| Part | Multiply | Divide |
|---|---|---|
| M | the multiplicand | the divisor |
| A (hi half) | upper half of the product, starts at 0 | the remainder, starts at 0 |
| Q (lo half) | the multiplier at first, the lower half of the product at the end | the dividend at first, the quotient at the end |
| x | one extra bit left of A: the carry out of the adder (Booth: an extra sign bit) | the sign of the subtraction |
| Q−1 | Booth only: the bit that was shifted out of Q last | not used |
Each tab is one circuit. Clock Once runs one clock cycle, Run All runs to the result. The trace panel writes one row per step, like the tables in the textbook.
Shift-and-add multiplication
Long multiplication in binary is easy, because each digit of the multiplier is 0 or 1: a row is either the multiplicand or nothing. So the hardware looks at one multiplier bit per cycle:
- Test the lowest bit Q0.
- If it is 1, add M to A.
- Shift x, A and Q one place right.
The shift does two jobs at once. It drops the multiplier bit that was just used, and it moves the lowest bit of A into Q, where it is a finished product bit. So the multiplier and the lower half of the product can share Q. Demo: 2 × 3 (multiplicand 2 = 0010, multiplier 3 = 0011):
| Cycle | Step | x A | Q |
|---|---|---|---|
| 0 | start | 0 0000 | 0011 |
| 1 | Q0 = 1: add M | 0 0010 | 0011 |
| 1 | shift right | 0 0001 | 0001 |
| 2 | Q0 = 1: add M | 0 0011 | 0001 |
| 2 | shift right | 0 0001 | 1000 |
| 3 | Q0 = 0: no add, shift right | 0 0000 | 1100 |
| 4 | Q0 = 0: no add, shift right | 0 0000 | 0110 |
The product is A:Q = 0000 0110 = 6, after two adds. Two N-bit numbers give a product of up to 2N bits: Demo: 15 × 15 ends with 1110 0001 = 225. In that run the sum in cycle 2 is 0111 + 1111 = 1 0110, which needs five bits. The fifth bit is the carry out of the adder. It is kept in x and the shift moves it back into A.
The first circuit in Patterson and Hennessy has three registers: a 2N-bit multiplicand that shifts left, an N-bit multiplier that shifts right, and a 2N-bit product, with a 2N-bit adder. The page shows the refined circuit. It keeps the multiplicand still, shifts the product right instead, and stores the multiplier in the unused right half of the product. Half the bits and half the adder are saved; the steps are the same.
Signed numbers: Booth's algorithm
Shift-and-add reads its inputs as unsigned numbers. Give it −3 = 1101 and it multiplies by 13. Booth's algorithm works on two's complement numbers directly. It rests on one fact: a run of ones is a difference of two powers of two. For example 0111 = 7 = 8 − 1. So instead of adding M once for every 1 in the run, subtract M where the run starts and add M one place after it ends.
The control looks at two bits each cycle: Q0 and Q−1, the bit that left Q in the cycle before (0 at the start).
| Q0 Q−1 | Meaning | Action before the shift |
|---|---|---|
1 0 | a run of ones starts | A = A − M |
1 1 | middle of a run of ones | nothing |
0 1 | the run has ended | A = A + M |
0 0 | a run of zeros | nothing |
The shift is an arithmetic right shift: the top bit keeps its value, so a negative A stays negative. A negative multiplier needs no special case. Its top bit is 1, so its last run of ones never "ends": the final add is skipped, and that is exactly the weight −2N−1 of the sign bit.
- Demo: 2 × −3: Q =
1101. The pairs are 10, 01, 10, 11: subtract, add, subtract, nothing. The result is1111 1010= −6. - Demo: 5 × 7: Q =
0111. The pairs are 10, 11, 11, 01: one subtract and one add give0010 0011= 35. Shift-and-add would add three times. - Demo: −8 × −8: the only use of the adder is 0 − (−8) = +8 =
0 1000. In four bits1000would read as −8. This is why A has the extra bit x. The result is0100 0000= 64.
On a 4-bit word the saving is small, and for a multiplier like 0101 Booth even uses the adder more often (four times instead of two). Its real value is that signed numbers work with no extra steps. Fast multipliers use a variant that looks at three bits at a time and so halves the number of rows to add.
Restoring division
Long division asks one question per digit: does the divisor fit into what is left? In base 2 the answer is yes (quotient bit 1) or no (quotient bit 0). The hardware finds out by trying. It subtracts the divisor and looks at the sign of the result.
- Shift x, A and Q one place left. The next dividend bit moves into A, and Q0 is left open.
- Subtract: A = A − M.
- Test the sign bit x. If it is 1, the result is negative: the divisor did not fit. Restore A by adding M back, and put 0 into Q0. If x is 0, keep the difference and put 1 into Q0.
After the last cycle Q holds the quotient and A the remainder. Demo: 7 ÷ 2 (dividend 0111, divisor 0010):
| Cycle | Step | x A | Q |
|---|---|---|---|
| 0 | start | 0 0000 | 0111 |
| 1 | shift left | 0 0000 | 111_ |
| 1 | subtract M: negative | 1 1110 | 111_ |
| 1 | restore, Q0 = 0 | 0 0000 | 1110 |
| 2 | shift, subtract (negative), restore, Q0 = 0 | 0 0001 | 1100 |
| 3 | shift, subtract: 3 − 2 = 1, Q0 = 1 | 0 0001 | 1001 |
| 4 | shift, subtract: 3 − 2 = 1, Q0 = 1 | 0 0001 | 0011 |
Quotient 3, remainder 1, with two restores. Demo: 13 ÷ 5 gives 2 remainder 3 with three restores. In Demo: 3 ÷ 5 the divisor never fits: all four cycles restore, the quotient is 0 and the remainder is the dividend, 3.
A restore costs a second use of the adder in the same cycle. Non-restoring division avoids it: it leaves the negative value in A and adds M in the next cycle instead of subtracting. The page shows the restoring kind because each step matches long division by hand.
Where the results go in MIPS: hi and lo
A 32-bit multiply gives a 64-bit product, and a divide gives two results. Neither fits in one 32-bit register. So MIPS has two special registers, hi and lo. Together they are the double register of the page: hi is A and lo is Q.
| Instruction | What it does |
|---|---|
mult $s0, $s1 | signed product: hi = upper 32 bits, lo = lower 32 bits |
multu $s0, $s1 | the same for unsigned numbers |
div $s0, $s1 | signed divide: lo = quotient, hi = remainder |
divu $s0, $s1 | the same for unsigned numbers |
mfhi $t0, mflo $t0 | copy hi or lo into an ordinary register |
To compute c = a * b for C ints a compiler emits mult and then mflo; the upper half in hi is ignored. For a / b it reads lo, for a % b it reads hi. MIPS raises no exception when a product does not fit in 32 bits or when the divisor is 0. Software must check for that itself.
See also Arithmetic Circuits for the adder inside this datapath (ripple carry, carry-lookahead, prefix) and for the array multiplier, which does all the adds in one cycle with N rows of adders.
See also Number Bases and Two's Complement and Number Systems for how negative numbers are stored, and The Single-Cycle MIPS Processor for the datapath that runs every other instruction in one cycle.
What the page leaves out
- Signed division. The usual way is to divide the absolute values and then fix the signs: the quotient is negative when the signs differ, and the remainder takes the sign of the dividend.
- Division by zero. The menus do not offer it. Real hardware runs its cycles anyway and leaves a meaningless result.
- Faster circuits: non-restoring and SRT division, radix-4 Booth recoding, and Wallace trees of carry-save adders that multiply in one or a few cycles.
- 32-bit words. The steps are the same; there are just 32 cycles instead of 4.
- The MIPS32
mulinstruction, which writes the lower half of the product straight to a general register, and floating-point multiply and divide.
On the mind map
References
Patterson and Hennessy, Computer Organization and Design: The Hardware/Software Interface (MIPS edition), Chapter 3: Arithmetic for Computers (Section 3.3, Multiplication; Section 3.4, Division)
Andrew D. Booth, A Signed Binary Multiplication Technique (1951)
Booth's multiplication algorithm (Wikipedia)
Division algorithm: restoring and non-restoring division (Wikipedia)