14.2  SRT Square Root Extraction and Digit Selection

Given a rational number $ x$ in the range $ \frac{1}{4} < x < 1$, our objective is to construct a sequence of partial roots, $ q_0=0,
q_1,\ldots$, that converge to $ \sqrt{x}$. For $ k>0$,

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

where $ 2^\rho$ is the underlying radix and the root digit $ m_k$ is again an integer in the interval $ -2^\rho < m_k < 2^\rho$, selected to maintain a bound on the partial remainders, which may be defined as

$\displaystyle p_k = 2^{k\rho}(x - q_k^2),$

or alternatively by the recurrence formula

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

The equivalence of these two expressions is established by the following:

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

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

and

$\displaystyle p_k = 2^\rho p_{k-1} - m_k(2q_{k-1} + 2^{-k\rho}m_k),$

for some $ m_k \in \mathbb{Z}$. Then for $ k \geq 0$, $ p_k = 2^{k\rho}(x - q_k^2)$.

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

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

Our objective is to select root digits that preserve the invariants $ \frac{1}{2} \leq q_k < 1$ and $ 2^{-k\rho} \leq \sqrt{x} - q_k < 2^{-k\rho}$. We derive two equivalent formulations of the latter inequality:

  (equiv-bounds-a-b, equiv-bounds-b-c) Let $ \rho \in \mathbb{N}$ and let $ x \in \mathbb{Q}$, $ x>0$. Let $ q_0 = 0$, $ p_0 = x$, and for $ k>0$,

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

and

$\displaystyle p_k = 2^\rho p_{k-1} - m_k(2q_{k-1} + 2^{-k\rho}m_k),$

for some $ m_k \in \mathbb{Z}$. Then for $ k>0$, if $ q_k \geq \frac{1}{2}$, then the following are equivalent:

(a) $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$;

(b) $ -2q_k \leq p_k - 2^{-k\rho}< 2q_k$;

(c) $ \frac{m_k-1}{2^\rho}\left(2q_{k-1} + (m_k-1)2^{-k\rho}\right) \leq p_{k-1} < \frac{m_k+1}{2^\rho}\left(2q_{k-1} + (m_k+1)2^{-k\rho}\right).$

PROOF: The equivalence of (a) and (b) follows from Lemma 14.2.1: since $ q_k \geq 2^{-k\rho}$,

$\displaystyle q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$ $\displaystyle \Leftrightarrow$ $\displaystyle (q_k - 2^{-k\rho})^2 \leq x < (q_k + 2^{-k\rho})^2$  
  $\displaystyle \Leftrightarrow$ $\displaystyle q_k^2 - 2^{1-k\rho}q_k + 2^{-2k\rho} \leq x < q_k^2 + 2^{1-k\rho}q_k + 2^{-2k\rho}$  
  $\displaystyle \Leftrightarrow$ $\displaystyle -2q_k + 2^{-k\rho} \leq 2^{k\rho}(x-q_k^2) < 2q_k + 2^{-k\rho}$  
  $\displaystyle \Leftrightarrow$ $\displaystyle -2q_k + 2^{-k\rho} \leq p_k < 2q_k + 2^{-k\rho}.$  

To show that (b) is equivalent to (c), note that since
$\displaystyle 2q_k + 2^{-k\rho}$ $\displaystyle =$ $\displaystyle 2(q_{k-1}+2^{-k\rho}m_k) + 2^{-k\rho}$  
  $\displaystyle =$ $\displaystyle 2q_{k-1} + (2m_k+1)2^{-k\rho}$  
  $\displaystyle =$ $\displaystyle (m_k+1)\left(2q_{k-1} + (m_k+1)2^{-k\rho}\right) - m_k(2q_{k-1} + 2^{-k\rho}m_k),$  

the upper bound $ p_k < 2q_k + 2^{-k\rho}$ is equivalent to
$\displaystyle {2^\rho p_{k-1} - m_k(2q_{k-1} + 2^{-k\rho}m_k)}$
  $\displaystyle <$ $\displaystyle (m_k+1)\left(2q_{k-1} + (m_k+1)2^{-k\rho}\right)$  
    $\displaystyle - m_k(2q_{k-1} + 2^{-k\rho}m_k)$  

