14.1  SRT Division and Quotient Digit Selection

Let $ x$ and $ d$ be rational numbers, pre-scaled so that $ 1 \leq d < 2$ and $ \vert x\vert < d$. Our objective is to compute a sequence of approximations that converges to the quotient $ \frac{x}{d}$. This is achieved by an iterative process that generates a sequence of partial remainders, $ p_0=x,p_1,\ldots,p_n$, and partial quotients, $ q_0=0,q_1,\ldots,q_n$. On each iteration, the current partial remainder $ p_{k-1}$ is shifted by $ \rho$ bits, where $ 2^\rho$ is the underlying radix of the computation, and a multiple $ m_kd$ of the divisor is subtracted to form the next partial remainder, while the quotient digit $ m_k$ contributes to the partial quotient:

  (div-remainder-formula, div-remainder-formula-corollary)
Given $ \rho \in \mathbb{N}$, $ d \in \mathbb{Q}$ and $ x \in \mathbb{Q}$. Let $ p_0 = x$, $ q_0 = 0$, and for $ k>0$,

$\displaystyle p_k = 2^\rho p_{k-1} - m_kd$

and

$\displaystyle q_k=q_{k-1}+2^{-k\rho} m_k,$

where $ m_k \in \mathbb{Z}$. Then for all $ k \geq 0$,

$\displaystyle p_k = 2^{k\rho}(x - q_kd).$

Thus, if $ d > 0$ and $ -d \leq p_k < d$, then

$\displaystyle -2^{-k\rho} \leq \frac{x}{d} - q_k < 2^{-k\rho}.$

PROOF: The claim is trivial for $ k=0$, and for $ k>0$,

$\displaystyle 2^{k\rho}(x-q_kd)$ $\displaystyle =$ $\displaystyle 2^{k\rho}(x-(q_{k-1}+2^{-k\rho}m_k)d)$  
  $\displaystyle =$ $\displaystyle 2^{k\rho}(x-q_{k-1}d)-m_kd$  
  $\displaystyle =$ $\displaystyle 2^\rho p_{k-1}-m_kd$  
  $\displaystyle =$ $\displaystyle p_k. $  

The quotient digit $ m_k$ is selected from the range $ 1-2^\rho
\leq m_k \leq 2^\rho-1$ and is required to preserve the invariant $ -d \leq p_k < d$. Thus, our objective may be formulated as follows:

Given a positive integer $ \rho$ and rationals $ d$ and $ p$ with $ 1 \leq d < 2$ and $ -d \leq p < d$, find an integer $ m$ such that $ \vert m\vert < 2^\rho$ and $ -d \leq 2^{\rho}p-md < d$.
The crux of the SRT algorithm is that the value of $ m$ is read from a fixed table, using indices derived from truncated approximations of $ p$ and $ d$. Let $ M$ and $ N$ denote the widths of the indices corresponding to $ p$ and $ d$, respectively. We have $ 2^N$ approximations of $ d$, occurring at equal sub-intervals (of length $ 2^{-N}$) of the interval $ 1 \leq d < 2$, and $ 2^M$ approximations of $ p$ occurring at equal sub-intervals (of length $ 2^{2-M}$) of the interval $ -2 \leq p < 2$.

As illustrated in Figure 14.1 for the case $ \rho =2$, $ M=5$, and $ N=2$, the sub-intervals of $ 1 \leq d < 2$ are numbered from left to right. For given $ N$, and for $ j=0,\ldots,2^N-1$, we shall denote the lower endpoint of sub-interval $ j$ as $ \delta_j$. Thus, $ j$ represents the fractional part of $ \delta_j$, i.e.,

$\displaystyle \delta_j = 1 + 2^{-N}j.$

Figure 14.1: $ \rho =2$, $ M=5$, $ N=2$
The sub-intervals of $ -2 < p < 2$ are numbered so that each $ i$ is the $ M$-bit two's complement representation of the lower endpoint $ \pi_i$ of sub-interval $ i$. Thus, for $ i=0,\ldots,2^M-1$,

