0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The equations may be too simple for algebraists, coding too straight-forward for coders - which part do you want to prove?) $\endgroup$ – greybeard Jun 1 '18 at 4:08
  • $\begingroup$ Just proof that it would work in any case of multiplication, so I guess algebraists. I didn't think to look it up on math.SE, I'll look through it thank you! $\endgroup$ – Andrew Raleigh Jun 1 '18 at 14:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Decimal focus" aside: differing by no more than a single order of magnitude is _not guaranteed: $a_n$ conventionally isn't zero, but there are no guarantees about, e.g., $a_{p-1}$, $a_{p-2}$, … $\endgroup$ – greybeard Jun 1 '18 at 6:51
  • $\begingroup$ @greybeard Oops, good point! Adjusted. (The decimal focus is because that's how the paper did it.) $\endgroup$ – Draconis Jun 1 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.