or

$\displaystyle p_{k-1} < \frac{m_k+1}{2^\rho}\left(2q_{k-1} + (m_k+1)2^{-k\rho}\right).$

Similarly, the lower bound $ p_k \geq -2q_k + 2^{-k\rho}$ may be replaced by

$\displaystyle p_{k-1} \geq \frac{m_k-1}{2^\rho}\left(2q_{k-1} + (m_k-1)2^{-k\rho}\right). $

We shall once again pursue a table-based approach to the selection of $ m_k$. As suggested by the similarity between the partial remainder recurrence formulas for division and square root, and between the bounds $ -d \leq p_k < d$ and Condition (b) of Lemma 14.2.3, we shall find that in various cases of interest, the same table may be used for both, with the variable $ 2q_{k-1}$ used for the table index in the square root computation in place of the constant $ d$. This imposes a bound, however, on $ m_k^2 2^{-k\rho}$, the term that distinguishes the two formulas. Consequently, the table is used to derive $ m_k$ for $ k>K$, for some $ K$, after the first $ K$ iterations are performed by some other method.

The following lemma guarantees that if $ \frac{1}{2} \leq q_K < 1$, then the same bounds are satisfied by all subsequent $ q_k$ and that for all $ k \geq K$, $ \vert p_k\vert < 2$:

  (sqrt-partial-remainder-bounds, partial-root-bounds) Let $ \rho$ be a positive integer and let $ x \in \mathbb{Q}$, $ \frac{1}{4} < x < 1$. Let $ q_0 = 0$, $ p_0 = x$, and for $ k>0$,

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

and

$\displaystyle p_k = 2^\rho p_{k-1} - m_k(2q_{k-1} + 2^{-k\rho}m_k),$

for some $ m_k \in \mathbb{Z}$. Assume that $ \frac{1}{2} \leq q_{k-1} < 1$ for some $ k>1$.

(a) If $ q_{k-1} - 2^{(1-k)\rho} \leq \sqrt{x} < q_{k-1} + 2^{(1-k)\rho}$, then $ \vert p_{k-1}\vert
< 2$.

(b) If $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$ and $ \vert m_k\vert<2^\rho$, then $ \frac{1}{2} \leq q_k < 1$.

PROOF: Since $ q_{k-1} = \sum_{i=1}^{k-1} 2^{-i\rho}m_i$ is an integral multiple of $ 2^{(1-k)\rho}$, $ q_{k-1} < 1$ implies $ q_{k-1} \leq 1 - 2^{(1-k)\rho}$.

Suppose $ q_{k-1} - 2^{(1-k)\rho} \leq \sqrt{x} < q_{k-1} + 2^{(1-k)\rho}$. By Lemma 14.2.2,

$\displaystyle p_{k-1} \geq -2q_{k-1} + 2^{(1-k)\rho} > -2$

and

$\displaystyle p_{k-1} < 2q_{k-1} + 2^{(1-k)\rho} \leq 2(1 - 2^{(1-k)\rho}) + 2^{(1-k)\rho} < 2.$

Now suppose $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$ and $ \vert m_k\vert<2^\rho$. Then
$\displaystyle q_k$ $\displaystyle =$ $\displaystyle q_{k-1} + 2^{-k\rho}m_k \leq 1 - 2^{(1-k)\rho} + 2^{-k\rho}m_k$  
  $\displaystyle <$ $\displaystyle 1 - 2^{(1-k)\rho} + 2^{-k\rho}2^\rho$  
  $\displaystyle =$ $\displaystyle 1.$  

If $ q_{k-1} < \frac{1}{2}$, then $ q_k \leq \frac{1}{2} - 2^{-k\rho} < \sqrt{x} - 2^{-k\rho}$, contradicting our assumption. 

