Square rooting deserves special attention because of its frequent use in a number of applications ([ERC1994], [OBE1999]). Although square rooting can be viewed as a particular case of the exponential operation, the similarity with division is a more important consideration for the choice of algorithms. Several techniques in base-B and in binary systems are reviewed in this section.
Let
be the 2n-digit base-B radicand.
The square root Q and the remainder R are denoted
and
respectively.
The remainder
ensuring that
The classical pencil and paper method, described in what follows, assumes that all roots of 2-digit numbers are available ((B2 − 1) × (B − 1) look-up table). Allowing the first digit of X to be zero, the radicand can always be sliced into n 2-digit groups. Algorithm 7.11 computes the square root of the 2n-digit integer X. The symbol * stands for integer multiplication, while ** and / stand for integer exponentiation and division respectively. One defines the function P(i, k) as
Algorithm 7.11 Integer Square Rooting in Base B
R(0):=X; Q(n−1):=0; q(n−1):=SQR (R(0)/B**(2*n-2)); Q(n-2):=q(n−1); R(1):=R(0)-(q(n−1)**2)*(B**(2*n-2)); for i in 2..n loop if P(i, B-1)<=R(i-1) then R(i):=R(i-1)-P(i, B-1); q(n-i):=B-1; Q(n-i-1):=B*Q(n-i)+q(n-i); elsif P(i, B-2)<=R(i) then R(i):=R(i-1)-P(i, B-2); q(n-i):=B-2; Q(n-i-1):=B*Q(n-i)+q(n-i); elsif … elsif P(i, 1) <=R(i) then R(i):=R(i-1)-P(i, 1); q(n-i):=1; Q(n-i-1):=B*Q(n-i)+q(n-i); else R(i):=R(i-1); q(n-i):=0; Q(n-i-1):=B*Q(n-i)+q(n-i); end if; end loop;
Example 7.12 Compute the square root of X = (591865472)10
Slicing (n = 5) gives X = R(0) = 05 '91 '86 '54 '72
Step 1
Step 3
Step 4
Step 5
Comments 7.6 The process can be carried on further, up to the desired quantity of digits after the decimal point.
The function P(i, k) (7.75) of Algorithm 7.11 is used to compute the greatest value of k verifying P(i, k) ≤ R (i − 1).
Actually, k can be defined algebraically by the formula
the integer part of the solution to such that
where
Obviously formula (7.76), using the square root, is useless for algorithmic implementation. Other methods must therefore be derived to get k verifying (7.78).
Techniques for square rooting in base B > 2 are quite similar to those for base-B division. The recurrence formula for the remainder is given by
with
for 2n-digit integers.
In base 2, the computation of the function P(i, k) is obviously more straightforward, since just 0 or 1 have to be considered for k. Moreover, since P(i, 0) = 0, just P(i, 1), hereafter denoted P(i), is computed,
Defining
Algorithm 7.11 can be simplified as follows.
Algorithm 7.12 Integer Binary Square Rooting; Restoring
R(0):=X; Q(n−1):=0; q(n):=0; P(1):=2**(2*(n−1)); for i in 1..n, loop if R(i−1)-P(i)>=0 then R(i):=R(i−1)-P(i); q(n-i):=1; Q(n-i−1):=2*Q(n-i)+q(n-i); else R(i):=R(i−1); q(n-i):=0; Q(n-i−1):=2*Q(n-i)+ q(n-i); end if; end loop;
Example 7.13 Compute the square root of
Step 1
Step 2
Step 3
Step 4
Step 6
Comments 7.7
As well as in the classical binary division algorithm, restoring the remainder, whenever negative, is not necessary since the following operation can cope with a negative remainder and perform in a single operation the restoring process together with the next step operation.
Considering a current step i, notice that when
the nonrestoring algorithm proceeds like the restoring one.
Whenever
the restoring process would add back P(i) to the partial result (7.84), set q(n − i) to zero, then subtract P(i + 1) from restored R(i − 1). These operations can be substituted by adding, to the partial result (7.84), the following expression
at the next step i + 1.
Since, from step i (7.84), q(n − i) = qn−i = 0, one can write:
and
then
Assuming
(7.88) can be written
The nonrestoring binary square rooting method is described in Algorithm 7.13, where P(i) and Pstar(i) are defined as follows
Algorithm 7.13 Integer Binary Square Rooting; Nonrestoring
R(0):=X; Q(n−1):=0; q(n):=0; P(1):=2**(2*(n−1)); R(1):=R(0)-P(1); if R(1)>=0 then q(n−1):=1; Q(n-2):=1; else q(n−1):=0; Q(n-2):=0; end if; for i in 2..n loop if R(i-1)>=0 then R(i):=R(i-1)-P(i); else R(i):=R(i-1)+Pstar(i); end if; if R(i)>=0 then q(n-i):=1; Q(n-i-1):=2*Q(n-i)+q(n-i); else q(n-i):=0; Q(n-i-1):=2*Q(n-i)+q(n-i); end if; end loop;
As well as for nonrestoring division algorithms, a final correction may be necessary. Whenever the final remainder is negative, it needs to be adjusted to the previous positive one.
Example 7.14 Note: 2's complement notation is used; the sign bit is in boldface type
Compute the square root of
Step 1
Step 2
Step 3
Step 5
Step 6
Step 7
the exact square root.
Comments 7.8 The square rooting methods developed in the preceding sections are classic and easy to implement. The main component involved in the step complexity is the signed sum. One digit is obtained at each step (digit recurrence), so, for a desired precision p, p n-digit adding stages are involved, combinationally or sequentially implemented. To speed-up the process, fast adders may be used. SRT type algorithms have been developed for square rooting, using the feature of carry-save redundant adders ([ERC2004]). On the other hand, convergence algorithms have been developed, such as Newton–Raphson, reviewed in the following section.
The priming function for square root computation could be
which has a root at x=X1/2.
To solve f(x)=0, the same equation used for inverse computation can be used:
or
Formula (7.94) involves a division and an addition at each step, which makes Newton–Raphson's method apparently less attractive in this case. Nevertheless, computing the inverse square root 1/X1/2, then multiplying by the radicand X, leads to a more effective solution.
The priming function is now
with root x=1/X1/2, and the equation of convergence is given by
which involves three multiplications, one subtraction (3's complement), and one division by 2 (shift in base 2). A final multiplication is needed: the inverse square root by the radicand.