To study and simulate the Non-Restoring Division Algorithm for unsigned binary integers. The simulator visualizes the optimized process that eliminates the extra "restore" step found in the Restoring algorithm by changing whether it adds or subtracts the divisor based on the sign of the partial remainder.
Theory
Restoring vs. Non-Restoring
In the Restoring Division algorithm, if subtracting the divisor yields a negative result, we "restore" the previous value by immediately adding the divisor back: A = (A - M) + M. Then, in the next iteration, we shift left and subtract M again: A = 2A - M.
Non-Restoring Division optimizes this. Instead of restoring A and then doing 2A - M, it simply leaves the negative result in A, shifts it left (which becomes 2(A - M) = 2A - 2M), and then adds M in the next step: 2A - 2M + M = 2A - M. Mathematically, the result is identical, but it saves one ALU operation per iteration!
Registers Used
M (Divisor): Holds the divisor (n bits).
Q (Dividend / Quotient): Initially holds the dividend.
A (Accumulator / Remainder): Initially 0. Holds the partial remainder.
Count: Counter initialized to n.
The Algorithm Steps
For an n-bit division, initialize A = 0, Q = Dividend, M = Divisor. Then repeat n times:
Check Sign of A:
If A ≥ 0 (Sign bit is 0): Shift Left AQ, then Subtract M (A = A - M).
If A < 0 (Sign bit is 1): Shift Left AQ, then Add M (A = A + M).
Set Quotient Bit (Q0):
If new A ≥ 0 (Sign bit is 0): Q0 = 1.
If new A < 0 (Sign bit is 1): Q0 = 0.
Decrement Count: Reduce count by 1.
Final Correction Step: After all n iterations, if A is negative (A < 0), we must restore A one final time to get the correct positive remainder: A = A + M.
Worked Example: 7 ÷ 3
Let n = 4. Dividend Q = 7 (0111). Divisor M = 3 (0011). A = 00000.
What makes non-restoring division more efficient than restoring division?
a) It uses a faster clock cycle
b) It avoids the intermediate "restore" addition step during iterations
c) It multiplies instead of dividing
d) It processes two bits per cycle
Answer: b) Non-restoring division eliminates the extra addition (restore) step by cleverly using an add operation in the next cycle if the current remainder is negative.
Question 2
In non-restoring division, if the current A is negative (A < 0), what operation is performed after shifting?
a) A = A - M
b) A = A + M
c) A is shifted right
d) The process halts
Answer: b) If A is negative, we add M (A = A + M) in the next step to implicitly "restore" the deficit from the previous over-subtraction.
Question 3
If the current A is positive or zero (A ≥ 0), what operation is performed after shifting?
a) A = A - M
b) A = A + M
c) A = M - A
d) No operation is performed
Answer: a) If A is positive, we proceed normally by subtracting the divisor (A = A - M).
Question 4
At the end of the non-restoring division algorithm, what is the final correction step if A is negative?
a) A = A - M
b) A = A + M
c) Q = Q - 1
d) None; A is allowed to be negative
Answer: b) Because the final remainder must be a positive number, if A ends up negative, we must perform a final restoration (A = A + M).
Question 5
How is the quotient bit Q0 set in each iteration?
a) Q0 = 1 if the new A is positive, 0 if negative
b) Q0 = 1 if the new A is negative, 0 if positive
c) It is always set to 1
d) It is derived from the carry out of the adder
Answer: a) Regardless of whether we added or subtracted, we look at the resulting A. If A ≥ 0, Q0 = 1. If A < 0, Q0 = 0.
Procedure
Follow these steps to operate the Non-Restoring Division Simulator:
1
Navigate to the Simulation tab to access the non-restoring division datapath.
2
Set Divisor (M): Click the bit buttons (M3–M0) to enter the 4-bit unsigned divisor. Ensure it is not zero.
3
Set Dividend (Q): Click the bit buttons (Q3–Q0) to enter the 4-bit unsigned dividend.
4
Run the Simulation: Click the "Divide" button.
5
Observe Iteration Steps: Watch the Iteration Table. Notice that each step has a Left Shift followed immediately by either A = A - M or A = A + M. The standalone "Restore A" step is gone.
6
Check the Correction Step: Look closely at the end of the simulation. If the final A value in the iteration table was negative, you will see an extra "Final Restore" step added to correct the remainder.