TABLE OF CONTENTS There are two different approaches to the development of algorithms for high-speed division. The more conventional approach uses add/subtract and shift operations, while the second relies on multiplication. The operation count in the first approach is linearly proportional to the word size, n. The number of steps in the second approach is logarithmically proportional to n, but each individual step is more complex. The first approach is discussed in this chapter while the second is presented in Chapter 8.
The most well known division algorithm of the first type is the SRT division, named after Sweeney, Robertson, and Tocher ([11], [15], [19]), each of whom developed it independently at around the same time. The motivation behind the SRT algorithm was an attempt to speed up the nonrestoring division (which consists of n add/subtract operations and is presented in Chapter 3) by allowing 0 to be a quotient digit for which no add/subtract operation is needed. In principle, we can change the rule for selecting the quotient digit in the nonrestoring division to
and the corresponding new remainder is
This modified nonrestoring division is diagrammed in Figure 7.1. The difficulty with this new selection rule is that a full comparison of 2 r i ?1 with either D or ? D is required. If we restrict D to be a normalized fraction satisfying 
, we may reduce the region of 2 r i ?1, for which q i=0,...
