Non-restoring division with flowchart

Non-restoring division is a division method that avoids the restore step of restoring division. When a subtraction gives a negative remainder, it is not restored; instead the next step adds the divisor. This is because restoring (A + M), shifting (× 2) and subtracting M gives 2(A + M) - M = 2A + M, which is one addition after shifting.

Registers

A (n + 1 bits, initially 0): partial remainder. Q (n bits): dividend, then quotient. M (n bits): divisor. Counter = n.

Algorithm

1. A = 0, Q = dividend, M = divisor, count = n.
2. Repeat n times:
   • If the sign of A is 0 (positive): shift A:Q left one bit, then A = A - M.
   • If the sign of A is 1 (negative): shift A:Q left one bit, then A = A + M.
   • If the new sign of A is 0, set Q0 = 1; else Q0 = 0.
   • Decrement count.
3. After n steps: if A is negative, A = A + M (correct the remainder).
4. Quotient is in Q, remainder is in A.

Flowchart

 Start: A=0, count=n
        |
        v
 A >= 0? --yes--> shift AQ left ; A = A - M
        | no                            |
        +--> shift AQ left ; A = A + M --+
                                        v
                          A >= 0 ? --yes--> Q0 = 1
                                   --no --> Q0 = 0
                                        v
                                  count = count - 1
                                        v
                              count = 0? --no--> (repeat)
                                        | yes
                                A < 0 ? --yes--> A = A + M
                                        v
                                       Stop

Example: 11 ÷ 3 (n = 4)

Dividend Q = 1011, M = 0011, A = 00000 (negative values are shown with a minus sign).

Final A is positive (2), so no correction is needed.

Quotient = 0011 = 3, remainder = 2. Check: 3 × 3 + 2 = 11. ✓