PRACTICAL–3
Implement Non-Restoring Division Algorithm
Aim: To implement the Non-Restoring Division Algorithm for performing binary division
of two unsigned binary numbers.
Objective: To understand the non-restoring binary division technique and perform division using
arithmetic shifting, addition, and subtraction operations.
Theory
1. Introduction
Non-Restoring Division is a binary division algorithm used in computer arithmetic. It is an
improvement over Restoring Division because it does not immediately restore a negative
partial remainder. Instead, the sign of the current partial remainder determines whether the
divisor is added or subtracted in the next iteration.
2. Registers Used
Register Purpose
A Accumulator/partial remainder; initially set to 0
Q Stores the dividend initially and contains the quotient at the end
M Stores the divisor
Count Number of iterations; normally equal to the number of dividend bits
3 Basic Principle
For each iteration, the combined register (A,Q) is shifted left by one bit. If A is non-negative
before the operation, M is subtracted from A. If A is negative, M is added to A. After the
operation, the new quotient bit is determined by the sign of A. Unlike restoring division, a
negative partial remainder is not immediately restored.
After the final iteration, if A is negative, a final correction is performed: A = A + M. The
corrected A is the remainder.
4. Decision Rules
Condition before operation Operation Quotient bit after operation
A≥0 A=A−M 1 if new A ≥ 0, otherwise 0
A<0 A=A+M 1 if new A ≥ 0, otherwise 0
4. Algorithm
1. Start.
2. Read the dividend Q and divisor M.
3. Initialize A = 0 and Count = n, where n is the number of bits in the dividend.
4. Shift the combined register (A,Q) left by one bit.
5. If A is non-negative, perform A = A − M; otherwise perform A = A + M.
6. If the new A is non-negative, set Q₀ = 1; otherwise set Q₀ = 0.
7. Decrement Count.
8. If Count is not zero, repeat from the left-shift step.
9. After all iterations, if A is negative, perform A = A + M.
10. Q contains the quotient and A contains the remainder.
11. Stop.
5. Flowchart
Following is the flowchart of the Booth's Algorithm:
6. Example: Restoring Division
Perform 11 ÷ 3 using the Restoring Division Algorithm.
Dividend = 11 = 1011₂
Divisor = 3 = 0011₂
Number of bits, n = 4
Initially A = 0000, Q = 1011, M = 0011
After Left A after
Iteration A before shift Q Operation Q₀
Shift (A,Q) operation
A≥0→A=A
1 0000 1011 0001 0110 1110 0
−M
A<0→A=A
2 1110 0110 1100 1100 1111 0
+M
A<0→A=A
3 1111 1100 1111 1000 0010 1
+M
A≥0→A=A
4 0010 1001 0101 0010 0010 1
−M
After the fourth iteration, A = 0010 is non-negative, so no final correction is required.
Final Quotient = Q = 0011₂ = 3
Final Remainder = A = 0010₂ = 2
Therefore, 11 ÷ 3 = 3 with remainder 2.
Code and Output:
Conclusion: