Multiplication and Division

Multiplication and division both involve shifting together with addition or subtraction. They can be implemented with an ALU that can add or subtract and some modified shift-register circuitry.

Multiplication Terminology

The terms multiplicand, multiplier, and product are defined by their roles in the multiplication algorithm as shown below.

multiplicand
  multiplier
————————————
      ·
      ·
      ·
————————————
     product

Division Terminology

The terms divisor, dividend, quotient, and remainder are defined by their roles in the division algorithm as shown below.

         quotient
        —————————
divisor/ dividend
            ·
            ·
            ·
        —————————
        remainder

Implementation

Multiplication and division can both be done with the circuit shown above. To multiply two 32-bit numbers MD, Lo, and Hi are each 32-bit registers. Lo and Hi and the multiplexer work together as a modified 64-bit shift register. Both operations involve 32 shift steps with the ALU possibly doing an add or subtract in each step.

The control for the two operations differs in several ways:

• initialization of register contents
• direction of shifting
• determination of the operation performed by the ALU
• filling
• register contents when done

Multiplication

When used for multiplication:

• MD initially contains the multiplicand and Lo contains the multiplier; Hi is initially 0
• each step shifts Hi/Lo to the right
• the ALU either adds the MD register (the multiplicand) to its Hi input or passes the Hi input through unchanged depending on the low-order bit of Lo
• the carry bit from the ALU supplies the fill bit
• Hi/Lo contains the 64-bit product

Division

When used for division:

• MD initially contains the divisor and Hi/Lo contains the dividend
• each step shifts Hi/Lo to the left
• the ALU either subtracts the MD register (the divisor) from its Hi input or passes the Hi input through unchanged depending on whether or not Hi is greater than or equal to MD
• the fill bit on the right indicates if a subtraction is done (1) or not (0)
• Lo contains the quotient and Hi contains the remainder