Division

contents: 0-1. CA Intro

Division

If the length of Dividend and Divisor is M and N,

the length of Quotient $\leqq$ M - N + 1 & the length of Remainder $\leqq$ N

• In MIPS-based computers, 32 bits are used to represent both Dividend and Divisor.
  Therefore, the length of both Quotient and Remainder $\leqq$ 32

Optimized version of the division HW

• 32-bit divisor register / ALU

• 64-bit remainder register (dividend and quotient shares a register with remainder)

    - HI: Remainder

    - LO: Quotient

Settings

• 0 is stored in the left half of the Remainder register

• The value of dividend is loaded into the right half of the Remainder register

• The value of divisor is loaded into the Divisor register

Division Algorithm

Example

When N = 4 (4-bit ALU / divisor, 8-bit product), $7 \div 3$

• should be repeated as many bits + 1 as it is

Signed division

Do division after converting both divisor & dividend to positives

After the division

• Negate the quotient only if the signs of the divisor and dividend are different

• Remainder's sign follows Dividend's sign

Instructions

• div rs, rt / divu rs, rt : do $rs / $st

    - The result (remainder and quotient) is stored in HI / LO

    - No overflow or divide-by-0 checking

Example:

• Initially, the value in $t0 (dividend) is loaded into the LO register

• Initially, $t (divisor) is used as the divisor register

• Then, do the division and store the remainder and quotient to HI and LO registers

Summary: Design for arithmetic operations

Addition & Subtraction

Use the same HW for addition and subtraction

• 32-bit parallel adder

• Additional XOR operators + subtract bit

Multiplication & Division

Use the same optimized HW for Multiplication and Division

• A single 32-bit register for multiplicand and divisor

• A single 32-bit ALU

• HI and LO registers for the results of multiplication and division