Humans have known how to multiply natural numbers for a long time. In primary school you learn how to multiply numbers using an algorithm which is often called long multiplication, and it was known to the ancient Babylonians. But it’s called “long” for a reason — you have to write a lot of lines! If you’re multiplying two numbers which both have length n, then you have to multiply every digit of the first number by every digit of the second number, so there are $$n^2$$ multiplication operations. Then there are several additions. But addition is much easier than multiplication, as you learn in primary school: you can just go down column by column and work it out, and adding up two numbers of length n only takes roughly n operations.

In 1960, the great mathematician Andrey Kolmogorov was teaching a seminar in Soviet Russia. He conjectured that the ancient Babylonian method was best possible, in the sense that any algorithm to multiply natural numbers of length n must involve at least n^2 single-digit multiplication operations. One of the students in that seminar was Anatoly Karatsuba. One week later, Karatsuba came back with an improved method, which requires only  about $$n^{\log_2 3} \sim n^{1.58}$$ multiplications. (Strictly speaking it’s $$O(n^{log_2 3})$$, if you know “big-O notation“.)

Karatsuba’s method to multiply two 2-digit numbers involves multiplying the the units digits, multiplying the tens digits, and then multiplying the sum of the digits of one number by the sum of the digits of the other number. With some judicious addition, subtraction and placement of extra zeroes, the required product can be found. Karatsuba’s method in general repeats this method, in a recursive fashion, on larger numbers.

This was all in the news recently. Since Karatsuba’s breakthrough, there have been several further advances in the multiplication of natural numbers. But in the last few weeks, a paper was posted by two mathematicians, including David Harvey, an Australian number theorist at UNSW. It purports to give an algorithm to multiply natural numbers in time $$O(n \log n)$$. A good article about all this recently appeared in quanta magazine, which is worth a read: here’s a link.

Breakthroughs in primary school arithmetic
Tagged on: