 Squaring

In the preceding algorithms, (uv)i, has both и and v as single-precision integers. This notation is abused in this subsection by permitting и to be a double-precision integer, such that 0 < и < 2(6 - 1). The value v will always be single-precision.

14.16 Algorithm Multiple-precision squaring

INPUT: positive integer x = (xt-iXt-2 • ■ • ххо)ь- OUTPUT: x ■ x = x2 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)b-t— 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 4v, c<—u.
• 2.3 wi+t<-u.
• 3. Retum((u>2«-iu>2t-2 • • • wiw0)b)-
• 14.17 Note (computational efficiency of Algorithm 14.16)
• (i) (overflow) In step 2.2, и can be larger than a single-precision integer. Since wi+j is always set to v, wi+j < 6-1. If c < 2(6 - 1), then wi+j + 2XjXt + c < (b - 1) + 2(6 - l)2 + 2(6 - 1) = (6 - 1)(26 + 1), implying 0 < и < 2(6 - 1). This value of и may exceed single-precision, and must be accommodated.
• (ii) (number of operations) The computationally intensive part of the algorithm is step 2. The number of single-precision multiplications is about (t2 + f)/2, discounting the multiplication by 2. This is approximately one half of the single-precision 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 x2) 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 speed-up 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 + 2-9-9+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 + 2-9-8 + 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: Multiple-precision squaring (see Example 14.19).