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 possible doing an add or subtract.

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 divisor) 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