**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).

**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.