Any proof of correctness of the Toom-Cook algorithm?

Question

I found the toom-cook algorithm here: http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00037/Multiplication_1_print.pdf

and have been trying to chase down proof of it being correct, but can't find anything. Does anyone know how to go about proving the algorithm? I was thinking induction but I can't even figure out how to do it.

This is just for the three-way splitting, page 6. Any ideas?

Answer 1

If you're only interested in the three-way splitting…

We know that any natural number is a linear combination of powers of ten, where the coefficients are in the range [0,9]. This is our writing system for numbers: the coefficients are simply the digits of the number.

Let's assume that our number has at least six digits (just for simplicity). If it has less than that, we don't need Toom-Cook: $n$ is bounded by a constant, so we can do the multiplication in $O(1)$.

So our number can now be written as $a_0 10^0 + a_1 10^1 + a_2 10^2 + \cdots + a_n 10^n$, where all $a_i$ are single-digit non-negative integers. And $n$ is at least 6.

We also know that we can find $p$ such that $|(n - 2p) - p| \leq 1$. (If $n$ is divisible by 3, then $p = \frac{n}{3}$. If $n-1$ is divisible by 3, then we let $(n-2p)$ be larger by 1. And if $n-2$ is divisible by 3, then we increase $p$ by 1.)

Now, through the laws of multiplication and exponents, it's clear that our number is equal to $(a_0 10^0 + a_1 10^1 + \cdots) + (a_p 10^0 + a_{p+1} 10^1 + \cdots) 10^p + (a_{2p} 10^0 + a_{2p+1} 10^1 + \cdots) 10^{2p}$.

Thus, the number can be divided into three generally-close-to-equal parts, as the paper says.