Restoring vs Non-Restoring Division and Booth's Algorithm: Step Tables for a Small Example

The Computer Arithmetic unit of TU BSc CSIT Computer Architecture (CSC213) produces one long-answer question almost every year, and it is always one of three: "Perform restoring division on the given numbers", "Perform non-restoring division" or "Multiply using Booth's algorithm, showing each step". BIT students meet the same three in the Fixed Point Arithmetic unit of BIT151.

The marks come from the table. Examiners look for the registers at every step, the operation performed, and the correct final result. This article works each algorithm on a small example so the pattern of the table is clear, then states the differences that the "compare restoring and non-restoring division" question expects. The unit notes and solved papers are on the Computer Arithmetic notes page.

Registers used

All three algorithms use the same hardware model. A holds the partial remainder (division) or the partial product (multiplication). Q holds the dividend and then the quotient (division), or the multiplier (multiplication). M holds the divisor or multiplicand. A counter n holds the number of bits. Booth's algorithm adds a one-bit register Q-1 to the right of Q.

The examples below use 4-bit registers, dividend 7 and divisor 2 for division, and multiplicand 3 and multiplier -2 for Booth. Write the bit width you are using at the top of the answer.

Restoring division: 7 divided by 2

Initial values: A = 0000, Q = 0111 (7), M = 0010 (2), n = 4.

The algorithm, repeated n times: shift A and Q left one bit together; subtract M from A; if A is negative, set Q0 = 0 and restore A by adding M back; otherwise set Q0 = 1.

Result: quotient Q = 0011 = 3, remainder A = 0001 = 1. Check: 7 = 2 x 3 + 1.

Subtracting M is done by adding the two's complement of M, which for 0010 is 1110. Show this once in the answer so the examiner sees you know how the subtraction is performed.

Non-restoring division: 7 divided by 2

The restoring step is wasteful: when A goes negative we add M back, then at the next step shift and subtract M again. Non-restoring division skips the restore. If A is negative after a step, the next step shifts and adds M instead of subtracting. The arithmetic works because shifting a negative A and then adding M gives 2A + M, which equals 2(A + M) - M, exactly the value restoring would have produced.

The algorithm, repeated n times: if A is non-negative, shift AQ left and subtract M; if A is negative, shift AQ left and add M. Then set Q0 = 1 if the new A is non-negative, else Q0 = 0. After the loop, if A is negative, add M once to get the true remainder.

Result: quotient 0011 = 3, remainder 0001 = 1, the same as before, with no restore operations.

Restoring versus non-restoring: the comparison

The non-restoring method is faster because it never performs the restoring addition; its only extra work is the single correction at the end.

Booth's algorithm: 3 times -2

Booth's algorithm multiplies signed numbers in two's complement directly, and it runs faster when the multiplier contains long runs of 1s, because a run of 1s needs only one subtraction at its start and one addition at its end instead of an addition for every 1 bit.

Initial values: M = 0011 (3), Q = 1110 (-2), A = 0000, Q-1 = 0, n = 4.

The algorithm, repeated n times: look at the pair (Q0, Q-1). If it is 10, A = A - M. If it is 01, A = A + M. If it is 00 or 11, do nothing. Then perform an arithmetic shift right on A, Q, Q-1 together (the sign bit of A is copied into itself, the old Q0 moves into Q-1).

Result: the product is A joined with Q = 1111 1010, which in 8-bit two's complement is -6. Check: 3 x (-2) = -6.

Two things examiners check. First, the shift must be arithmetic: the leftmost bit of A is preserved, which is why A became 1110 and not 0110 after step 2. Second, Q-1 receives the bit that falls off the right end of Q at every shift.

Booth's algorithm flowchart in words

If the question asks for the flowchart, draw it in this order: start; load M with the multiplicand, Q with the multiplier, A = 0, Q-1 = 0, count = n; a decision box on the pair Q0 Q-1 with three exits (10 goes to A = A - M, 01 goes to A = A + M, 00 or 11 goes straight on); an arithmetic shift right of A, Q, Q-1; count = count - 1; a decision "count = 0?" that loops back to the pair test if not; end with the product in A and Q. The restoring division flowchart has the same shape with the shift first, then A = A - M, then a decision on the sign of A with the restore branch.

Which numbers to practise with

The paper usually gives dividend and divisor, or multiplicand and multiplier, as small decimal numbers and expects you to choose a bit width. Use one more bit than the largest magnitude needs, so that the sign bit is free, and state the width. Practise at least one division where the quotient has a 1 in its leftmost bit, one Booth multiplication with a negative multiplicand, and one with both operands negative; the sign handling is where marks are lost.

Solved past paper versions of all three questions, with the full tables, are on the CSC213 Computer Architecture page. BIT students find the same algorithms in the Fixed Point Arithmetic Algorithms unit of BIT151.