282 ARITHMETIC 4.3.3 The leftmost column of this (Web space)
282 ARITHMETIC 4.3.3 The leftmost column of this tableau is a listing of the given values of W(O), W(l), , W(4); the Icth succeeding column is obtained by computing the difference between successive values of the preceding column and dividing by. k. The coefficients 0, appear at the top of the columns, so that 130= 10, @I = 294, ** I 84 = 36, and we have W(z)=36&+341xc3+691×2+294&+10 = (((36(x -3) + 341)(x -2) + 691)(x -1) + 294)x + 10. (16) In general, we can write w(x) = (. . . ((f3,4~–m+2) + em-2)(x-m+3) + k3)(2-m+4) +-.+el)~+eo, and this formula shows how the coefficients M&-l, . . . , WI, Wo can be obtained from the e s: 36 341 -3.36 36 233 691 -2.36 -2 a233 (17) 36 161 225 294 -1.36 -1 . 161 -1.225 36 125 64 69 10 Here the numbers below the horizontal lines successively show the coefficients of the polynomials th, h4x + m + 2) + em-2, (emml(x -m + 2) + emp2)(x -77~ + 3) + emp3, etc. From this tableau we have W(z)=36×4+125×3+64×2+69x+10, so the answer to our original problem is 1234 . 2341 = W(16), where W(16) is obtained by adding and shifting. A generalization of this method for obtaining coefficients is discussed in Section 4.6.4. The basic Stirling number identity, n xn = x~+-.+{;}x~+{;}, 0n Eq. 1.2.6-41, shows that if the coefficients of W(x) are nonnegative, so are the numbers tl,, and in such a case all of the intermediate results in the above com- putation are nonnegative. This further simplifies the Toom-Cook multiplication algorithm, which we will now consider in detail.