14.3  Square Root Seed Tables

In order to employ a $ K$-admissible SRT table to compute square roots as described in Theorem 14.2, we shall require an efficient method of deriving, for a given radicand $ x$, the initial root digits $ m_1,\ldots,m_K$ to be used in the iterative computation of $ p_K$ and $ q_K$, which must satisfy the constraints of the theorem. Our strategy is to read the $ (K\rho)$-bit integer $ S = 2^{K\rho}q_K$ from a table using the $ (K\rho)$-bit integer $ \ell = \lfloor 2^{K\rho}x
\rfloor$ as an index. Lemma 14.3.1 (a) below provides a set of conditions on the table entry $ S$ at index $ \ell$ that ensures that $ q_K$ meets its requirements.

As previously noted, we would like to arrange for the column of the digit selection table that is determined by the partial root $ q_k$ to be independent of $ k$ for $ k \geq K$. Thus, we would like to ensure that the most significant $ N+1$ bits of $ q_k$, consisting of the leading 1 and the $ N$-bit table index, coincide with the corresponding bits of $ q_K$. If we assume $ K\rho > N+1$, as in the case of interest $ K=2$, $ \rho =3$, $ N=4$, then a sufficient condition is that the leading $ K\rho-1$ bits match, i.e., for all $ k>K$,

$\displaystyle \lfloor 2^{K\rho-1}q_k \rfloor = \lfloor 2^{K\rho-1}q_K \rfloor.$

Lemma 14.3.1 (b) provides a formula for deriving an adjusted value $ S'$ from the seed table entry $ S$ that retains the properties of $ q_K$ required by Theorem 14.2 and, as established by (c), satisfies this additional condition as well. Note that this derivation requires a full-width comparison of $ \sqrt{x}$ and $ q_K$, which may be implemented by reading the value of $ S^2$ from a parallel table and comparing it with $ x$ during the pre-processing phase.

As a simplifying assumption, we ignore the case $ K = \rho = 1$, which is of no practical interest:

  (seed-req-a, seed-req-b, seed-req-c) Let $ \rho$ and $ K$ be positive integers with $ K\rho > 1$. Let $ x \in \mathbb{Q}$, $ \frac{1}{4} < x < 1$, and $ \ell = \lfloor 2^{K\rho}x
\rfloor$.

(a) Let $ S \in \mathbb{Z}$ satisfy

$\displaystyle 2^{K\rho-1} \leq S < 2^{K\rho}$

and

$\displaystyle 2^{-K\rho}(S-1)^2 \leq \ell < \ell+1 \leq 2^{-K\rho}(S+1)^2,$

and let $ Q = 2^{-K\rho}S$. Then $ \frac{1}{2} \leq Q < 1$ and

$\displaystyle Q - 2^{-K\rho} \leq \sqrt{x} < Q + 2^{-K\rho}.$

(b) Let

$\displaystyle S' = \left\{\begin{array}{ll}
S & \mbox{if $S$ is odd or $\sqrt{x} > Q$}\\
S-1 & \mbox{if $S$ is even and $\sqrt{x} < Q$}\end{array} \right. $

and $ Q' = 2^{-K\rho}S'$. Then $ \frac{1}{2} \leq Q' < 1$ and

$\displaystyle Q' - 2^{-K\rho} \leq \sqrt{x} < Q' + 2^{-K\rho}.$

(c) Let $ q_K = Q'$ and for all $ k>K$, let $ q_k = q_{k-1} +
2^{-k\rho}m_k$, where $ m_k \in \mathbb{Z}$ and $ \vert m_k\vert < 2^{\rho}$. Then for all $ k \geq K$, if $ q_k - 2^{-k\rho} \leq \sqrt{x} < q_k + 2^{-k\rho}$, then

$\displaystyle \lfloor 2^{K\rho-1}q_k \rfloor = \lfloor 2^{K\rho-1}Q' \rfloor.$

PROOF:

(a) The bounds on $ Q$ hold trivially. To derive the bounds on $ \sqrt{x} - Q$, note that substituting $ 2^{K\rho}Q$ for $ S$ in the second hypothesis yields

