# 14.2  SRT Square Root Extraction and Digit Selection

Given a rational number in the range , our objective is to construct a sequence of partial roots, , that converge to . For ,

where is the underlying radix and the root digit is again an integer in the interval , selected to maintain a bound on the partial remainders, which may be defined as

or alternatively by the recurrence formula

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

(sqrt-remainder-formula) Let and let . Let , , and for ,

and

for some . Then for , .

PROOF: The claim is trivial for , and for ,

Our objective is to select root digits that preserve the invariants and . We derive two equivalent formulations of the latter inequality:

(equiv-bounds-a-b, equiv-bounds-b-c) Let and let , . Let , , and for ,

and

for some . Then for , if , then the following are equivalent:

(a) ;

(b) ;

(c)

PROOF: The equivalence of (a) and (b) follows from Lemma 14.2.1: since ,

To show that (b) is equivalent to (c), note that since

the upper bound is equivalent to

or

Similarly, the lower bound may be replaced by

We shall once again pursue a table-based approach to the selection of . As suggested by the similarity between the partial remainder recurrence formulas for division and square root, and between the bounds 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 used for the table index in the square root computation in place of the constant . This imposes a bound, however, on , the term that distinguishes the two formulas. Consequently, the table is used to derive for , for some , after the first iterations are performed by some other method.

The following lemma guarantees that if , then the same bounds are satisfied by all subsequent and that for all , :

(sqrt-partial-remainder-bounds, partial-root-bounds) Let be a positive integer and let , . Let , , and for ,

and

for some . Assume that for some .

(a) If , then .

(b) If and , then .

PROOF: Since is an integral multiple of , implies .

Suppose . By Lemma 14.2.2,

and

Now suppose and . Then

If , then , contradicting our assumption.

With replaced by in Lemma 14.2.2 (c), our objective may be formulated as follows:

Given positive integers and and rational numbers and such that and , find such that and for all , if , then

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

Definition 14.2.1   (admissible-for-iteration-p) Let , , , and be positive integers and let be an integer-valued function of two integer variables. Then is an admissible radix- SRT square root table for iteration k if for all and , if , , , and

then the following conditions hold for :

(a) .

(b) If , then

(c) If , then

(admissible-sqrt-table-criterion) Let , , , and be positive integers, , and let be an integer-valued function of two integer variables. Then is an admissible radix- SRT square root table for iteration k if and only if or all , , , and , if , , , , and , then satisfies and

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

:
:
:
: .
For given and , the constraints of the lemma hold vacuously if lies either entirely above the line or entirely below , as determined by the lower right vertex, , or the upper right vertex, , respectively. Thus, the constraints are in force only if

We may assume that this condition holds.

We must show that the upper bound

is satisfied by every with , i.e., below and on or above , if and only if Condition (b) of Definition 14.2.1 holds. Since the bound is satisfied trivially if , we may assume that . Of the two lines and , has the greater slope and -intercept and therefore lies above for . But for and ,

and hence lies above in the region of interest. It follows that the required upper bound holds for all with if and only if lies entirely below , or equivalently, both upper vertices lie on or below . Suppose first that or , so that . If the slope is negative, then since

we have
 0

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

On the other hand, if , then . If the slope is positive, then every point lies below , since

 0

and if , then the critical vertex is the upper right. Thus, a necessary and sufficient condition is

The analysis of the lower bound,

is similar. Since the bound is satisfied trivially if , we may assume . For , lies below , since

and lies above , since

Consequently, the bound is satisfied for all with if and only if each point in lies on or above , as determined by its lower vertices. If , i.e., , then since

if , then for all ,

and if , then the critical vertex is the lower right. Therefore, the requirement is

If , then a similar argument yields the condition

The preceding results of this section may be summarized:

(srt-sqrt-theorem-a, srt-sqrt-theorem-b) Let , , , and be positive integers and let be an admissible radix- SRT square root table for every iteration . Let , . Let , , and for ,

and

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

PROOF: We shall prove by induction that for , and . Suppose that these conditions hold for . Then by Lemma 14.2.2, by Lemma 14.2.3, and consequently, for some and , and . Therefore, by hypothesis, and

By Lemma 14.2.2, , and by Lemma 14.2.3,

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 . In Section 14.3, we turn to the problem of generating the initial partial quotient and remainder, and .

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 is an admissible radix- square root table for all iterations , then is an admissible radix- division table.

PROOF: Suppose that

where , . Then for some ,

for all . Let . For all max, Conditions (a), (b), and (c) of Definition 14.2.1 hold. It follows that if , then

which implies . Similarly, if , then

which implies

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

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

then the following conditions hold for :

(a) .

(b) .

(c) If , then

A -admissible table is essentially one that is admissible for every iteration :

(admissibility-equivalence-a, admissibility-equivalence-b) Let , , , and be positive integers and let be an integer-valued function of two integer variables.

(a) If is a -admissible radix- SRT table, then for all , is an admissible SRT square root table for iteration k.

(b) Let be an admissible radix- SRT square root table for iteration k for all and let

Then is a -admissible radix- SRT table.

PROOF: Suppose that satisfies Definition 14.2.2. Let and

Then

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 , then we have , where

which implies

Now suppose is an admissible SRT square root table for every iteration and let be defined as above. Let

for some and and let . If , then

and Definition 14.2.2 is satisfied. In the remaining case,

and the three conditions of Definition 14.2.1 must hold for . Since (a) and (c) coincide with the corresponding conditions of Definition 14.2.2, we need only show that . Since this is clearly true if , we may assume that . Suppose . Then and it follows from (b) that

a contradiction. Therefore, we may also assume . But then for all ,

and hence

Consequently,

which implies

Thus, for given , , , and , Definition 14.2.2 may be used to determine whether there exists a table that is admissible all square root iterations , 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 , , , and be positive integers. There exists a -admissible radix- SRT table if and only if for all and with and , if

and

(where is defined as in Definition 14.1.1), then

In this case, one such table is defined by

max

PROOF: Let , , and

Suppose that if , then the conclusion of the lemma holds. Then clearly, the requirements of Definition 14.2.2 are satisfied by    max.

Conversely, suppose that some satisfies Definition 14.2.2 and that . Then and , where

and we need only show that . But note that is an increasing function of for , since

Therefore,

If for a -admissible table , then as noted in the proof of Lemma 14.2.4, must lie above the line . Consequently, in addition to the criterion given in Section 14.1, the staircase that separates the regions and must lie above that line.

Consider the division table of Figure 14.1. Since the lower left vertex of lies on , this point does not lie above ; therefore, this is not a -admissible square root table for any positive . Moreover, the same is true of every radix-4 table for every . There does, however, exist a 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 radix-8 table of Figure 14.2. Since the lower right vertex of lies on the line , this table cannot be used for the square root. As confirmed by ExistsDivSqrtTable, however, there exist both and 2-admissible radix-8 tables.

David Russinoff 2017-08-01