With $ 2q_{k-1}$ replaced by $ d$ in Lemma 14.2.2 (c), our objective may be formulated as follows:

Given positive integers $ \rho$ and $ K$ and rational numbers $ d$ and $ p$ such that $ 1 \leq d < 2$ and $ \vert p\vert < 2$, find $ m \in \mathbb{Z}$ such that $ -2^\rho < m
< 2^\rho$ and for all $ k>K$, if $ -d + 2^{(1-k)\rho} \leq p < d + 2^{(1-k)\rho}$, then

$\displaystyle \frac{m-1}{2^\rho}\left(d + (m-1)2^{-k\rho}\right) \leq p < \frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right).
$

We have the following formulation of the requirements of a square root digit selection table for a given iteration $ k$, analogous to Definition 14.1.1:

Definition 14.2.1   (admissible-for-iteration-p) Let $ \rho$, $ M$, $ N$, and $ k$ 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 square root table for iteration k if for all $ i$ and $ j$, if $ 0
\leq i < 2^M$, $ 0 \leq j < 2^N$, $ k>K$, and

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} + 2^{(1-k)\rho} < \pi_i < \delta_j + 2^{-N} + 2^{(1-k)\rho},$

then the following conditions hold for $ m = \phi(i,j)$:

(a) $ -2^\rho < m
< 2^\rho$.

(b) If $ m \neq 2^\rho-1$, then

$\displaystyle \pi_i + 2^{3-M} \leq \left\{\begin{array}{l}
\frac{m+1}{2^\rho}\...
...^{-k\rho}\right)\\
\mbox{   if $2^{M-1} \leq i < 2^M-1$}.\end{array} \right. $

(c) If $ m \neq 1-2^\rho$, then

$\displaystyle \pi_i \geq \left\{\begin{array}{ll}
\frac{m-1}{2^\rho}\left(\del...
...j + (m-1)2^{-k\rho}\right)& \!\!\mbox{if $i \geq 2^{M-1}$}.\end{array} \right. $

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

$\displaystyle \frac{m-1}{2^\rho}\left(d + (m-1)2^{-k\rho}\right) \leq p < \frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right).
$

PROOF: Consider the following four lines in the $ dp$-plane:

$ \ell_1$: $ p=d+2^{(1-k)\rho}$
$ \ell_2$: $ p=-d+2^{(1-k)\rho}$
$ \ell_3$: $ p=\frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right)$
$ \ell_4$: $ p=\frac{m-1}{2^\rho}\left(d + (m-1)2^{-k\rho}\right)$.
For given $ i$ and $ j$, the constraints of the lemma hold vacuously if $ S_{ij}$ lies either entirely above the line $ \ell_1$ or entirely below $ \ell_2$, as determined by the lower right vertex, $ (\delta_j+2^{-N},\pi_i)$, or the upper right vertex, $ (\delta_j+2^{-N},\pi_i+2^{3-M})$, respectively. Thus, the constraints are in force only if

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} + 2^{(1-k)\rho} < \pi_i < \delta_j + 2^{-N} + 2^{(1-k)\rho}.$

We may assume that this condition holds.

We must show that the upper bound

$\displaystyle p < \frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right)$

is satisfied by every $ (d,p) \in S_{ij}$ with $ -d + 2^{(1-k)\rho} \leq p < d + 2^{(1-k)\rho}$, i.e., below $ \ell_1$ and on or above $ \ell_2$, if and only if Condition (b) of Definition 14.2.1 holds. Since the bound is satisfied trivially if $ m=2^{\rho}-1$, we may assume that $ m < 2^{\rho}-1$. Of the two lines $ \ell_1$ and $ \ell_3$, $ \ell_1$ has the greater slope and $ p$-intercept and therefore lies above $ \ell_3$ for $ d > 0$. But for $ d \geq 1$ and $ k \geq 2$,
$\displaystyle \frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right) + d$ $\displaystyle \geq$ $\displaystyle \frac{m+1}{2^\rho}+1$  
  $\displaystyle >$ $\displaystyle \frac{1-2^\rho}{2^\rho}+1$  
  $\displaystyle =$ $\displaystyle 2^{-\rho}$  
  $\displaystyle \geq$ $\displaystyle 2^{(1-k)\rho},$  

