Karatsuba and Toom-3 algorithms for 3-digit number multiplications

Question

I was wondering about this problem concerning Katatsuba's algorithm. When you apply Karatsuba you basically have to do 3 multiplications per one run of the loop Those are (let's say ab and cd are 2-digit numbers with digits respectively a, b, c and d):

X = bd
Y = ac
Z = (a+c)(c+d) 

and then the sums we were looking for are:

bd = X 
ac = Y 
(bc + ad) = Z - X - Y

My question is: let's say we have two 3-digit numbers: abc, def. I found out that we will have to perfom only 5 multiplications to do so. I also found this Toom-3 algorithm, but it uses polynomials I can;t quite get. Could someone write down those multiplications and how to calculate the interesting sums bd + ae, ce+ bf, cd + be + af

Answer 1

The basic idea is this: The number 237 is the polynomial p(x)=2x²+3x+7 evaluated at the point x=10. So, we can think of each integer corresponding to a polynomial whose coefficients are the digits of the number. When we evaluate the polynomial at x=10, we get our number back.

What is interesting is that to fully specify a polynomial of degree 2, we need its value at just 3 distinct points. We need 5 values to fully specify a polynomial of degree 4.

So, if we want to multiply two 3 digit numbers, we can do so by:

1. Evaluating the corresponding polynomials at 5 distinct points.
2. Multiplying the 5 values. We now have 5 function values of the polynomial of the product.
3. Finding the coefficients of this polynomial from the five values we computed in step 2.

Karatsuba multiplication works the same way, except that we only need 3 distinct points. Instead of at 10, we evaluate the polynomial at 0, 1, and "infinity", which gives us b,a+b,a and d,d+c,c which multiplied together give you your X,Z,Y.

Now, to write this all out in terms of abc and def is quite involved. In the Wikipedia article, it's actually done quite nicely:

1. In the Evaluation section, the polynomials are evaluated to give, for example, c,a+b+c,a-b+c,4a+2b+c,a for the first number.
2. In Pointwise products, the corresponding values for each number are multiplied, which gives:

X = cf
Y = (a+b+c)(d+e+f)
Z = (a+b-c)(d-e+f)
U = (4a+2b+c)(4d+2e+f)
V = ad

1. In the Interpolation section, these values are combined to give you the digits in the product. This involves solving a 5x5 system of linear equations, so again it's a bit more complicated than the Karatsuba case.