4.3.3 HOW FAST CAN WE MULTIPLY? 287 B. (Web hosting support)
4.3.3 HOW FAST CAN WE MULTIPLY? 287 B. A modular method. There is another way to multiply large numbers very rapidly, based on the ideas of modular arithmetic as presented in Section 4.3.2. It is very hard to believe at first that this method can be of advantage, since a multiplication algorithm based on modular arithmetic must include the choice of moduli and the conversion of numbers into and out of modular representation, besides the actual multiplication operation itself. In spite of these formidable difficulties, A. Schijnhage discovered that all of these operations can be carried out quite rapidly. In order to understand the essential mechanism of Schonhage s method, we shall look at a special case. Consider the sequence defined by the rules 40 = 1, qk+l = 3qk -1, (20) SO that qk = 3 -3k-1 -… -1 = B(3k j- 1). We will study a procedure that multiplies (18qk + 
-bit numbers, in terms of a method for multiplying (18qk-i + -bit numbers. Thus, if we know how to multiply numbers having (18qo + = 26 bits, the procedure to be described will show us how to multiply numbers of (18ql + = 44 bits, then 98 bits, then 260 bits, etc., t.w&,ually increasing the number of bits by almost a factor of 3 at each step. Let pk = 18qk + 8. When multiplying &-bit numbers, the idea is to use the six moduli ml = pa-1 -1 , m2 = 26a+l -1 9 m3 = 2%+2 -1 m4 = 2@+3 -1 7 m5 = pa+5 -1 , m6 = 26~+7 -1. (21) These moduli are relatively prime, by Eq. 4.3.2-18, since the exponents %7/c–1, 640+1, 6%+2, 6qk+3, 6qk+5, 6qkf7 (22) are always relatively prime (see exercise 6). The six moduli in (21) are capable of representing numbers up to m = m1m2msm4m5ms > 236qk+16 = 22Pk, so there is no chance of overflow in the multiplication of pk-bit numbers u and v. Thus we may use the following method, when k > 0: a) Compute ~1 = Umodml, . . . . us = umodms; and vi = vmodmi, . . . , 216 = V mod ms. b) Multiply u1 by vl, u2 by v2, . . . , us by vs. These are numbers of at most 6qk +7 = 18qk-l+ 1 < pk-1 bits, so the multiplications can be performed by using the assumed pk-l-bit multiplication procedure. C) COmpUte w1 = uivi modmi, ws = 212212modms, . . . , ws = u6v6 mod ms. d)ComputewsuchthatO~w