Fast Multiplication Algorithms for Large Integers
Date: 08/16/97 at 11:51:31 From: Richard Eager Subject: Fast Multiplication Algorithms for Large Integers I am wondering if there are any 'elementary' algorithms for computing the product of 2 n-digit numbers in less than O(n^1.58) time (that is an algorithm from Knuth that uses a few algebra tricks to speed up long-hand multiplication). The only faster algorithms I have heard of are FFT multiplication routines. One method I have tried (based on some reading) is using modular arithmetic, but it is slow converting backwards - i.e. to multiply 17 by 23, find each number mod 7,11,13 and multiply each congruence: | 7 11 13 --------------- 17 | 3 6 4 --------------- 23 | 2 1 10 --------------- x | 6 6 1 So then you have to solve: x = 6 (mod 7) (= represents the congruence symbol) x = 6 (mod 11) x = 1 (mod 13) This can be reduced to: x = 6 (mod 77) x = 1 (mod 13) which has a solution: 391 (+ 1001n) Several mod multiplications and additions can be done all in linear time before converting back (i.e. you could multiply 1000000 10000-digit numbers and add them together in about twice the time it would take to multiply only 2 numbers). Is there a very efficient algorithm for converting back? Or can FFT multiplication be explained with only mod arithmetic and pre-calculus? Thanks, Richard Eager
Date: 08/26/97 at 13:03:59 From: Doctor Rob Subject: Re: Fast Multiplication Algorithms for Large Integers The *mechanics* of the FFT algorithm can be explained, but not the reason why it works. I know of no general-purpose faster algorithms. Inverting the multiple-moduli scheme is not too tough, however. Once you have picked the moduli to be pairwise relatively prime, you can do some one-time work to set up the inversion process, and then it goes fairly quickly. The operative theorem is the Chinese Remainder Theorem, and there is an algorithm for computing the unique smallest positive x such that x = a[i] (mod m[i]). x is determined modulo m = Prod m[i]. For each i, compute b[i] = m/m[i], and c[i] and d[i] such that 1 = c[i]*b[i] + d[i]*m[i]. This is usually done with the Extended Euclidean Algorithm. Set e[i] = b[i]*c[i]. Once this is done, you are ready. Now given a problem of the type x = a[i] (mod m[i]), you can compute x using the following formula: x = Sum a[j]*e[j] (mod m). The proof that this works is that, when you reduce this modulo m[i], e[j] = b[j] = 0 (mod m[i]) if i <> j, so all terms but the i-th one are zero in the above sum. Furthermore, e[i] = 1 (mod m[i]) by construction, so x = a[i] (mod m[i]). Example: You chose moduli 7, 11, and 13. m = 7*11*13 = 1001, and b = 143, b = 91, and b = 77. Then it doesn't take long to find that 1 = 5*143 - 102*7, 1 = 4*91 - 33*11, and 1 = 12*77 - 71*13, so e = 715, e = 364, and e = 924. Now given x = 6 (mod 7), x = 6 (mod 11), and x = 1 (mod 13), using the formula, we get x = 6*715 + 6*364 + 1*924 = 7398 = 391 (mod 1001). You don't have to recompute the e[i]'s every time, only when you change the set of moduli. The complexity of forming the sum of products and doing one modular reduction is not huge. I leave it to you to figure that out, recalling that the a[i]'s are all smaller than m[i], while the e[i]'s are smaller than m. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.