Let and be rational numbers, pre-scaled so that and . Our objective is to compute a sequence of approximations that converges to the quotient . This is achieved by an iterative process that generates a sequence of partial remainders, , and partial quotients, . On each iteration, the current partial remainder is shifted by bits, where is the underlying radix of the computation, and a multiple of the divisor is subtracted to form the next partial remainder, while the quotient digit contributes to the partial quotient:
PROOF: The claim is trivial for , and for ,
The quotient digit is selected from the range and is required to preserve the invariant . Thus, our objective may be formulated as follows:
Given a positive integer and rationals and with and , find an integer such that and .The crux of the SRT algorithm is that the value of is read from a fixed table, using indices derived from truncated approximations of and . Let and denote the widths of the indices corresponding to and , respectively. We have approximations of , occurring at equal sub-intervals (of length ) of the interval , and approximations of occurring at equal sub-intervals (of length ) of the interval .
As illustrated in Figure 14.1 for the case , , and , the sub-intervals of are numbered from left to right. For given , and for , we shall denote the lower endpoint of sub-interval as . Thus, represents the fractional part of , i.e.,
are numbered so that each is the -bit two's complement representation of the lower endpoint of sub-interval . Thus, for ,
The divisor is approximated by some and at each iteration, the partial remainder is approximated by some . The index is simply extracted from the leading fractional bits of , and hence the error is bounded by
We shall develop a procedure for generating a table of minimal dimensions that provides a quotient digit satisfying for all . Note that this constraint is equivalent to
The following definition presents a formulation of the table requirements that allows straightforward computational verification:
PROOF: First note that if lies either entirely above the line or entirely below the line , then no constraint is imposed on . In the first case, the lower right vertex of , , must lie on or above , a condition expressed by the inequality
Since , the upper bound is satisfied trivially if . Therefore, a necessary and sufficient condition to ensure that this bound holds generally is that if , then does not intersect the region between the lines and , or equivalently, that lies entirely below the latter of the two. The maximum value of the quotient in occurs at either the upper left or the upper right vertex, depending on the sign of their common -coordinate, . If or , then and the critical vertex is the upper left, , so the requirement is
Similarly, since , the lower bound
If , then the critical vertex is the lower right, and the requirement is
The following is an immediate consequence of Lemmas 14.1.1 and 14.1.2:
Definition 14.1.1 provides simple procedures that (a) determine the existence of an admissible SRT table for given radix and dimensions and (b) construct one if possible:
For each of these tables, the following conditions may be verified by inspection of the graph for each entry :
Note that in some cases, there is a choice between two acceptable values of . If lies within the region bounded by and , where , then the required inequalities are satisfied by both and . For example, in the radix-4 table of Figure 14.1, although we have assigned 2 as the value of , since lies between and , we could have chosen 1 instead.
It is clear that a necessary and sufficient condition for the existence of an admissible radix- table is that each straddles at most one of the lines , . For example, if we attempt to construct a radix-8 table, thereby doubling the height of the rectangular elements shown in Figure 14.2, we find that the uncertainty rectangle intersects both and , requiring that satisfy both and . In fact, these indices are identified by executing the function ExistsDivTable.
The admissibility of a division table may be checked visually by examining the bold “staircases” that bound the regions of constant value. Suppose that and are separated by a segment of such a staircase, i.e., and . Since is contained in both and , it must lie above the line and below . That is, a staircase that separates the regions on which and must lie entirely above , and when shifted up through one sub-interval, it must still lie below .
David Russinoff 2017-08-01