4.3.3 HOW FAST CAN WE MULTIPLY? (Web hosting plans) 279 Formula
4.3.3 HOW FAST CAN WE MULTIPLY? 279 Formula (2) can be used for double-precision multiplication when we want a quadruple-precision result, and it will be just a little faster than the traditional method on many machines. But the main advantage of (2) is that we can use it to define a recursive process for multiplication that is significantly faster than the familiar order-n2 method when n is large: If T(n) is the time required to perform multiplication of n-bit numbers, we have T(2n) 5 3T(n) + cn (3) for some constant c, since the right-hand side of (2) uses just three multiplications plus some additions and shifts. Relation (3) implies by induction that 7727 5 C(3k -a ), k 2 1, if we choose c to be large enough so that this inequality is valid when k = 1; therefore we have T(n) I 7v q _ < c(3 rknl -2bl) < 3c. 31gn = 3cdg3. (5) Relation (5) shows that the running time for multiplication can be reduced from order n2 to order n1g3 z n1.585, so the recursive method is much faster than the traditional method when n is large. (A similar but more complicated method for doing multiplication with run- ning time of order n1g3 was apparently first suggested by A. Karatsuba in Doklady Akad. Nauk SSSR 145 (1962), 293-294 [English translation in Soviet Physics-Doklady 7 (1963), 595-5961. Curiously, this idea does not seem to have been discovered before 1962; none of the calculating prodigies who have be- come famous for their ability to multiply large numbers mentally have been reported to use any such method, although formula (2) adapted to decimal nota- tion would seem to lead to a reasonably easy way to multiply eight-digit numbers in one s head.) The running time can be reduced still further, in the limit as n approaches infinity, if we observe that the method just used is essentially the special case r = 1 of a more general method that yields qr + 1,g 2 (2r + l)T(n) + fm (6) for any fixed T. This more general method can be obtained as follows: Let zf = (U(,+l)n-1 . . . %740)2 and 21 = (y,+qn-1 . . . VlVO)Z be broken into r + 1 pieces, u = l&2,, + . . . + U12 + uo, 2, = V,2 +. . * + VIZ + vi, (7)