Given a rational number in the range , our objective is to construct a sequence of partial roots, , that converge to . 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:
PROOF: The equivalence of (a) and (b) follows from Lemma 14.2.1:
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 , :
(a) If , then .
(b) If and , then .
PROOF: Since is an integral multiple of , implies .
Suppose . By Lemma 14.2.2,
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:
(b) If , then
(c) If , then
PROOF: Consider the following four lines in the -plane:
We must show that the upper bound
On the other hand, if
. If the
slope is positive, then every point
lies below , since
The analysis of the lower bound,
The preceding results of this section may be summarized:
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
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:
PROOF: Suppose that
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:
(c) If , then
A -admissible table is essentially one that is admissible for every iteration :
(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
PROOF: Suppose that satisfies Definition 14.2.2. Let and
Now suppose is an admissible SRT square root table for every iteration and let be defined as above. Let
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:
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
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