Non-Restoring Division Algorithm for Unsigned Integers: An Efficient Approach

Learn about the non-restoring division algorithm, an efficient method for performing division on unsigned integers. This guide explains the algorithm's steps, its differences from restoring division, and its advantages in terms of speed and computational efficiency.

Non-Restoring Division Algorithm for Unsigned Integers

Understanding Non-Restoring Division

Non-restoring division is an algorithm for performing division on unsigned integers. Unlike restoring division, it avoids the step of restoring the previous value of the dividend after a subtraction results in a negative value. This makes it potentially faster but slightly more complex to understand.

The Non-Restoring Division Algorithm

The algorithm uses the quotient digit set {-1, 1} instead of {0, 1}. Assume:

  • N: Number of bits in the dividend
  • M: Divisor (loaded into register M)
  • Q: Dividend (loaded into register Q)
  • A: Remainder (initialized to 0)

The steps are:

  1. Initialization: Set A = 0, load M with the divisor, load Q with the dividend.
  2. Check Sign of A: Examine the sign bit of A.
  3. Shift and Add/Subtract:
    • If A is positive (sign bit 0): Shift A and Q left, then perform A = A - M.
    • If A is negative (sign bit 1): Shift A and Q left, then perform A = A + M.
  4. Set Quotient Bit:
    • If A is positive (sign bit 0): Set the least significant bit of Q to 1.
    • If A is negative (sign bit 1): Set the least significant bit of Q to 0.
  5. Decrement Counter: Decrement N (the counter).
  6. Repeat: Repeat steps 2-5 until N = 0.
  7. Final Correction (if necessary): If A is negative, add M to A.
  8. Result: The quotient is in Q, and the remainder is in A.

Example: Non-Restoring Division

(The example from the original text performing the non-restoring division algorithm for 11 divided by 3 is shown here. The table showing the step-by-step register values and operations is given in the original text and should be recreated here.)

Conclusion

The non-restoring division algorithm provides a potentially faster method for unsigned integer division compared to the restoring method by reducing the number of operations. While slightly more complex, it avoids the extra addition step required in restoring division.