We have seen the idea of nested multiplication, which provides one answer to the question: “How do I evaluate this polynomial quickly?”.

One interesting related question is: “How do I multiply these two numbers quickly?”. Using normal elementary school multiplication we achieve a O(n²) runtime for multiplying two n-bit numbers together. I’ve come across an interesting multiplication technique called Karatsuba multiplication that has a better asymptotic runtime, and is widely used in mathematical software today to multiply large numbers.

We will now see how to multiply two 2-digit numbers together using this multiplication routine:

w = the base of the 2-digit numbers

a = a1*w + a0

b = b1*w + b0

a*b = (a1*w + a0)*(a1*w + a0)
= a1*b1*w² + (a0*b1 + a1*b0)*w + a0*b0


Let the coefficients of this polynomial be represented by p2, p1, and p0:

p2 = a1*b1
p1 = a0*b1 + a1*b0
p0 = a0*b0

However, instead of computing p1 directly, let us introduce an alternative equivalent expression for p1:

p1 = (a0 + a1)*(b0 + b1) - p2 - p0


By using this alternate expression for computing p1, we are doing three multiplications instead of four to compute p2, p1 and p0. This expression is faster to compute for very large numbers, as we recall that addition and subtraction are O(n), whereas multiplication is always slower. The algorithm seen above can be generalized to n-digit numbers, and has an asymptotic runtime of less than O(n²). If this Karatsuba multiplication is recursively applied, there will be a turning point where the addition and subtraction overhead will become relatively expensive, at which point elementary-school multiplication should be used. Mathematical software uses a hybrid of these multiplication methods to compute the product in the fastest way possible.