$\displaystyle \pi_i = \left\{\begin{array}{ll}
2^{2-M}i & \mbox{if $ i < 2^{M-1}$}\\
2^{2-M}i-4 & \mbox{if $i \geq 2^{M-1}$}.\end{array} \right. $

These partitions produce a $ 2^M
\times 2^N$ matrix of rectangles in the $ dp$-plane, each of width $ 2^{-N}$ and height $ 2^{2-M}$. Let $ R_{ij}$ denote the rectangle with lower left vertex $ (\delta_j,\pi_i)$, and let $ S_{ij}$ denote the rectangle with the same lower left vertex and width and twice the height, i.e., for $ 0
\leq i < 2^M$ and $ 0 \leq j < 2^N$,

$\displaystyle R_{ij} = \left\{(d,p) \mid \delta_j \leq d < \delta_j+2^{-N}, \pi_i \leq p < \pi_i+2^{2-M}\right\}$

and

$\displaystyle S_{ij} = \left\{(d,p) \mid \delta_j \leq d < \delta_j+2^{-N}, \pi_i \leq p < \pi_i+2^{3-M}\right\}.$

The divisor $ d$ is approximated by some $ \delta_j$ and at each iteration, the partial remainder $ p$ is approximated by some $ \pi_i$. The index $ j$ is simply extracted from the leading fractional bits of $ d$, and hence the error is bounded by

$\displaystyle 0 \leq d-\delta_j < 2^{-N}.$

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

$\displaystyle 0 \leq p - \pi_i < 2^{3-M},$

i.e., $ (d,p)$ is confined to the uncertainty rectangle $ S_{ij}$.

We shall develop a procedure for generating a table of minimal dimensions that provides a quotient digit $ m = \phi(i,j)$ satisfying $ -d \leq 2^{\rho}p-md < d$ for all $ (d,p) \in S_{ij}$. Note that this constraint is equivalent to

$\displaystyle \frac{m-1}{2^{\rho}} \leq \frac{p}{d} < \frac{m+1}{2^{\rho}},$

and therefore the sign of each table entry $ \phi(i,j)$ is determined by that of $ \pi_i$ and need not be stored explicitly by an implementation. Thus, such a table consists of at most $ 2^{M+N}$ $ \rho$-bit entries.

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

  (admissible-div-table-p) Let $ \rho$, $ M$, and $ N$ be positive integers and let $ \phi$ be an integer-valued function of two integer variables. Then $ \phi$ is an admissible radix-$ 2^\rho$ $ M \times N$ SRT division table if for all $ i$ and $ j$, if $ 0
\leq i < 2^M$, $ 0 \leq j < 2^N$, and

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} < \pi_i < \delta_j + 2^{-N},$

then

max$\displaystyle (1-2^\rho,L_{ij}) \leq \phi(i,j) \leq {\it min}(2^\rho-1,U_{ij}),$

where

$\displaystyle L_{ij} = \left\{\begin{array}{ll}
\mathit{min}\left(2^\rho-1, \l...
...M})}{\delta_j + 2^{-N}}\rceil - 1\right) & \mbox{otherwise}\end{array} \right. $

and

$\displaystyle U_{ij} = \left\{\begin{array}{ll}
\mbox{max}\left(1-2^\rho, \lfl...
...}{\delta_j}\rfloor + 1\right) & \mbox{if $i \geq 2^{M-1}$}.\end{array} \right. $

  (admissible-div-table-criterion, admissible-div-table-criterion-converse)
Let $ \rho$, $ M$, and $ N$ be positive integers and let $ \phi$ be an integer-valued function of two integer variables. Then $ \phi$ is an admissible radix-$ 2^\rho$ $ M \times N$ SRT division table if and only if for all i, j, p, and d, if $ 0
\leq i < 2^M$, $ 0 \leq j < 2^N$, $ (d,p) \in S_{ij}$, and $ -d \leq p < d$, then $ m = \phi(i,j)$ satisfies $ -2^\rho < m
< 2^\rho$ and $ -d \leq 2^{\rho}p-md < d.$

PROOF: First note that if $ S_{ij}$ lies either entirely above the line $ p=d$ or entirely below the line $ p=-d$, then no constraint is imposed on $ \phi(i,j)$. In the first case, the lower right vertex of $ S_{ij}$, $ (\delta_j+2^{-N},\pi_i)$, must lie on or above $ p=d$, a condition expressed by the inequality