and hence $ \ell_3$ lies above $ \ell_2$ in the region of interest. It follows that the required upper bound holds for all $ (d,p) \in S_{ij}$ with $ -d + 2^{(1-k)\rho} \leq p < d + 2^{(1-k)\rho}$ if and only if $ S_{ij}$ lies entirely below $ \ell_3$, or equivalently, both upper vertices lie on or below $ \ell_3$. Suppose first that $ i < 2^{M-1}$ or $ i = 2^M-1$, so that $ \pi_i + 2^{3-M} > 0$. If the slope $ m+1$ is negative, then since

$\displaystyle \delta_j + (m+1)2^{-k\rho} > 1 - 2^{\rho}2^{-k\rho} = 1 - 2^{(1-k)\rho} \geq 0,$

we have
$\displaystyle \pi_i + 2^{3-M}$ $\displaystyle >$ 0  
  $\displaystyle \geq$ $\displaystyle \frac{m+1}{2^\rho}\left(\delta_j + (m+1)2^{-k\rho}\right)$  
  $\displaystyle >$ $\displaystyle \frac{m+1}{2^\rho}\left(\delta_j + 2^{-N} + (m+1)2^{-k\rho}\right)$  

and both vertices lie above the line. If the slope is non-negative, then the critical vertex is the upper left. In either case, a necessary and sufficient condition is that

$\displaystyle \pi_i + 2^{3-M} \leq \frac{m+1}{2^\rho}\left(\delta_j + (m+1)2^{-k\rho}\right).$

On the other hand, if $ 2^{M-1} \leq i < 2^M-1$, then $ \pi_i + 2^{3-M} \leq 0$. If the slope $ m+1$ is positive, then every point $ (d,p) \in S_{ij}$ lies below $ \ell_3$, since

$\displaystyle p$ $\displaystyle <$ $\displaystyle \pi_i + 2^{3-M}$  
  $\displaystyle \leq$ 0  
  $\displaystyle \leq$ $\displaystyle \frac{m+1}{2^\rho}\left(\delta_j + (m+1)2^{-k\rho}\right)$  
  $\displaystyle \leq$ $\displaystyle \frac{m+1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right),$  

and if $ m+1 \leq 0$, then the critical vertex is the upper right. Thus, a necessary and sufficient condition is

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

The analysis of the lower bound,

$\displaystyle p \geq \frac{m-1}{2^\rho}\left(d + (m-1)2^{-k\rho}\right),$

is similar. Since the bound is satisfied trivially if $ m=1-2^{\rho}$, we may assume $ m > 1-2^{\rho}$. For $ d \geq 1$, $ \ell_4$ lies below $ \ell_1$, since
$\displaystyle d+2^{(1-k)\rho} - \frac{m-1}{2^\rho}(d + (m-1)2^{-k\rho})$ $\displaystyle =$ $\displaystyle \left(1-\frac{m-1}{2^\rho}\right)d + 2^{(1-k)\rho}\left(1-\left(\frac{m-1}{2^\rho}\right)^2\right)$  
  $\displaystyle \geq$ $\displaystyle 1-\frac{m-1}{2^\rho}$  
  $\displaystyle >$ $\displaystyle 0,$  

and $ \ell_4$ lies above $ \ell_2$, since
$\displaystyle \frac{m-1}{2^\rho}(d + (m-1)2^{-k\rho}) - (-d+2^{(1-k)\rho})$ $\displaystyle \geq$ $\displaystyle \left(1+\frac{m-1}{2^\rho}\right)d - 2^{(1-k)\rho}$  
  $\displaystyle \geq$ $\displaystyle 1+\frac{2-2^\rho}{2^\rho} - 2^{-\rho}$  
  $\displaystyle =$ $\displaystyle 2^{-\rho}$  
  $\displaystyle >$ $\displaystyle 0.$  

