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[1] = 143, b[2] = 91, and b[3] = 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[1] = 715, e[2] = 364, and e[3] = 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/