Divider

Weighting a bread loaf with restoration and without restoration

We want to computer Q = A ÷ D. By a stoke of luck, we have available a scale, a white bread whose weight is actually just A and a set of brass weights with values D, 2D, 4D, 8D, .... 2i*D respectively marked with 1, 2, 4, 8, ... 2i.
In fact D is a binary number, and 2i*D is simply obtained by a shift of D. The scale compares the sum of the weights on each of the two plates ( £ or > ).

Digit recurrence division

Division is not frequent. Nevertheless since its execution delay is far larger than the addition or multiplication's one, its impact in the total execution time is substantial, thus it is advisable to design dividers carefully.
Let say that we want Q = A ÷ D. This is equivalent to Q * D = A. Therefore if Q and D are both written onto n bits, A is written onto 2n  bits.
Let us build a series Qn, Qn-1, ... Q2, Q1, Q0 and a series Rn, Rn-1, ... R2, R1, R0 such that the invariant A = Qj * D + Rj holds for all j.
The recurrence is :

  • Qj-1 = Qj + qj-1 * 2j-1                     ( this is merely a concatenation )
  • Rj-1 = Rj – qj-1 * D * 2j-1                ( this is a conditional subtraction )

with initial conditions :

  • Qn = 0
  • Rn = A.

When the recurrence terminates, we have Q = Q0 = Si qi * 2i. R = R0 is the division remainder.

Conditional subtractor

A "conditional subtractor" gives the following result S:
if R < D then S = R else S = R – D ; // S = R modulo D
Each "SC" cell computes both the result ant the carry (borrow) of the subtraction R – D. If the output carry (leftmost) equals '1' then S is assigned the result of the subtraction else S is assigned the value of R. This last case, that seems to "restore" R to its previous value is sometimes called "restoration", from which the divider's name derives.
 

The "conditional subtractor" function: if R < D then S = R else S = R – D, is abstracted by its transfer function called "Robertson's diagram". To converge the division imposes moreover that 0 £ R £ 2*D.

"SC" cell of the conditional subtractor

Check whether you are acquainted with the logic of the "SC" cell :
if q = '0' then { co = majority ( r, d, ci ) ; s = r } // identity
else { co = majority ( r, d, ci ) ; s = r Å d Å ci } // subtraction

Restoring divider

A "restoring" divider consists in a series of shifts and attempted subtractions. It is made of a regular net of conditional subtraction "SC" cell (subtraction or identity according to a carry out bit).

Inverse of the division

If the restoring divider is turned upside-down and the conditional subtractors "SC" are substituted by conditional adders "AC" ( identity or addition according to qi ) the operators delivers the inverse of the division i.e. the multiplication with "remainder" : A = D * Q + R.

Non-restoring divider

A "non-restoring" divider is a sequence of shifts and additions or subtractions. Is made of a regular structure of "AS" cells (addition or subtraction according to q), q is given by the signs of R and D.

  • if R < 0 and D < 0 then {S = R – D ; q = '1'}
  • if R < 0 and D ³ 0 then {S = R + D ; q = '-1'}
  • if R ³ 0 and D < 0 then {S = R + D ; q = '-1'}
  • if R ³ 0 and D ³ 0 then {S = R – D ; q = '1'}

 

The function of a row of "AS" cells is plotted by the "Robertson's Diagram"
if R < 0 then S = R + D else S = R – D.

Advantages and disadvantages of the non-restoring divider

The main advantage is the compatibility with 2's complement notation for dividend A and divisor D. Nevertheless the quotient Q is noted with digits '-1' and '1', it must be converted to 2's complement, which is very simple.

For the division, it is agreed that if the final remainder R is not zero then it must have the same sign as the dividend A. A final quotient Q by +1 or -1 is sometimes necessary for the divider to abide by this convention.

  • if A ³ 0 and R < 0 and D ³ 0 then { Q = Q – 1 ; R = R + D }
  • if A ³ 0 and R < 0 and D < 0 then { Q = Q + 1 ; R = R – D }
  • if A < 0 and R > 0 and D ³ 0 then { Q = Q + 1 ; R = R – D }
  • if A < 0 and R > 0 and D < 0 then { Q = Q – 1 ; R = R + D }

One pathological case remains R = - | D | that must be detected to force R = 0 .

Fast dividers

Three approaches are combined to realize fast dividers:

  • Utilization of carry-propagation-free addition/subtraction.
  • Preconditioning of the dividend and the divisor in order to simplify the division.
  • Use of higher radixes to reduce the number of steps.

Robertson Diagram

For a square Robertson's diagram, the successive partial remainders are normalized: ( Rj * b-j ) where b is the numeration radix.
The black sloops represent the transfer function Rj Þ Rj-1, the red line is the identity function, that passes to the following step. Pulling the mouse out of the pictures suspends the animation. Clicking terminates or restarts the animation. Clicking into the square fixes the starting point.

Radix 10 is familiar to us, it is given here just for illustration because it would not be very efficient in binary. "SRT" is named after D. Sweeney, J. Robertson and K. Tocher, who published simultaneously carry-propagation-free dividers.