Restoring Division Algorithm in Computer Architecture

Restoring Division Algorithm – The long-hand division algorithm, which we usually perform with pencil and paper, is a trial method. This method faces the difficulty of determining the quotient value. The simplest way implement binary division is to methodically position the divisor with respect to the dividend and perform the subtraction operation.

Restoring Division Implementation

Division is the most difficult and time-consuming operation for a general-purpose computer. The figure below shows the hardware implementation of a 4-bit binary divisor using the restoring technique. Here dividend is stored in register Q (Q₃ Q₂ Q₁ Q₀), the divisor is stored in register M(M₃ M₂ M₁ M₀), and initially, the register A(A₃ A₂ A₁ A₀) is cleared.

Restoring Division Algorithm

Initially, an n-bit positive divisor is stored in register M, and an n-bit positive dividend is loaded into register Q. Register A is set to 0.

The following steps are included in the algorithm to perform the division operation.

Step-1: Shift the combined contents of register A and register Q to the left by one bit.

Step-2: Perform trail subtraction by subtracting the contents of register M from the contents of register A.

Step-3: If there is no borrow in the previous subtraction, put 1 in the LSB of register Q by adding the contents of register M with the contents of register A.

Step-4: Repeat steps 1 to 3 for n times, where n is the number of bits in the dividend.

After performing the division operation, the quotient will be available in register Q, and the remainder will be in register A. The flow chart for the division operation is given in the figure below.

Let’s see an example to understand the Restoring Division Technique.

Example 1: Explain the steps for restoring the division method if the dividend is 1011₂, and the divisor is 0011₂.

Solution:

Given that
Dividend (Q₃Q₂Q₁Q₀) = 1011

Divisor (M₃M₂M₁M₀) = 0011

and initially register A (A₃A₂A₁A₀) = 0000

Since both dividend and divisor are 4-bit numbers; step 1 to 3 have to be repeated four times

Cycle-I

Step-1: Shift the combined contents of A and Q to the left by one bit. Therefore

AQ = 0001 0110

Step-2: Subtract the divisor (0011) from register A, resulting

A=1110 with borrow = 1

Step-3: Since borrow = 1, restore the original content in register A by adding the divisor (0011) to register A (1110). Now

AQ = 0001 0110.

Cycle-II

Step-1: Shift the combined contents of A and Q to the left by one bit. Therefore,

AQ = 0010 1100

Step-2: Subtract the divisor (0011) from register A.

A = 1111 with borrow = 1

Step-3: Since borrow = 1, restore the original contents of A. Now

AQ = 0010 1100

Cycle-III

Step-1: Shift the combined contents of A and Q left by one bit. Therefore

AQ = 0101 1000

Step-2: Subtract the divisor (0011) from register A, which results.

A = 0010 with borrow = 0

Step-3: Since borrow = 0, put 1 in the LSB of Q (Q₀). Therefore

AQ = 0010 1001

Cycle-IV

Step-1: Shift the combined contents of A and Q left by one bit.

AQ = 0101 0010

Step-2: Subtract the divisor (0011) from register A, which results.

A = 0010 with borrow = 0

Step-3: Since borrow=0, put 1 in the Q₀. Therefore

AQ = 0010 0011

Now the quotient 0011 (3) is available in the register Q, and the remainder 0010 (2) is available in the register A.

Q&A Section