4.3.3 HOW FAST CAN WE MULTIPLY? 281 University, (Cheap web hosting)
4.3.3 HOW FAST CAN WE MULTIPLY? 281 University, 1966), 51-771 later showed how Toom s method can be adapted to fast computer programs. Before we discuss the Toom-Cook algorithm any further, let us study a small example of the transition from U(z) and V(x) to the coefficients of W(z). This example will not demonstrate the efficiency of the method, since the numbers are too small, but it points out some useful simplifications that we can make in the general case. Suppose that we want to multiply u = 1234 times 2, = 2341; in binary notation this is u = (0100 1101 0010)s times v = (1001 0010 0101)s. Let r = 2; the polynomials V(s), V(z) in (8) are U(x) = 4X2 + 132 + 2, V(x) = 9×2 + 2x + 5. Hence we find, for W(x) = U(x)V(s), U(0) = 2, U(1) = 19, U(2) = 44, U(3) = 77, U(4) = 118; V(0) = 5, V(1) = 16, V(2) = 45, V(3) = 92, V(4) = 157; W(0) = 10, W(1) = 304, W(2) = 1980, W(3) = 7084, W(4) = 18526. (12) Our job now is to compute the five coefficients of W(z) from the latter five values. There is an attractive little algorithm that can be used to compute the coefficients of a polynomial W(z) = Wm-lxm-l + . . . + WIz + W , when the values W(O), W(l), . . . , W(m -1) are given: Let us first write W(x) = 8,-l xd + 8,-2 xm–2 + . . . + 81x + eo, (13) where xk = X(X -1). . . (X - k + l), and where the coefficients I!?~ are unknown. The falling factorial powers have the important property that W(X + I) -W(X) = (77~-~)e,-~ 28 + (772-2)e,-2 xd + . . . + el; hence by induction we find that, for all k 2 0, em-1 x– m-l-k em-2xzkSL=!5+…+ : ok. (14) 0 Denoting the left-hand side of (14) by (l/k!) Ak W(z), we see that PA - W(s) (k: l)! and (l/k!) Ak W(0) = ok. So the coefficients 0, can be evaluated using a very simple method, illustrated here for the polynomial W(s) in (12): 10 294 304 138212 = 691 1676 = 341 1980 3428/2 =1714 102313 14414 = 36 (15) 7084 5104 6338/2 = 3169 145513 =485 11442 18526