# 14.3  Square Root Seed Tables

In order to employ a -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 , the initial root digits to be used in the iterative computation of and , which must satisfy the constraints of the theorem. Our strategy is to read the -bit integer from a table using the -bit integer as an index. Lemma 14.3.1 (a) below provides a set of conditions on the table entry at index that ensures that 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 to be independent of for . Thus, we would like to ensure that the most significant bits of , consisting of the leading 1 and the -bit table index, coincide with the corresponding bits of . If we assume , as in the case of interest , , , then a sufficient condition is that the leading bits match, i.e., for all ,

Lemma 14.3.1 (b) provides a formula for deriving an adjusted value from the seed table entry that retains the properties of 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 and , which may be implemented by reading the value of from a parallel table and comparing it with during the pre-processing phase.

As a simplifying assumption, we ignore the case , which is of no practical interest:

(seed-req-a, seed-req-b, seed-req-c) Let and be positive integers with . Let , , and .

(a) Let satisfy

and

and let . Then and

(b) Let

and . Then and

(c) Let and for all , let , where and . Then for all , if , then

PROOF:

(a) The bounds on hold trivially. To derive the bounds on , note that substituting for in the second hypothesis yields

Since , this implies

and the claim follows.

(b) We may assume , for otherwise , , and the claims follow immediately. Since , , and hence , which implies . Moreover,

i.e., .

(c) First note that for , , where , and hence

Since

we have and

For the reverse inequality, we may assume . We may also assume ; otherwise, and since and are both integral multiples of ,

contradicting . It follows that is odd. Therefore, since ,

which implies

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 and be positive integers and let , where . Then

and

PROOF: Under the assumption that , its definition is equivalent to

The lower bound yields

and

which implies . From the upper bound, we have

and, since ,

which implies

and hence,

Along with the initial approximation , the corresponding partial remainder is required to initiate the iterative approximation of . While this may be computed directly as , an iterative computation is likely to be more efficient. For example, if and , a two-cycle iteration using existing hardware is preferable to a computation involving a -bit multiplication. In any case, to apply Theorem 14.2.4, it must be observed that is actually generated by the recurrence formula from the root digits extracted from the table entry:

(seed-digits) Let , , and be positive integers with and let . Let , and for ,

where Then .

PROOF: By induction, for ,

for if

then

In particular,

David Russinoff 2017-08-01