Multiplication

contents: 0-1. CA Intro

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