Non-Restoring Division in Binary Arithmetic
Non-restoring division is an efficient hardware algorithm used in digital computing to perform binary division without the performance penalty of restoring intermediate values. In traditional restoring division, if a trial subtraction yields a negative result, the system must perform an extra addition step to restore the previous remainder. Non-restoring division eliminates this redundant step by deferring the correction to the next operational cycle, significantly increasing quotient calculation speed and reducing hardware complexity in computer processors.
The Principle of Non-Restoring Division
In standard binary division, the hardware shifts the partial
remainder and subtracts the divisor. If the subtraction results in a
negative value (indicated by a sign bit of 1), the algorithm determines
that the divisor does not fit, sets the current quotient bit to
0, and adds the divisor back to restore the previous state
before shifting again.
Non-restoring division removes the need to undo this negative subtraction immediately. Instead, it leverages algebraic equivalence across consecutive cycles:
- If the current partial remainder is positive or
zero:
- Set the current quotient bit to
1. - Shift the remainder left by one bit (\(2R\)).
- Subtract the divisor (\(D\)) in the next step: \(R_{next} = 2R - D\).
- Set the current quotient bit to
- If the current partial remainder is negative:
- Set the current quotient bit to
0. - Shift the negative remainder left by one bit (\(2R\)).
- Add the divisor (\(D\)) in the next step: \(R_{next} = 2R + D\).
- Set the current quotient bit to
Because shifting a negative remainder of \((R - D)\) results in \(2(R - D) = 2R - 2D\), adding \(D\) in the subsequent cycle yields \(2R - 2D + D = 2R - D\). This mathematically achieves the exact same state as restoring the remainder first and then subtracting, but requires half the arithmetic steps.
How Non-Restoring Division Accelerates Computation
1. Halving the Worst-Case Operations
Restoring division can require up to two arithmetic operations per bit (one subtraction and one conditional addition). Non-restoring division guarantees exactly one arithmetic operation (either an addition or a subtraction) per bit cycle, dramatically cutting down the total execution time for division operations.
2. Predictable Cycle Times and Simpler Control Logic
Because every step consists strictly of one shift and one add/subtract operation, the execution timing is constant and predictable. Hardware designers can construct synchronous clock pipelines without handling variable delays caused by conditional restoration branches.
3. Reduced Propagation Delay in Hardware
Arithmetic Logic Units (ALUs) implementing non-restoring division experience less internal switching and lower propagation delay. The decision to add or subtract in step \(k+1\) is directly dictated by the sign bit of step \(k\), allowing direct multiplexer routing rather than sequential add-back hardware loops.
Final Correction
If the final partial remainder remains negative after all quotient bits have been determined, a single addition of the divisor is performed at the very end to yield the true positive remainder. Because this correction occurs at most once per entire division operation rather than once per bit, it introduces negligible overhead compared to the cumulative performance gains.