Integer Division

Integer Division

• The division process for binary numbers is similar to the decimal numbers. bas Fig. 4.13.1 shows binary division process.

• In the division process, first the bits of the dividend are examined from left to right, until the set of bits examined represents a number greater than or equal to the divisor.

• Until this condition occurs, 0's are placed in the quotient from left to right.

• When the condition is satisfied, a 1 is placed in the quotient and the divisor is subtracted from the partial dividend. The result is referred to as a partial remainder.

• From this point onwards, the division process is required. In each repetition cycle, additional bits from the dividend are brought down to the partial remainder until the result is greater than or equal to the divisor and the divisor is subtracted from the result to produce a new partial remainder.

• The process continues until all the bits of the dividend are brought down and result is still less than the divisor.

Example: 1

Divide (1001010)₂ + (1000)₂

Solution :

 

1. Restoring Division Algorithm

• Fig. 4.13.2 shows the hardware for implementation of restoring division.

• It consists of n+1–bit binary adder, shift, add and subtract control logic and registers A, B and Q.

• As shown in Fig. 4.13.2 divisor and dividend are loaded into register B and register Q, respectively. Register A is initially set to zero. The division operation is then carried out.

• After the division is complete, the n–bit quotient is in register Q and the remainder is in register A.

Division operation steps :

1. Shift A and Q left one binary position.

2. Subtract divisor (i.e. add 2's complement of divisor (B)) from A and place answer back in A (A← A – B).

3. If the sign bit of A is 1, set Q₀ to 0 and add divisor back to A (that is, restore A); Otherwise, set Q₀ to 1.

4. Repeat steps 1, 2, and 3 n times.

A flowchart for division operation is as shown in Fig. 4.13.3.

Example: 2

Perform the division of following numbers using restoring division algorithm :

Dividend = 1 0 1 0

Divisor = 0 0 1 1

Solution :

Fig. 4.13.4 shows steps involved in the above binary division.

Example: 3

Divide the following unsigned numbers using restoring division method

Dividend = 1000,     Divisor = 11

Solution :

Example: 4

Perform the following division using restoring division algorithm :

Dividend 1001

Divisor = 0101.

Solution :

Example: 5

Using restoring division algorithm solve the following :

Dividend = 17

Divisor = 03.

Solution :

Dividend =17 = (10001)₂ → Q

Divisor = 03  = (0011)₂ → B

Example: 6

Perform restoring division when divisor V = 3 and dividend D = 7. Also give the results for all possible combinations of signs of D and V.

Solution :

The restoring division algorithm assumes positive signs of D and V.

Remainder = (0001)₂ = 1 and Quotient = (0010)₂ = 2

In the division operation, the magnitudes of quotient (Q) and remainder (R) are not affected by the input signs. The signs of Q and R are easily derived from the signs of D and V using expression : D = Q × V + R.

The signs of Q and R for all possible combinations of signs of D and V are as follows :

D = 7,      V = 3        =˃    Q = 2, R = 1

D = 7,      V = – 3     =˃     Q = – 2, R = 1

D = –7,     V = 3       =˃     Q = – 2, R = – 1

D= –7,    V = – 3       =˃     Q = 2, R = –1

Example for Practice

Example: 7  

Demonstrate the division of 1100₂ by 101₁ using restoring method, draw block diagram and explain the operation.

 

Review Questions

1. Explain the restoring division algorithm.

2. Discuss in detail about division algorithm in detail with diagram and examples.

 

2. Non–Restoring Division

• Consider the sequence of operations that takes place after the subtraction operation in the restoring algorithm.

If A is positive

Shift left and subtract divisor→ 2A – B

If A is negative

Restore → A + B

Shift left and subtract divisor→ 2 (A+B) – B

≡ 2A + B

• Looking at the above operations we can write following steps for non–restoring algorithm.

Step 1 : If the sign of A is 0, shift A and Q left one bit position and subtract divisor from A; otherwise, shift A and Q left and add divisor to A. If the sign of A is 0, set Q₀ to 1; otherwise, set Q₀ to 0.

Step 2 : Repeat steps 1 and 2 for n times.

Step 3 : If the sign of A is 1, add divisor to A.

Note : Step 3 is required to leave the proper positive remainder in A at the end of n cycles.

• A flowchart for non–restoring division operation is as shown in Fig. 4.13.7. (See Flowchart on next page)

Example: 8

Perform the division of following numbers using non–restoring division algorithm :

Dividend = 1 0 1 0

Divisor = 0 0 1 1

Solution :

Fig. 4.13.8 shows steps involved in the non–restoring binary division.

In this example, after 4 cycles A is positive and hence step 3 is not required.

Example: 9

Perform the division of following numbers using non–restoring division algorithm:

Dividend = 1 0 1 1

Divisor = 0 1 0 1

Solution :

• Fig. 4.13.9 shows steps involved in the non–restoring binary division.

• The hardware shown in Fig. 4.13.2 can also be used to perform non–restoring algorithm.

There is no simple algorithm for signed division. In signed division, the operands are pre–processed to transform them into positive values. Then using one of the algorithms just discussed quotients and remainders are calculated. The quotients and remainders are then transformed to the correct signed values.

Example: 10

Explain non–restoring division algorithm for performing 19/4.

Solution :

Divided = 19 = 0 1 0 0 1 1

Divisor = 4 = 0 1 0 0

Example: 11

In a small town there are three temples in a row and a well in front of each temple. A pilgrim came to the town with certain number of flowers.

Before entering the first temple, he washed all the flowers he had with the water of well. To his surprise, flowers doubled. He offered few flowers to the God in the first temple and moved to the second temple. Here also, before entering the temple he washed the remaining flowers with the water of well. And, again his flowers doubled. He offered few flowers to the God in second temple and moved to the third temple. Here also, his flowers doubled after washing them with water. He offered few flowers to the God in third temple.

There were no flower left when pilgrim came out of third temple and he offered same number of flowers to the God in all three temples. What is the minimum number of flowers the pilgrim had initially (X)? And, find the value of (X/3) using restoring division method. How many flower did he offer to each God (Y) ? And, find the value of (Y/3) using non–restoring division method.

Solution :

Assume that the pilgrim had X flowers initially and he offered Y flowers to each God from the data in the puzzle we have.

[(2X–Y) × 2 –Y] × 2–Y = 0

[4X – 2Y – Y] × 2–Y = 0

(8X – 6Y)– Y= 0

8X–7Y = 0 or

8X = 7Y

The minimum values of X and Y are 7 and 8 respectively to satisfy the above equation. Hence, the pligrim had 7 flowers and he offered 8 flowers to each God.

X/3 using restoring division method : 7/3

Refer example : 6

Y/3 using non–restoring division method : 8/3

Examples for Practice

Example: 12

Explain non–restoring division algorithm with the help of suitable example.

Example: 13

Perform the division on the following 5–bit unsigned integer using non–restoring division: 10101/ 00101.

 

Review Questions

1. Explain non–restoring division algorithm with the help of suitable example.

2. Draw the block diagram of integer divider and explain the division algorithm.

 

3. Comparison between Restoring and Non–Restoring Division Algorithm

Non–restoring

1. Needs restoring of register A if the result of subtraction is negative.

2. In each cycle content of register A is first shifted left and then divisor is subtracted from it.

3. Does not need restoring of remainder.

4. Slower algorithm.

Restoring

1. Does not need restoring.

2. In each cycle content of register A is first shifted left and then divisor is added or subtracted with the content of register A depending on the sign of A.

3. Needs restoring of remainder if remainder is negative.

4. Faster algorithm.

 

Review Question

1. Compare restoring and non–restoring division algorithm.