$\displaystyle (Q - 2^{-K\rho})^2 \leq 2^{-K\rho}\ell < 2^{-K\rho}(\ell + 1) \leq (Q + 2^{-K\rho})^2.$

Since $ 2^{-K\rho}\ell \leq x < 2^{-K\rho}(\ell + 1)$, this implies

$\displaystyle (Q - 2^{-K\rho})^2 \leq x < (Q + 2^{-K\rho})^2,$

and the claim follows.

(b) We may assume $ S' = S-1$, for otherwise $ S' = S$, $ Q' = Q$, and the claims follow immediately. Since $ Q > \sqrt{x} > \frac{1}{2}$, $ S = 2^{K\rho}Q > 2^{K\rho-1}$, and hence $ 2^{K\rho-1} \leq S' <
2^{K\rho}$, which implies $ \frac{1}{2} \leq Q' < 1$. Moreover,

$\displaystyle \sqrt{x} - 2^{-K\rho} < Q - 2^{-K\rho} = Q' < Q \leq \sqrt{x} + 2^{-K\rho},$

i.e., $ Q' - 2^{-K\rho} \leq \sqrt{x} < Q' + 2^{-K\rho}$.

(c) First note that for $ k \geq K$, $ q_k = Q' + \sum_{i=K+1}^k 2^{-i\rho}m_i$, where $ \vert m_i\vert \leq 2^\rho-1$, and hence

$\displaystyle \vert q_k - Q'\vert$ $\displaystyle =$ $\displaystyle \left\vert \sum_{i=K+1}^k 2^{-i\rho}m_i \right\vert$  
  $\displaystyle <$ $\displaystyle 2^{-(K+1)\rho}(2^\rho-1)\sum_{i=0}^\infty 2^{-i\rho}$  
  $\displaystyle =$ $\displaystyle 2^{-K\rho}.$  

Since

