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).

 
Source
< Prev   CONTENTS   Source   Next >