Toom-Cook Multiplication

[danbaron]

I think that Toom-Cook is still one of the fastest methods for multiplying big integers of less than 10,000 digits (the other being Karatsuba, which I haven't looked at).

http://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm

http://en.wikipedia.org/wiki/Toom–Cook_multiplication

http://en.wikipedia.org/wiki/Karatsuba_multiplication

I may be wrong (I often am), but my impression is that Toom-Cook is pretty simple.

I can show my idea of the basic concept by an example.

Say, we want to multiply 23 times 35.

We write,

p(x) = 2x + 3,
q(x) = 3x + 5.

We are using our realization that any integer can be written as a polynomial.
Here, p(x), represents 23, and q(x), represents 35, when x equals 10.

We write,

p(x)q(x) = r(x).

That is, p(x) times q(x), equals r(x).

So,

(2x + 3)(3x + 5) = ax^2 + bx + c = r(x).

Now,

p(0)q(0) = r(0).

So,

(2*0 + 3)(3*0 + 5) = a*0 + b*0 + c.

Therefore,

c = 15.

Now,

p(1)q(1) = r(1).

Therefore, when we do the substitutions (for x and c),

a + b = 25.

Now,

p(-1)q(-1) = r(-1).

Therefore, when we do the substitutions (for x and c),

a - b = -13.

Now, we already know c, and we just need to find a and b.
We have two linear equations and two unknowns,

a + b = *25,
a - b = -13.

We just add the two equations and we get,

2a = 12.

Therefore,

a = 6.

Now, we can substitute 6 for a in,

a + b = 25,

and we get,

b = 19.

So,

r(x) = 6x^2 + 19x + 15.

Now, we substitute 10 for x in r(x), and we are done,

r(10) = 600 + 190 + 15 = 805.

Believe it or not!



(We could have just multiplied p(x) times q(x) to find the coefficients of r(x), right? That is, we could have multiplied (2x + 3)(3x + 5); but this is supposed to be fast multiplication, and that is what we want to avoid doing (If we multiply p(x) times q(x), then we have gained nothing, correct?). That is the trick to the method, we don't do those multiplications. In a real case, the coefficients of p(x) and q(x) would typically be huge.

Also, I think that usually p(x) and q(x) are written as quadratic polynomials (both of the numbers to be multiplied are split into 3 parts of approximately equal numbers of digits), and then, the method is called Toom-3 (a quadratic polynomial has 3 coefficients). How, if you wanted to do so, you would determine the polynomial degree which is most efficient for a particular multiplication, I don't know.

Also, when at the end we substituted 10 into r(x) to get the answer, 805, in this case, doing that only required register shifting and additions. We should always be able to choose our base so that this final step only requires register shifting and additions.)