$\displaystyle \pi_i \geq \delta_j + 2^{-N}.$

The second case similarly depends on the location of the upper right vertex, $ (\delta_j+2^{-N},\pi_i+2^{3-M})$, and is characterized by

$\displaystyle \pi_i + 2^{3-M} \leq -(\delta_j + 2^{-N}).$

Thus, the constraint on $ \phi(i,j)$ is in force only if neither of these inequalities holds, i.e.,

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} < \pi_i < \delta_j + 2^{-N}.$

Suppose that this condition holds for indices $ i$ and $ j$ and let $ m = \phi(i,j)$. Then all $ (d,p) \in S_{ij}$ with $ -d \leq p < d$ must satisfy

$\displaystyle \frac{m-1}{2^{\rho}} \leq \frac{p}{d} < \frac{m+1}{2^{\rho}}.$

Since $ p < d$, the upper bound is satisfied trivially if $ m=2^{\rho}-1$. Therefore, a necessary and sufficient condition to ensure that this bound holds generally is that if $ m \neq 2^{\rho}-1$, then $ S_{ij}$ does not intersect the region between the lines $ p=d$ and $ p = \frac{m+1}{2^{\rho}}d$, or equivalently, that $ S_{ij}$ lies entirely below the latter of the two. The maximum value of the quotient $ \frac{p}{d}$ in $ S_{ij}$ occurs at either the upper left or the upper right vertex, depending on the sign of their common $ p$-coordinate, $ \pi_i + 2^{3-M}$. If $ i < 2^{M-1}$ or $ i = 2^M-1$, then $ \pi_i + 2^{3-M} > 0$ and the critical vertex is the upper left, $ (\delta_j,\pi_i+2^{3-M})$, so the requirement is

$\displaystyle \frac{\pi_i + 2^{3-M}}{\delta_j} \leq \frac{m+1}{2^{\rho}}.$

If $ 2^{M-1} \leq i < 2^M-1$, then $ \pi_i \leq 0$ and consideration of the upper right vertex yields

$\displaystyle \frac{\pi_i + 2^{3-M}}{\delta_j+2^{-N}} \leq \frac{m+1}{2^{\rho}}.$

In all cases, the required upper bound is satisfied if and only if $ m \geq L_{ij}$.

Similarly, since $ p \geq -d$, the lower bound

$\displaystyle \frac{p}{d} \geq
\frac{m-1}{2^{\rho}}$

is satisfied trivially if $ m=1-2^{\rho}$. To guarantee that this bound holds generally, it must be shown that if $ m
\neq 1-2^{\rho}$, then each point in $ S_{ij}$ lies on or above the line $ p =
\frac{m-1}{2^{\rho}}d$. The minimum value of $ \frac{p}{d}$ in $ S_{ij}$ occurs at either the lower left or the lower right vertex, depending on the sign of $ \pi_i$.

If $ \pi_i \geq 0$, then the critical vertex is the lower right, $ (\delta_j+2^{-N},\pi_i)$ and the requirement is

$\displaystyle \frac{\pi_i}{\delta_j+2^{-N}} \geq \frac{m-1}{2^{\rho}}.$

If $ \pi_i < 0$, then consideration of the lower left vertex yields

$\displaystyle \frac{\pi_i}{\delta_j} \geq \frac{m-1}{2^{\rho}}.$

In all cases, the required lower bound is satisfied if and only if $ m \leq U_{ij}$

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 $ \rho$, $ M$, and $ N$ be positive integers and let $ \phi$ be an admissible radix-$ 2^\rho$ $ M \times N$ SRT division table. Let $ x \in \mathbb{Q}$ and $ d \in \mathbb{Q}$ such that $ 1 \leq d < 2$ and $ \vert x\vert < d$. Let $ p_0 = x$, $ q_0 = 0$, and for $ k>0$,

$\displaystyle p_k = 2^\rho p_{k-1} - m_kd$

and

$\displaystyle q_k=q_{k-1}+2^{-k\rho} m_k,$