Consequently, the bound is satisfied for all $ (d,p) \in S_{ij}$ with $ -d \leq p-2^{(1-k)\rho} < d$ if and only if each point in $ S_{ij}$ lies on or above $ \ell_4$, as determined by its lower vertices. If $ i < 2^{M-1}$, i.e., $ \pi_i \geq 0$, then since

$\displaystyle \delta_j + (m-1)2^{-k\rho} \geq 1 - 2^{\rho}2^{-k\rho} = 1 - 2^{(1-k)\rho} \geq 0,$

if $ m-1 \leq 0$, then for all $ (d,p) \in S_{ij}$,

$\displaystyle p \geq \pi_i \geq 0 \geq \frac{m-1}{2^\rho}\left(\delta_j + (m+1)2^{-k\rho}\right)
\geq \frac{m-1}{2^\rho}\left(d + (m+1)2^{-k\rho}\right),
$

and if $ m-1 > 0$, then the critical vertex is the lower right. Therefore, the requirement is

$\displaystyle \pi_i \geq \frac{m-1}{2^\rho}\left(\delta_j+2^{-N} + (m-1)2^{-k\rho}\right).$

If $ \pi_i < 0$, then a similar argument yields the condition

$\displaystyle \pi_i \geq \frac{m-1}{2^\rho}\left(\delta_j + (m-1)2^{-k\rho}\right). $

The preceding results of this section may be summarized:

  (srt-sqrt-theorem-a, srt-sqrt-theorem-b) Let $ \rho$, $ M$, $ N$, and $ K$ be positive integers and let $ \phi$ be an admissible radix-$ 2^\rho$ $ M \times N$ SRT square root table for every iteration $ k>K$. Let $ x \in \mathbb{Q}$, $ \frac{1}{4} < x < 1$. Let $ q_0 = 0$, $ p_0 = x$, and for $ k=1,\ldots,n$,

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

and

$\displaystyle p_k = 2^\rho p_{k-1} - m_k(2q_{k-1} + 2^{-k\rho}m_k),$

where $ m_k \in \mathbb{Z}$. Assume that $ \frac{1}{2} \leq q_K < 1$, $ q_K - 2^{-K\rho} \leq \sqrt{x} < q_K + 2^{-K\rho}$, and for $ k>K$, if $ \frac{1}{2} \leq q_{k-1} < 1$ and $ \vert p_{k-1}\vert
< 2$, then $ m_k = \phi(i,j)$, where $ (2q_{k-1},p_{k-1}) \in S_{ij}$. Then for all $ k \geq K$, $ \vert p_k\vert < 2$ and $ -2^{-k\rho} \leq \sqrt{x}-q_k < 2^{-k\rho}$.

PROOF: We shall prove by induction that for $ k \geq K$, $ \frac{1}{2} \leq q_k < 1$ and $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$. Suppose that these conditions hold for $ k-1$. Then $ -2q_{k-1} + 2^{(1-k)\rho} \leq p_{k-1} < 2q_{k-1} + 2^{(1-k)\rho}$ by Lemma 14.2.2, $ \vert p_{k-1}\vert
< 2$ by Lemma 14.2.3, and consequently, for some $ i$ and $ j$, $ m_k = \phi(i,j)$ and $ (2q_{k-1},p_{k-1}) \in S_{ij}$. Therefore, by hypothesis, $ \vert m_k\vert<2^\rho$ and

$\displaystyle \frac{m_k-1}{2^\rho}\left(2q_{k-1} + (m_k-1)2^{-k\rho}\right)
\leq p_{k-1} < \frac{m_k+1}{2^\rho}\left(2q_{k-1} + (m_k+1)2^{-k\rho}\right).
$

By Lemma 14.2.2, $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$, and by Lemma 14.2.3, $ \frac{1}{2} \leq q_k < 1$

We shall develop a procedure for generating a table for a given radix that meets the requirements of both division and square root, of minimal dimensions and with minimal $ K$. In Section 14.3, we turn to the problem of generating the initial partial quotient and remainder, $ q_K$ and $ p_K$.

