Squaring
In the preceding algorithms, (uv)i, has both и and v as singleprecision integers. This notation is abused in this subsection by permitting и to be a doubleprecision integer, such that 0 < и < 2(6  1). The value v will always be singleprecision.
14.16 Algorithm Multipleprecision squaring
INPUT: positive integer x = (xtiXt2 • ■ • ххо)ь OUTPUT: x ■ x = x^{2} in radix 6 representation.
 1. For i from 0 to (2f  1) do: ги_{;}<0.
 2. For i from 0 to (t  1) do the following:
 2.1 (wn)bt— W2i + Xi ■ Xi, W2i^V, c<—u.
 2.2 For j from (i + 1) to (i  1) do the following:
 (uv)b<^Wi+j + 2Xj ■ Xi + C, Wi+j 4—v, c<—u.
 2.3 w_{i+t}<u.
 3. Retum((u>2«iu>2t2 • • • wiw_{0})b)
 14.17 Note (computational efficiency of Algorithm 14.16)
 (i) (overflow) In step 2.2, и can be larger than a singleprecision integer. Since w_{i+}j is always set to v, w_{i+}j < 61. If c < 2(6  1), then w_{i+}j + 2XjX_{t} + c < (b  1) + 2(6  l)^{2} + 2(6  1) = (6  1)(26 + 1), implying 0 < и < 2(6  1). This value of и may exceed singleprecision, and must be accommodated.
 (ii) (number of operations) The computationally intensive part of the algorithm is step 2. The number of singleprecision multiplications is about (t^{2} + f)/2, discounting the multiplication by 2. This is approximately one half of the singleprecision multiplications required by Algorithm 14.12 (cf. Note 14.15(ii)).
 14.18 Note (squaring vs. multiplication in general) Squaring a positive integer x (i.e., computing x^{2}) can at best be no more than twice as fast as multiplying distinct integers x and y. To see this, consider the identity xy = ((x + y)^{2} — (x — y)^{2})/4. Hence, x ■ у can be computed with two squarings (i.e., (a; + y)^{2} and (x  y)^{2}). Of course, a speedup by a factor of 2 can be significant in many applications.
 14.19 Example (squaring) Table 14.4 shows the steps performed by Algorithm 14.16 in squaring x = 989. Here, t = 3 and 6 = 10. □
i 
3 
W2i + Xi 
Wi+j + 2xjXi + c 
u 
V 
Wb 
WA 
W 3 
U>2 
W1 
Wo 
0 
 
0 + 81 
 
8 
1 
0 
0 
0 
0 
0 
1 
1 
 
0 + 2 • 8 • 9 + 8 
15 
2 
0 
0 
0 
0 
2 
1 

2 
— 
0 + 299+15 
17 
7 
0 
0 
0 
7 
2 
1 

17 
7 
0 
0 
17 
7 
2 
1 

1 
— 
7+ 04 
— 
7 
1 
0 
0 
17 
1 
2 
1 
2 
— 
17 + 298 + 7 
10 
8 
0 
0 
8 
1 
2 
1 

10 
8 
0 
10 
8 
1 
2 
1 

2 
 
16 + 81 
 
9 
7 
0 
7 
8 
1 
2 
1 
9 
7 
9 
7 
8 
1 
2 
1 
Table 14.4: Multipleprecision squaring (see Example 14.19).