where $ m_k \in \mathbb{Z}$. Assume that for all $ k>0$, if $ \vert p_{k-1}\vert
< 2$, then $ m_k = \phi(i,j)$, where $ (d,p_{k-1}) \in S_{ij}$. Then for all $ k \geq 0$, $ \vert p_k\vert < 2$ and

$\displaystyle 2^{-k\rho} \leq \frac{x}{d} - q_k < 2^{-k\rho}.$

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 $ \rho$, $ M$, and $ N$ be positive integers. There exists an admissible radix-$ 2^{\rho}$ $ M \times N$ SRT division table if and only if for all $ i$ and $ j$ with $ 0
\leq i < 2^M$ and $ 0 \leq j < 2^N$, if

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} < \pi_i < \delta_j + 2^{-N},$

then $ L_{ij} \leq U_{ij}$. In this case, one such table is defined by

$\displaystyle \phi(i,j) =$   max$\displaystyle (1-2^\rho,L_{ij}).$

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 $ \rho =2$, the smallest admissible division table has dimensions $ M=5$ and $ N=2$, and that for $ \rho =3$, the smallest table has $ M=7$ and $ N=3$. These two tables, as generated by SRTTableEntry, are displayed in Figures 14.1 and 14.2, in which each value $ \phi(i,j)$ is indicated by a label associated with $ R_{ij}$.

For each of these tables, the following conditions may be verified by inspection of the graph for each entry $ \phi(i,j) = m$:

  1. If $ S_{ij}$ intersects the region $ -d \leq p < d$, then $ m$ is defined and $ -2^\rho < m
< 2^\rho$.
  2. If $ m$ is defined and $ m \neq 2^\rho-1$, then each point in $ S_{ij}$ lies below the line $ p = \frac{m+1}{2^\rho}d$.
  3. If $ m$ is defined and $ m \neq 1-2^\rho$, then each point in $ S_{ij}$ lies on or above the line $ p = \frac{m-1}{2^\rho}d$.
As argued in the proof of Theorem 14.1, it follows that $ \phi$ is an admissible radix $ 2^\rho$ division SRT table.

Note that in some cases, there is a choice between two acceptable values of $ m$. If $ S_{ij}$ lies within the region bounded by $ p =
\frac{m}{2^\rho}d$ and $ p = \frac{m+1}{2^\rho}d$, where $ -2^\rho < m
< 2^\rho$, then the required inequalities are satisfied by both $ m$ and $ m+1$. For example, in the radix-4 table of Figure 14.1, although we have assigned 2 as the value of $ \phi(00100,10)$, since $ S_{00100,10}$ lies between $ p = \frac{1}{2}d$ and $ p = \frac{1}{4}d$, we could have chosen 1 instead.

It is clear that a necessary and sufficient condition for the existence of an admissible $ M \times N$ radix-$ 2^\rho$ table is that each $ S_{ij}$ straddles at most one of the lines $ p =
\frac{m}{2^\rho}d$, $ m=1-2^{\rho},\ldots,2^\rho-1$. For example, if we attempt to construct a $ 6 \times 3$ radix-8 table, thereby doubling the height of the rectangular elements shown in Figure 14.2, we find that the uncertainty rectangle $ S_{001101,000}$ intersects both $ p = \frac{3}{4}d$ and $ p = \frac{7}{8}d$, requiring that $ m=\phi(001101,000)$ satisfy both $ m \leq 6$ and $ m \geq 7$. 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 $ R_{ij}$ and $ R_{(i-1)j}$ are separated by a segment of such a staircase, i.e., $ \phi(i,j) = m$ and $ \phi(i-1,j) =
m-1$. Since $ R_{ij}$ is contained in both $ S_{ij}$ and $ S_{(i-1)j}$, it must lie above the line $ p = \frac{m-1}{2^\rho}d$ and below $ p =
\frac{m}{2^\rho}d$. That is, a staircase that separates the regions on which $ \phi=m$ and $ \phi=m-1$ must lie entirely above $ p = \frac{m-1}{2^\rho}d$, and when shifted up through one sub-interval, it must still lie below $ p =
\frac{m}{2^\rho}d$.

Figure 14.2: $ \rho =3$, $ M=7$, $ N=3$

David Russinoff 2017-08-01