First we note that any table that meets the requirements for square root extraction may be used for division as well:

  (sqrt-table-is-div-table) If $ \phi$ is an admissible radix-$ 2^\rho$ $ M \times N$ square root table for all iterations $ k>K$, then $ \phi$ is an admissible radix-$ 2^\rho$ $ M \times N$ division table.

PROOF: Suppose that

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

where $ 0
\leq i < 2^M$, $ 0 \leq j < 2^N$. Then for some $ K'$,

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} + 2^{(1-k)\rho} < \pi_i < \delta_j + 2^{-N} + 2^{(1-k)\rho}$

for all $ k > K'$. Let $ m = \phi(i,j)$. For all $ k >$max$ (K,K')$, Conditions (a), (b), and (c) of Definition 14.2.1 hold. It follows that if $ m \neq 2^\rho-1$, then

$\displaystyle \pi_i + 2^{3-M} \leq \left\{\begin{array}{ll}
\frac{m+1}{2^\rho}...
...j+2^{-N}\right) & \!\!\!\mbox{if $2^{M-1} \leq i < 2^M-1$},\end{array} \right. $

which implies $ m \geq L_{ij}$. Similarly, if $ m \neq 1-2^\rho$, then

$\displaystyle \pi_i \geq \left\{\begin{array}{ll}
\frac{m-1}{2^\rho}\left(\del...
...
\frac{m-1}{2^\rho}\delta_j & \mbox{if $i \geq 2^{M-1}$},\end{array} \right. $

which implies $ m \leq U_{ij}$

While Definition 14.2.1 provides a procedure to determine whether a square root table is admissible for a given iteration $ k$, we would like a procedure for determining admissibility for all sufficiently large $ k$. This is provided by the following:

Definition 14.2.2   (admissible-srt-table-p) Let $ \rho$, $ M$, $ N$, and $ K$ be positive integers and let $ \phi$ be an integer-valued function of two integer variables. Then $ \phi$ is a $ K$-admissible radix-$ 2^\rho$ $ M \times N$ SRT 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} + 2^{-K\rho},$

then the following conditions hold for $ m = \phi(i,j)$:

(a) $ -2^\rho < m
< 2^\rho$.

(b) $ m \geq L_{ij}$.

(c) If $ m \neq 1-2^\rho$, then

$\displaystyle \pi_i \geq \left\{\begin{array}{l}
\frac{m-1}{2^\rho}\left(\delt...
...-1)2^{-(K+1)\rho}\right)\\
\mbox{   if $i \geq 2^{M-1}$}.\end{array} \right. $

A $ K$-admissible table is essentially one that is admissible for every iteration $ k>K$:

  (admissibility-equivalence-a, admissibility-equivalence-b) Let $ \rho$, $ M$, $ N$, and $ K$ be positive integers and let $ \phi$ be an integer-valued function of two integer variables.

(a) If $ \phi$ is a $ K$-admissible radix-$ 2^\rho$ $ M \times N$ SRT table, then for all $ k>K$, $ \phi$ is an admissible SRT square root table for iteration k.

(b) Let $ \phi$ be an admissible radix-$ 2^\rho$ $ M \times N$ SRT square root table for iteration k for all $ k>K$ and let

$\displaystyle \phi'(i,j) = \left\{\begin{array}{ll}
1 - 2^\rho & \mbox{if $-\d...
... - 2^{3-M} + 2^{-K\rho}$}\\
\phi(i,j) & \mbox{otherwise}.\end{array} \right. $

Then $ \phi'$ is a $ K$-admissible radix-$ 2^\rho$ $ M \times N$ SRT table.

PROOF: Suppose that $ \phi$ satisfies Definition 14.2.2. Let $ k>K$ and

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} + 2^{(1-k)\rho} < \pi_i < \delta_j + 2^{-N} + 2^{(1-k)\rho}.$

Then

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

