Multiplying Integers

Simple multiplication algorithm

If you’re asked to multiply $25$ and $63$ and you don’t have a calculator handy, what would you do? You would probably use the multiplication algorithm you learned in elementary school, multiplying each digit from one number with each digit from the other and then adding up the products:

Stop and think: What is the running time of this algorithm applied to two $n$-digit numbers? Can you propose a faster multiplication algorithm?

Since this algorithm multiplies each digit of the first number with each digit of the second number, it requires a quadratic number of multiplications. Can it be done faster, e.g., in $O(n^{1.5})$?

In 1960, the great Russian mathematician Andrey Kolmogorov conjectured that the multiplication algorithm we learned in elementary school is asymptotically optimal and, therefore, cannot be improved in the sense of the big-$O$ notation. Within a week after he presented this conjecture at a seminar, a 23-year-old student, Anatoly Karatsuba, proved him wrong! We describe the Karatsuba algorithm below.

Karatsuba algorithm

The Karatsuba algorithm is a different (more complex, but fast!) multiplication algorithm. Let’s multiply two-digit numbers $AB$ and $CD$, where $AB$ is $10A + B$ and $CD$ is $10C+D$:

$$(10A+B)×(10C +D) = 100(A×C)+10(A×D)+10(B×C)+B×D.$$

Here, we have four small multiplications $A×C$, $A×D$, $B×C$, and $B×D$ and it appears it cannot be done with fewer multiplications. Note that we do not count multiplications by $100$ and $10$ as “real” multiplications as they amount to simply adding zeroes.

Exercise break: Can you multiply $AB$ and $CD$ with three multiplications using the hint below?

$$(10A + B) × (10C + D) = 100(A×C) + 10(A×D)+10(B×C) + B×D$$ ...