UN

Multiplication

Slides 26 & 27 are on your exam: the multiply algorithm flowchart and the hardware that runs it. Learn the 3 steps, then learn the 4 boxes.

1. Vocabulary

Product=Multiplicand×Multiplier\text{Product} = \text{Multiplicand} \times \text{Multiplier}

Multiplicand = the number on top (the one that gets repeatedly added).
Multiplier = the number underneath (the one whose bits we test, one at a time).

2. Paper-and-pencil binary multiplication

Exactly like decimal long multiplication, but each partial product is either a copy of the multiplicand (when the multiplier bit is 1) or all zeros (when it is 0) — because you're only ever multiplying by 1 or 0. 

      10101      ← Multiplicand (21)
    ×   101      ← Multiplier   (5)
    -------
      10101      ← bit 0 of multiplier is 1 → copy
     000000      ← bit 1 is 0 → zeros    (shifted 1 left)
    1010100      ← bit 2 is 1 → copy     (shifted 2 left)
    -------
    1101001      ← Product (105)  ✔ 21 × 5 = 105
Size of the product. An nn-bit multiplicand times an mm-bit multiplier gives a product that is n+mn + m bits long (ignoring sign bits). This is why multiply, like add, must worry about overflow — we usually want a 32-bit result from multiplying two 32-bit numbers.

3. The multiplication algorithm ★ (slide 26)

The hardware can't write out partial products and add them all at the end — it has one adder. So it does the same work incrementally: initialise Product = 0, then repeat nn times:

Product = 0
initialisation, before the loop
start loop
1. Test Multiplier₀ (the rightmost bit)
bit = 1
1a. If it is 1: Product = Product + Multiplicand
if it is 0, do nothing
always
2. Shift the Multiplicand register LEFT 1 bit
always
3. Shift the Multiplier register RIGHT 1 bit
nth repetition?
Done after n repetitions
otherwise loop back to step 1
The first multiplication algorithm — n iterations for an n-bit multiplier.
Why shift left, why shift right?
  • Shifting the multiplicand left is the “move the partial product one column over” step from the paper method — it multiplies it by 2.
  • Shifting the multiplier right brings the next bit down into position 0, so step 1 can always just look at the rightmost bit.
Complexity. For an mm-bit multiplier the loop runs mm times ⇒ Time=O(m)\text{Time} = O(m) (the slide writes O(n)O(n) for an nn-bit multiplier — same statement). Storage is the multiplicand + multiplier + product registers ⇒ Space=O(n+m)\text{Space} = O(n+m), written O(5n)=O(n)O(5n) = O(n) on the slide when both operands are nn bits.

4. The hardware ★ (slide 27)

Four boxes plus a control unit. For 32-bit operands:

RegisterWidthWhat it does
Multiplicand64 bits (2n)Shifts left once per iteration
ALU64-bit adderAdds Multiplicand into Product
Multiplier32 bits (n)Shifts right once per iteration
Product64 bits (2n)Accumulates; initialised to 0
Note the widths: the multiplicand register and the ALU are double width, because after shifting left nn times the multiplicand has grown into the upper half. The Control test block reads Multiplier₀, decides whether to trigger the add, and issues the two shift signals and the Product write signal.

In the 4-bit slide example the same picture is used with 8-bit Multiplicand / 8-bit ALU / 4-bit Multiplier / 8-bit Product — the rule is simply double the operand width.

5. Full worked trace — 0010 × 0011 (2 × 3)

4-bit operands, so 4 iterations, 8-bit registers. Follow the three steps every row.

IterStepMultiplierMultiplicandProduct
0Initial values00110000 00100000 0000
11a: bit = 1 ⇒ Prod += Mcand00110000 00100000 0010
2: shift Multiplicand left00110000 01000000 0010
3: shift Multiplier right00010000 01000000 0010
21a: bit = 1 ⇒ Prod += Mcand00010000 01000000 0110
2: shift Multiplicand left00010000 10000000 0110
3: shift Multiplier right00000000 10000000 0110
31: bit = 0 ⇒ no operation00000000 10000000 0110
2: shift Multiplicand left00000001 00000000 0110
3: shift Multiplier right00000001 00000000 0110
41: bit = 0 ⇒ no operation00000001 00000000 0110
2: shift Multiplicand left00000010 00000000 0110
3: shift Multiplier right00000010 00000000 0110

Product = 0000 0110 = 6 ✔ 2 × 3 = 6.

Exam technique. Draw the 5-column table, write the initial row, then mechanically do 3 rows per iteration. The only decision you ever make is “is the rightmost multiplier bit 1?”. Do all nn iterations even when the multiplier has gone to zero — the marks are for the method.

6. Signed multiplication

The easy approach the book uses:

  1. Remember the signs of both operands.
  2. Convert both to positive numbers.
  3. Run the algorithm for 31 iterations (32-bit operands, signs left out).
  4. Negate the product only if the original signs disagree.

7. Multiplication in MIPS

A 32×32 product needs 64 bits, but MIPS registers are 32 bits. So MIPS keeps a dedicated pair, Hi and Lo, holding the upper and lower halves of the product.

InstructionMeaning
mult $s2, $s3signed: Hi, Lo = $s2 × $s3
multu $s2, $s3unsigned product
mflo $s1$s1 = Lo (move from Lo)
mfhi $s1$s1 = Hi (move from Hi)

To compute $t0 = $t2 × $t1 keeping only the low 32 bits:

mult $t2, $t1
mflo $t0

The assembler also offers a 3-operand pseudoinstruction mul $t0, $t2, $t1, which it expands into exactly the pair above.

Slide example — compiling an if/else with multiply

int i, j, m, n;         // i=$s1  j=$s2  m=$s3  n=$s4
m = 2;
n = 1;
j = i % 2;
if (j == 0)  m = m * i;
else         n = n * i;
    addi $s3, $zero, 2      # m = 2
    addi $s4, $zero, 1      # n = 1
    div  $s1, $s3           # i ÷ 2   → Hi = remainder
    mfhi $s2                # j = i % 2

    bne  $s2, $zero, L1     # if j != 0 jump to else
    mult $s3, $s1           # m * i
    mflo $s3                # m = m * i
    j    L2
L1:
    mult $s4, $s1           # n * i
    mflo $s4                # n = n * i
L2:
    ...

Note the trick: % (remainder) is obtained with div + mfhi.