Of the conditions imposed by Definition 14.2.1, (a) and (c) follow from the corresponding conditions of Definition 14.2.2. To establish (b), note that if $ m \neq 2^\rho-1$, then we have $ m \geq L_{ij}$, where

$\displaystyle L_{ij} = \left\{\begin{array}{ll}
\lceil\frac{2^{\rho}(\pi_i + 2...
..._j + 2^{N}}\rceil - 1 & \mbox{if $2^{M-1} \leq i < 2^M-1$},\end{array} \right. $

which implies

$\displaystyle \pi_i + 2^{3-M} \leq \left\{\begin{array}{ll}
\frac{m+1}{2^\rho}...
...}\right) & \!\!\!\mbox{if $2^{M-1} \leq i < 2^M\!\!-\!\!1$}.\end{array} \right.$

Now suppose $ \phi$ is an admissible SRT square root table for every iteration $ k>K$ and let $ \phi'$ be defined as above. Let

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

for some $ i$ and $ j$ and let $ m = \phi'(i,j)$. If $ \pi_i \leq -\delta_j - 2^{-N} - 2^{3-M} + 2^{-K\rho}$, then
$\displaystyle L_{ij}$ $\displaystyle <$ $\displaystyle \frac{2^{\rho}(\pi_i + 2^{3-M})}{\delta_j + 2^{-N}}$  
  $\displaystyle \leq$ $\displaystyle \frac{2^{\rho}(-\delta_j - 2^{-N} + 2^{-K\rho})}{\delta_j + 2^{-N}}$  
  $\displaystyle =$ $\displaystyle \frac{2^{(1-K)\rho}}{\delta_j + 2^{-N}} - 2^\rho$  
  $\displaystyle <$ $\displaystyle 1 - 2^\rho$  
  $\displaystyle =$ $\displaystyle m$  

and Definition 14.2.2 is satisfied. In the remaining case,

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

and the three conditions of Definition 14.2.1 must hold for $ k=K+1$. Since (a) and (c) coincide with the corresponding conditions of Definition 14.2.2, we need only show that $ m \geq L_{ij}$. Since this is clearly true if $ m = 2^\rho-1$, we may assume that $ m \leq 2^\rho-2$. Suppose $ \pi_i \geq \delta_j$. Then $ i < 2^{M-1}$ and it follows from (b) that
$\displaystyle \pi_i + 2^{3-M}$ $\displaystyle \leq$ $\displaystyle \frac{m+1}{2^\rho}\delta_j + \frac{(m+1)^2}{2^\rho}2^{-(K+1)\rho}$  
  $\displaystyle <$ $\displaystyle (1 - 2^{-\rho})\delta_j + 2^{-\rho}2^{(1-K)\rho}$  
  $\displaystyle =$ $\displaystyle \delta_j + 2^{-\rho}(2^{(1-K)\rho} - \delta_j)$  
  $\displaystyle \leq$ $\displaystyle \delta_j + 2^{-\rho}(1 - 1)$  
  $\displaystyle =$ $\displaystyle \delta_j,$  

a contradiction. Therefore, we may also assume $ \pi_i < \delta_j$. But then for all $ k>K$,

$\displaystyle -\delta_j - 2^{-N} - 2^{3-M} + 2^{(1-k)\rho} < \pi_i < \delta_j + 2^{-N} + 2^{(1-k)\rho},$

and hence

$\displaystyle \pi_i + 2^{3-M} \leq \left\{\begin{array}{l}
\frac{m+1}{2^\rho}\...
... (m+1)2^{-k\rho}\right) \mbox{if $2^{M-1} \leq i < 2^M-1$}.\end{array} \right. $

Consequently,

$\displaystyle \pi_i + 2^{3-M} \leq \left\{\begin{array}{ll}
\frac{m+1}{2^\rho}...
...\right) & \!\!\!\mbox{if $2^{M-1} \leq i < 2^M\!\!-\!\!1$},\end{array} \right. $

which implies $ m \geq L_{ij}$

Thus, for given $ \rho$, $ M$, $ N$, and $ K$, Definition 14.2.2 may be used to determine whether there exists a table that is admissible all square root iterations $ k>K$, and consequently for division as well. If such a table does exist, then it may be generated by the same procedure that was developed for division tables:

Lemma 14.2.7   (srt-table-existence-a, srt-table-existence-b) Let $ \rho$, $ M$, $ N$, and $ K$ be positive integers. There exists a $ K$-admissible radix-$ 2^{\rho}$ $ M \times N$ SRT 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} + 2^{-K\rho}$

