This article is based on a brilliant essay in Quanta magazine, behind which lies a lovely story of a mathematical discovery. I take the essay a little further and describe an algorithm we posted on arxiv to increase the speed of the calculation even further (though not as fast as the fastest method there is).
You probably learned to multiply numbers in elementary school. If you multiplied two 4-digit numbers, you learnt to multiply the second number’s unit digit ( in the below) like so
You’d then progress on to the tens digit, repeat the same procedure (multiply by each digit of the first number. While doing so, you remember to write out the digits of the second multiplication by one place to the left and on and on. If you were multiplying two digit numbers, you would need to perform single-digit multiplications.
Multiplication is one of the most well-understood mathematical operations, it was thought, when the famous mathematician and physicist Andrey Kolmogorov gave a series of lectures on complexity theory at the Moscow State University in the 1960s. One of the students listening to the famous man speak about the order of the number of operations required to perform complex arithmetic tasks was a fellow called Anatoly Karatsuba. He heard Kolmogorov describe multiplication as an operation for two -digit numbers. Later he went home and over the week of lectures managed to prove a much faster way to multiply two numbers. He wrote this up for Kolmogorov, who, suitably impressed, mentioned it in other lectures. Kolmogorov then wrote it up for publication, as the contribution of Karatsuba and another student Yuri Ofman, without their knowledge – they heard only from getting printer proofs!
The algorithm they invented is very simple to explain for four digit numbers. Suppose we wanted to multiply and , where
where are two-digit numbers. The product of these two numbers is
One would normally think that one would need to perform four multiplications and two additions to compute this, but note, as Anatoly Karatsuba did, that this could be written as
which therefore needs only three multiplications and three additions.
Generalizing this “divide-and-conquer” strategy results in a systematic recursion relation between the complexity of the -digit number multiplication and the -digit multiplication, i.e.,
where the last term captures the order- additions that have to also be performed. This function can be computed for large and yields
The method is elegant and simple, but has since been superseded by far more analytically complex Fourier transform algorithms that are and indeed itself in complexity.
. Note that if you possible multiplications of -digit numbers, you would need to compute entries into a giant matrix. It would then take you searches to find the particular element you wanted to find, which is of .