Mumbai University > Information Technology> sem 4> computer organization and architecture

Marks: 5M

Year: Dec16

Non-restoring division Algorithm

Algorithm for Non-restoring division is given in below image :

• A variant that skips the restoring step and instead works with negative residuals

• If P is negative

1. (i-a) Shift the register pair (P,A) one bit left

2. (ii-a) Add the contents of register B to P

• If P is positive

1. (i-b) Shift the register pair (P,A) one bit left

2. (ii-b) Subtract the contents of register B from P

• (iii) If P is negative, set the low-order bit of A to 0, otherwise set it to 1

• After n cycles

1. The quotient is in A

2. If P is positive, it is the remainder, otherwise it has to be restored (add B to it) to get the remainder

Example:

Dividend (A) = 101110, ie 46, and Divisor (B) = 010111, ie 23.

Initialization :

Set Register A = Dividend = 000000

Set Register Q = Dividend = 101110

( So AQ = 000000 101110 , Q0 = LSB of Q = 0 )

Set M = Divisor = 010111, M' = 2's complement of M = 101001

Set Count = 6, since 6 digits operation is being done here.

After this we start the algorithm, which I have shown in a table below :

In table, SHL(AQ) denotes shift left AQ by one position leaving Q0 blank.

Similarly, a square symbol in Q0 position denote, it is to be calculated later