and

$\displaystyle L_{ij} > 1 - 2^\rho$

(where $ L_{ij}$ is defined as in Definition 14.1.1), then

$\displaystyle \pi_i \geq \left\{\begin{array}{ll}
\frac{L_{ij}-1}{2^\rho}\left...
...!1)2^{-(K+1)\rho}\right)& \!\!\!\mbox{if $i \geq 2^{M-1}$}.\end{array} \right. $

In this case, one such table is defined by

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

PROOF: Let $ 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} + 2^{-K\rho}.$

Suppose that if $ L_{ij} > 1 - 2^\rho$, then the conclusion of the lemma holds. Then clearly, the requirements of Definition 14.2.2 are satisfied by $ m =$   max$ (1-2^\rho,L_{ij})$.

Conversely, suppose that some $ m$ satisfies Definition 14.2.2 and that $ L_{ij} > 1 - 2^\rho$. Then $ L_{ij} \leq m < 2^\rho$ and $ \pi_i \geq f(m)$, where

$\displaystyle f(m) = \left\{\begin{array}{ll}
\!\!\frac{m-1}{2^\rho}\left(\del...
...!1)2^{-(K+1)\rho}\right)& \!\!\!\mbox{if $i \geq 2^{M-1}$,}\end{array} \right. $

and we need only show that $ \pi_i \geq f(L_{ij})$. But note that $ f$ is an increasing function of $ m$ for $ m > -2^\rho$, since
$\displaystyle 2^\rho(f(m+1) - f(m))$ $\displaystyle \geq$ $\displaystyle \delta_j + (2m-1)2^{-(K+1)\rho}$  
  $\displaystyle \geq$ $\displaystyle 1 + (1 - 2^{\rho+1})2^{-(K+1)\rho}$  
  $\displaystyle >$ $\displaystyle 1 - 2^{1-K\rho}$  
  $\displaystyle \geq$ $\displaystyle 0.$  

Therefore, $ \pi_i \geq f(m) \geq f(L_{ij})$

If $ \phi(i,j) = m$ for a $ K$-admissible table $ \phi$, then as noted in the proof of Lemma 14.2.4, $ S_{ij}$ must lie above the line $ p=\frac{m-1}{2^\rho}\left(d + (m-1)2^{-K\rho}\right)$. Consequently, in addition to the criterion given in Section 14.1, the staircase that separates the regions $ \phi=m$ and $ \phi=m-1$ must lie above that line.

Consider the $ 5 \times 2$ division table of Figure 14.1. Since the lower left vertex of $ R_{11010,00}$ lies on $ p=-\frac{1}{2}d$, this point does not lie above $ p=-\frac{1}{2}\left(d - 4^{1-K}\right)$; therefore, this is not a $ K$-admissible square root table for any positive $ K$. Moreover, the same is true of every $ 5 \times N$ radix-4 table for every $ N$. There does, however, exist a $ 6 \times 2$ 2-admissible table. This is confirmed by execution of the function ExistsDivSqrtTable, displayed in the appendix, which implements the procedure specified by Lemma 14.2.7. Such a table may be generated by executing SRTTableEntry.

Now consider the $ 7 \times 3$ radix-8 table of Figure 14.2. Since the lower right vertex of $ R_{0011110,001}$ lies on the line $ p = \frac{3}{4}d$, this table cannot be used for the square root. As confirmed by ExistsDivSqrtTable, however, there exist both $ 8
\times 3$ and $ 7 \times 4$ 2-admissible radix-8 tables.

David Russinoff 2017-08-01