Page 88 - Engineering Digital Design

2.9 BINARY ARITHMETIC 59

In this example, not all steps are shown, but the implied division process is

4
A - 2 B = A - 01010000 < 0, Q 4 = 0
3
A -2 £ = A -00101000 < 0, Q 3 = 0
2
A - 2 B = A - 00010100 > 0,
= 00111 = A', 02 = 1
]
A' - 2 B = A'- 00001010 > 0, Q\ - 0
A' - 2°B = A' - 00000101 > 0, Q 0 = 1
= 00000010 = A" = R,

6
7
5
where A - 2 B < 0, A - 2 B < 0, A - 2 #, etc., all yield quotients bits 0 = 0.
Notice that the subtractions can be carried out with 2's complement arithmetic according
to Algorithm 2.9.
The following algorithm generalizes the binary division process as just presented:

Algorithm 2.12: A 2 -=- B 2
(1) Set B to fc-bits and A to (k + n)-bits.
(2) Set i = n — 1 and the remainder = A.
(3) Set Q,; = 1 if R - 2*B > 0 and subtract 2'B from A; otherwise set Q t = 0 if
fl-2''B<0.
(4) Repeat step (2) for i = n — 2, n — 3,..., 1,0 to generate quotient bits Q n-2,
Qn-3, *.., 0i, 0o ending with the final w-bit quotient 0 = Q n-\... 0i 0o-

Binary division involving numbers with fractions is handled in a manner similar to that
for decimals. The bit position of the radix point measured from the LSB in the dividend is
the same for the quotient. If a fraction exists in the divisor, the radix point of the quotient
is that of the dividend minus that of the divisor all taken from the LSB.
Division involving negative numbers is most easily carried out as unsigned division with
the result determined by the normal laws of algebra—that is, operands of like sign produce
a positive quotient, while those of unlike sign produce a negative quotient. The remainder
is given the same sign as the dividend. Signed division can be performed directly by using
2's complement, but the process requires many decision-making steps and, for this reason,
is rarely used.

High-Speed Division by Direct Quadratic Convergence A great deal of effort has
gone into making multiplication as fast and efficient as possible for use in high-speed
computers. So it is only logical that use be made of this fact in generating suitable algorithms
for high-speed division. Such methods, commonly used in modern computers, involve
iterative divide algorithms and are nonrestoring. One such method features a system that
operates on both the dividend D D and the divisor D$ with equal multipliers so as to cause
the divisor to converge quadratically on unity, thereby yielding the dividend as the quotient.
This requires that at least the divisor DS be represented as a fraction. Therefore, in binary