14.1  SRT Division and Quotient Digit Selection

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:

(div-remainder-formula, div-remainder-formula-corollary)
Given , and . Let , , and for ,

and

where . Then for all ,

Thus, if and , then

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.,

The sub-intervals of are numbered so that each is the -bit two's complement representation of the lower endpoint of sub-interval . Thus, for ,

These partitions produce a matrix of rectangles in the -plane, each of width and height . Let denote the rectangle with lower left vertex , and let denote the rectangle with the same lower left vertex and width and twice the height, i.e., for and ,

and

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

The approximation of is more subtle because our implementation does not compute explicitly. As a practical matter, a full carry-propagate addition cannot be executed in the same cycle as the table access, and consequently is represented in a carry-save form, i.e., as a sum of two terms. These terms are both truncated to bits and the results are added to produce the approximation of . Thus, the resulting error may approach twice the distance between successive approximations:

i.e., is confined to the uncertainty rectangle .

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

and therefore the sign of each table entry is determined by that of and need not be stored explicitly by an implementation. Thus, such a table consists of at most -bit entries.

The following definition presents a formulation of the table requirements that allows straightforward computational verification:

(admissible-div-table-p) Let , , and be positive integers and let be an integer-valued function of two integer variables. Then is an admissible radix- SRT division table if for all and , if , , and

then

max

where

and

Let , , and be positive integers and let be an integer-valued function of two integer variables. Then is an admissible radix- SRT division table if and only if for all i, j, p, and d, if , , , and , then satisfies and

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

The second case similarly depends on the location of the upper right vertex, , and is characterized by

Thus, the constraint on is in force only if neither of these inequalities holds, i.e.,

Suppose that this condition holds for indices and and let . Then all with must satisfy

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

If , then and consideration of the upper right vertex yields

In all cases, the required upper bound is satisfied if and only if .

Similarly, since , the lower bound

is satisfied trivially if . To guarantee that this bound holds generally, it must be shown that if , then each point in lies on or above the line . The minimum value of in occurs at either the lower left or the lower right vertex, depending on the sign of .

If , then the critical vertex is the lower right, and the requirement is

If , then consideration of the lower left vertex yields

In all cases, the required lower bound is satisfied if and only if

The following is an immediate consequence of Lemmas 14.1.1 and 14.1.2:

Theorem 14..1   (srt-div-theorem-a, srt-div-theorem-b) Let , , and be positive integers and let be an admissible radix- SRT division table. Let and such that and . Let , , and for ,

and

where . Assume that for all , if , then , where . Then for all , and

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:

Lemma 14.1.3   (div-table-existence-a, div-table-existence-b) Let , , and be positive integers. There exists an admissible radix- SRT division table if and only if for all and with and , if

then . In this case, one such table is defined by

max

These procedures are implemented by the functions ExistsDivTable and SRTTableEntry, as displayed in the appendix. By direct computation of the former, it is readily shown that for , the smallest admissible division table has dimensions and , and that for , the smallest table has and . These two tables, as generated by SRTTableEntry, are displayed in Figures 14.1 and 14.2, in which each value is indicated by a label associated with .

For each of these tables, the following conditions may be verified by inspection of the graph for each entry :

1. If intersects the region , then is defined and .
2. If is defined and , then each point in lies below the line .
3. If is defined and , then each point in lies on or above the line .
As argued in the proof of Theorem 14.1, it follows that is an admissible radix division SRT table.

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