Computer Arithmetic - Fundamentals of Computer Organization and Architecture - page 72

Figure 4.9 Hardware structure implementing Booth's algorithm

becomes a repeated pair of a 0 (1) followed by a 1(0). This last situation can be
improved if three rather than two bits are inspected at a time.

Division Among the four basic arithmetic operations, division is considered the

most complex and most time consuming. In its simplest form, an integer division oper-
ation takes two arguments, the dividend X and the divisor D. It produces two outputs,
the quotient Q and the remainder R. The four quantities satisfy the relation X ¼
Q D þ R where R , D. A number of complications arise when dealing with
division. The most obvious among these is the case D ¼ 0. Another subtle difficulty

is the requirement that the resulting quotient should not exceed the capacity of the reg-
ister holding it. This can be satisfied if Q , 2 n 1 ,wheren is the number of bits in the
register holding the quotient. This implies that the relation X , 2 n 1 D must also be
satisfied. Failure to satisfy any of the above conditions will lead to an

overflow

condition.
We will start by showing the division algorithm assuming that all values
involved, that is, divided, divisor, quotient, and remainder are interpreted as frac-
tions. The process is also valid for integer values as will be shown later.
In order to obtain a positive fractional quotient Q ¼

0q 1 q 2 q n 1 , the division
operation is performed as a sequence of repeated subtractions and shifts. In each
step, the remainder should be compared with the divisor D. If the remainder
is larger, then the quotient bit is set to “1”; otherwise the quotient bit is set to
“0”. This can be represented by the following equation r i ¼

2r i 1 q i D
where r i and r i 1 are the current and the previous remainder, respectively, with r 0 ¼
X and i ¼ 1, 2, ... ,(n 2 1).

Example Consider the division of a dividend X ¼ 0.5 (0.100000) and a divisor

¼

D ¼ 0.75 (0.1100). The process is illustrated in the following table.

¼

r 0 ¼ X 0 † 100000Initial values
2r 0 01 † 00000 et q 1 ¼ 1
2 D þ 11 † 010
r 1 ¼ 2r 0 2 D 00 † 01000
2r 1 00 † 1000 et q 2 ¼ 0