280 ARITHMETIC 43.3 where each Uj and each (Christian web host)
280 ARITHMETIC 43.3 where each Uj and each Vj is an n-bit number. Consider the polynomials U(x) = &XT +. . . + UlX + VI& V(x) = V,x + * * * + VlX + vo, 63) and let W(x) = U(x)V(x) = W2rx2r + * * * + WlX + wi. (9) Since u = U(2n) and Y = V(2n), we have UZI = W(2n), so we can easily compute uz, if we know the coefficients of W(z). The problem is to find a good way to compute the coefficients of W(z) by using only 2r + 1 multiplications of n-bit numbers plus some further operations that involve only an execution time proportional to n. This can be done by computing U(O)V(O) = W(O), U(l)V(l) = W(l), . . . , U(2r)V(2r) = W(2r). (10) The coefficients of a polynomial of degree 2r can be written as a linear com- bination of the values of that polynomial at 2r + 1 distinct points; computing such a linear combination requires an execution time at most proportional to n. (Actually, the products U(j)V(j) are not strictly products of n-bit numbers, but they are products of at most (n + t)-bit numbers, where t is a fixed value depend- ing on T. It is easy to design a multiplication routine for (n + t)-bit numbers that requires only T(n) + cln operations, where T(n) is the number of operations needed for n-bit multiplications, since two products of t-bit by n-bit numbers can be done in csn operations when t is fixed.) Therefore we obtain a method of multiplication satisfying (6). Relation (6) implies that T(n) 2 csn10g~+l(27f1) < cgnl-t os~+l 2, if we argue as in the derivation of (5), so we have now proved the following result: Theorem A. Given f > 0, there exists a multiplication algorithm such that the number of elementary operations T(n) needed to multiply two n-bit numbers satisfies T(n) < c(e)nl+ , (11) for some constant C(E) independent of n. I This theorem is still not the result we are after. It is unsatisfactory for practical purposes in that the method becomes much more complicated as E –+ 0 (and therefore as r + oo), causing C(E) to grow so rapidly that extremely huge values of n are needed before we have any significant improvement over (5). And it is unsatisfactory for theoretical purposes because it does not make use of the full power of the polynomial method on which it is based. We can obtain a better result if we let r vary with n, choosing larger and larger values of T as n increases. This idea is due to A. L. Toom [Doklady Akad. Nauk SSSR 150 (1963), 496-498, English translation in Soviet Mathematics 3 (1963), 714-7161, who used it to show that computer circuitry for multiplication of n-bit numbers can be constructed involving a fairly small number of components as n grows. S. A. Cook [On the minimum computation time of functions (Thesis, Harvard