Next: Signed Multiplication Up: arithmetic_html Previous: Fast Addition

# Multiplication and Division

Multiplication

Example for multiplication:

The paper-and-pencel method:

Improve the method so that only 2 numbers are added each time:

Algorithm for hardware multiplication

Do n times:

{

if () then ;

right shift A and Q by 1 bit

}

Note: When A and Q are right shifted, the MSB of A is filled with 0 and the LSB of A becomes the MSB of Q, and the LSB of Q is lost.

Example:

Always use three registers M, A, and Q. Initially, the multiplicand is in M, the multiplier is in Q, and A is zero.

The upper half of the product is in register A, while the lower half is in register Q.

Example for division:

Algorithm for hardware division (restoring)

Do n times:

{ left shift A and Q by 1 bit

;

if (), then , (restore)

else

}

Note: When A and Q are left shifted, the MSB of Q becomes the LSB of A, and the MSB of A is lost. The LSB of Q is made available for the next quotient bit.

Example:

Initially, the divisor is in register M, the dividend is in register Q, and register A is zero. Note that subtraction by is implemented by adding its 2's complement .

The quotient is in register Q, and the reminder is in register A.

Algorithm for hardware division (non-restoring)

In the algorithm above, if the subtraction produces a non-positive result (), registers A and Q are left shifted and the next subtraction is carried out. But if the subtraction produces a negative result (), the dividend need be first restored by adding the divisor back before left shift A and Q and the next subtraction:

• If , then (left shift and subtract);
• If , then (restore, left shift and subtract).
Note that when , the restoration is avoided by combining the two steps. This leads to a faster non-restoring division algorithm:

Algorithm for hardware division (non-restoring)

Do n times:

{ left shift A and Q by 1 bit

if (previous ) then

else ;

if (current ) then

else

}

if () then (remainder must be positive)

The quotient is in register Q, and the reminder is in register A. The restoring division requires two operations (subtraction followed by an addition to restore) for each zero in the quotient. But non-restoring division only requires one operation (either addition or subtraction) for each bit in quotient.

Next: Signed Multiplication Up: arithmetic_html Previous: Fast Addition
Ruye Wang 2013-01-25