Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
College Algorithms

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search