$\displaystyle \lfloor 2^{K\rho}q_k\rfloor \leq 2^{K\rho}q_k < 2^{K\rho}(Q'+2^{-K\rho}) = S' + 1,$

we have $ \lfloor 2^{K\rho}q_k\rfloor \leq S' = 2^{K\rho}Q'$ and

$\displaystyle \lfloor 2^{K\rho-1}q_k \rfloor = \left\lfloor \frac{\lfloor 2^{K\...
...eft\lfloor \frac{2^{K\rho}Q'}{2} \right\rfloor = \lfloor 2^{K\rho-1}Q' \rfloor.$

For the reverse inequality, we may assume $ q_k < Q'$. We may also assume $ \sqrt{x} < Q$; otherwise, $ Q' = Q$ and since $ q_k$ and $ Q'$ are both integral multiples of $ 2^{-k\rho}$,

$\displaystyle q_k \leq Q' - 2^{-k\rho} = Q - 2^{-k\rho} < \sqrt{x} - 2^{-k\rho},$

contradicting $ \sqrt{x} < q_k + 2^{-k\rho}$. It follows that $ S'$ is odd. Therefore, since $ q_k > Q' - 2^{-K\rho}$,

$\displaystyle 2^{K\rho-1}q_k > 2^{K\rho-1}Q' - \frac{1}{2} = \frac{S'}{2} - \fr...
...}{2} = \left\lfloor \frac{S'}{2} \right\rfloor
= \lfloor 2^{K\rho-1}Q' \rfloor,$

which implies $ \lfloor 2^{K\rho-1}q_k \rfloor \geq \lfloor 2^{K\rho-1}Q' \rfloor.$ 

The next lemma establishes the existence of a compliant seed table and gives a formula for computing its entries, implemented by the function Seed, specified in the appendix:

Lemma 14.3.2   (seed-compliance) Let $ \rho$ and $ K$ be positive integers and let $ \psi(\ell) = \left\lceil \sqrt{2^{K\rho} (\ell+1)} \right\rceil - 1$, where $ 2^{K\rho-2} \leq \ell <2^{K\rho}$. Then

$\displaystyle 2^{K\rho-1} \leq \psi(\ell) < 2^{K\rho}$

and

$\displaystyle 2^{-K\rho}(\psi(\ell)-1)^2 \leq \ell < \ell+1 \leq 2^{-K\rho}(\psi(\ell)+1)^2.$

PROOF: Under the assumption that $ \psi(\ell) \in \mathbb{Z}$, its definition is equivalent to

$\displaystyle \sqrt{2^{K\rho}(\ell+1)} - 1 \leq \psi(\ell) < \sqrt{2^{K\rho}(\ell+1)}.$

The lower bound yields

$\displaystyle 2^{K\rho}(\ell+1) \leq (\psi(\ell)+1)^2$

and
$\displaystyle \psi(\ell)$ $\displaystyle \geq$ $\displaystyle \sqrt{2^{K\rho}(\ell+1)} - 1$  
  $\displaystyle \geq$ $\displaystyle \sqrt{2^{K\rho}(2^{K\rho-2}+1)} - 1$  
  $\displaystyle >$ $\displaystyle \sqrt{2^{K\rho}2^{K\rho-2}}-1$  
  $\displaystyle =$ $\displaystyle 2^{K\rho-1}-1,$  

which implies $ \psi(\ell) \geq 2^{K\rho-1}$. From the upper bound, we have

$\displaystyle \psi(\ell) < \sqrt{2^{K\rho}(\ell+1)} \leq \sqrt{2^{K\rho}2^{K\rho}} = 2^{K\rho}$

and, since $ 4\ell \geq 2^{K\rho}$,
$\displaystyle \sqrt{2^{K\rho}(\ell+1)} - \sqrt{2^{K\rho}\ell}$ $\displaystyle \leq$ $\displaystyle \sqrt{4\ell(\ell+1)} - \sqrt{4\ell^2}$  
  $\displaystyle <$ $\displaystyle \sqrt{4\ell(\ell+1)+1} - \sqrt{4\ell^2}$  
  $\displaystyle =$ $\displaystyle 2\ell+1-2\ell$  
  $\displaystyle =$ $\displaystyle 1,$  

which implies

$\displaystyle \psi(\ell) < \sqrt{2^{K\rho}(\ell+1)} < \sqrt{2^{K\rho}\ell} + 1$

and hence,

$\displaystyle (\psi(\ell)-1)^2 < 2^{K\rho}\ell. $

Along with the initial approximation $ q_K$, the corresponding partial remainder $ p_K$ is required to initiate the iterative approximation of $ \sqrt{x}$. While this may be computed directly as $ p_K = 2^{K\rho}(x
- q_K^2)$, an iterative computation is likely to be more efficient. For example, if $ \rho =3$ and $ K=2$, a two-cycle iteration using existing hardware is preferable to a computation involving a $ (6
\times 6)$-bit multiplication. In any case, to apply Theorem 14.2.4, it must be observed that $ q_K$ is actually generated by the recurrence formula from the root digits extracted from the table entry:

  (seed-digits) Let $ \rho$, $ K$, and $ S$ be positive integers with $ S < 2^{K\rho}$ and let $ Q = 2^{-K\rho}S$. Let $ q_0 = 0$, and for $ k = 1,\ldots,K$,

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

where $ m_k = S[(K-k+1)\rho-1:(K-k)\rho].$ Then $ q_K = Q$.

PROOF: By induction, for $ 1 \leq k \leq K$,

$\displaystyle q_k = 2^{-k\rho}S[K\rho-1:(K-k)\rho],$

for if

$\displaystyle q_{k-1} = 2^{(1-k)\rho}S[K\rho-1:(K-k+1)\rho],$

then


$\displaystyle q_k$ $\displaystyle =$ $\displaystyle 2^{(1-k)\rho}S[K\rho-1:(K-k+1)\rho] + 2^{-k\rho}m_k$  
  $\displaystyle =$ $\displaystyle 2^{-k\rho}2^\rho S[K\rho-1:(K-k+1)\rho] + 2^{-k\rho}S[(K-k+1)\rho-1:(K-k)\rho]$  
  $\displaystyle =$ $\displaystyle 2^{-k\rho}S[K\rho-1:(K-k)\rho].$  

In particular,

$\displaystyle q_K = 2^{-K\rho}S[K\rho-1:0] = 2^{-K\rho}S = Q. $

David Russinoff 2017-08-01