Karatsuba Multiplication

When we were kids, teachers taught us how to multiply. My generation probably was taught the standard multiplication algorithm. That is, take the first digit, multiply out the second number's digits one by one with carry, then repeat for every digit of the first number, and remembering to shift correctly.

On a side note, the "newer" younger math generation are sometimes taught weird things. The logic behind it is giving a chance for the kids to develop a sense of "why" of how the multiplication algorithm works, and make it easier for more kids to understand. I think it's retarded. Kids don't give a shit why this works, except young Gauss and other great ones. Anyways...

We are so familiar with multiplication, having done it for years and years before having access to the calculator at school, that we don't really think about: is there a faster way? What if we had two numbers with a 1024 digits each?

Multiplying it out with the standard algorithm, we would have to carry $1024^2$ multiplications, and then another $1024^2$ digit additions.

So can you think of a better way to multiply? Well, Komolgorov, a prominent mathematician, a pioneer of computational complexity, analysis and probability theory, conjectured (yes conjectured, because he was so convinced) in 1952 that there is no way of doing considerably better than that simple algorithm (meaning better than $\mathcal{O}(n^2)$ digit operations). In 1960, he announced his conjecture in a seminar on computational complexity, and a few days later, a student by the name of Karatsuba came up with an algorithm that was strictly better than standard multiplication. Needless to say, it was quite an embarrassing event for Komolgorov.

Curiously enough, this algorithm is extremely simple. The idea goes as follows:

Given a multiplication $a\cdot b$, we can rewrite $a = a_110^m + a_0$ and $b = b_110^m + b_0$ where we choose an $m$ that will cut the digits of $a$ and $b$ in the middle more or less. Now we notice that $a\cdot b = a_1b_110^{2m} + (a_1b_0 + a_0b_1)10^m + a_0b_0$. Now we still haven't done anything new. This is still what standard multiplication is doing. Karatsuba noticed that we can find $(a_1b_0 + a_0b_1)$ in not 2, but 1 multiplication step. The trick, $(a_1b_0 + a_0b_1) = (a_1+a_0)(b_1+b_0) - a_1b_1 - a_0b_0$. Since we already computed $a_1b_1$ and $a_0b_0$, we only have to multiply out the first term.

Ok, how is this so much better than standard multiplication? Informally, if we recursively apply this trick to compute $(a_1+a_0)(b_1+b_0)$, $a_1b_1$ and $a_0b_0$, we get a "multiplication tree" of depth $\mathcal{O}(\log(n))$ with each node branching into 3 subnodes. Standard multiplication has an extra multiplication step, so each node branches into 4 subnodes. This extra subnode obviously compounds rapidly at every layer.

Returning to our first example, multiplying two numbers with 1024 digits with this method takes $3^{10} = 59049$ digit multiplications instead of $1024^2 = 4^{10} = 1048576$.

What about the extra addition steps? Well, you can convince yourself that the addition steps from having more multiplication steps will blow up anyways.

Conclusion: Karatsuba Multiplication takes order $\mathcal{O}(n^{\log_23})$ digit multiplications, and should be used to multiply numbers with more than around 200 digits.

For more recent developments, algorithms have been found to do even better than Karatsuba's, but they involve much heavier mathematical artillery such as Fast Fourier Transforms.

Happy Halloween!

[DM]