Multiplication

If a multiplicand and a multiplier have m and n digits, the product has at most m + n digits

• MIPS-based computers use 32-bit word for the arithmetic operations
• The product in MIPS-based computers has at most 64 digits

Optimized version of the multiplication HW

• 32-bit multiplicand register / ALU
• 64-bit product register (multiplier shares a register with product)
  • HI: most significant 32 bits
  • LO: least significant 32 bits
  • Actually, there is one more bit in the left of the product register to hold the carry out of the adder

Settings

• 0 is stored in the left half of the product register
• The multiplier value is loaded into the right half of the product register
• The multiplicand value is loaded into the multiplicand register

Multiplication Algorithm

Example

When N = 4 (4-bit ALU / multiplicand, 8-bit product), $2 \times 3$

• should be repeated as many bits as it is

Signed multiplication

Do multiplication after converting both multiplicand & multiplier to positives

• For 31 iterations (except a sign bit)
• After the multiplication, negate the result (if it is required)

Better solution: Booth's Algorithm

• Supports multiplication of two's complement signed numbers in a more efficient way
• Requires almost same hardware with the multiplication of unsigned numbers

Instructions

• mult rs, rt / multu rs, rt (rs: multiplicand, rt: multiplier)
  • The result (product) is stored in HI / LO

• mfhi rd / mflo rd
  • Move from HI / LO to rd

Example: mult $t0, $ t1

• $t0 (multiplicand) is used as the Multiplicand register
• Initially, the value in $t1 (multiplier) is loaded into LO register
• Then, do the multiplication and store the 64-bit product to HI and LO registers