Web hosting contract - 290 ARITHMETIC 4.3.3 The reader will find it
290 ARITHMETIC 4.3.3 The reader will find it instructive to study the ingenious method represented by (30) and (31) very carefully. Similar techniques are discussed in Section 4.6.3. SchGnhage s paper [Computing 1(1966), 182-1961 shows that these ideas can be extended to the multiplication of n-bit numbers using T z 2G moduli, obtaining a method analogous to Algorithm C. We shall not dwell on the details here, since Algorithm C is always superior; in fact, an even better method is next on our agenda. C. Use of discrete Fourier transforms. The critical problem in high-precision multiplication is the determination of convolution products such as urvo + %-1Ul + * *. + Uo%, and there is an intimate relation between convolutions and an important math- ematical concept called Fourier transformation. If w = exp(27ri/K) is a Kth root of unity, the one-dimensional Fourier transform of the sequence of com- plex numbers (uo, ul,. . . , UK–~) is defined to be the sequence (CO, Q1, . . . ,+&-I), where ii, = c wstut , O