This problem, this approach was invented by Karatsuba in the early 1960s.

So he was a graduate student of Komolgorov,

a famous Russian mathematician.

And Komolgorov theorized that n squared was the best that one could do.

So there was a lower bound of n squared, doing polynomial multiplication.

Karatsuba, a grad student, heard the problem, went away,

came back a week later with a solution.

So let's look at what is involved.

So if we look at A(x) it's just a very simple polynomial, a1x + a0.

And B(x) = b1x + b0, and then C(x) is, what would match in there?

a1b1x squared + (a1b0 + a0b1)x + a0b0.

So we'll notice here we need four multiplications.

We need to multiply a1 times b1.

We need to multiply a1 times b0, a0 times b1, and a0 times b0.

This is how we did the divide and conquer in fact in our last video.

So we need four multiplications.

Karatsuba's insight was that there was a way to re-write C(x),

so that you only needed to do three multiplications.

So basically what he did is he re-wrote that inner term,

a1b0 + a0b1 as something slightly more complicated.

So he added together, (a1 + a0) (b1 + b0).

So (a1 + a0) (b1 + b0) is just a1b1 + a0b1 + a1b0 + a0b0.

And then he subtracted out the a1b1 and

the a0b0, so he's left with a1b0 + a0b1.

Which is exactly what's there to begin with.

The key here though, is how many multiplications are needed.

It only needs three multiplications.

We need to compute a1 b1, even though we use it twice.

We need to compute a0 b0, even again, though we use it only twice.

And then we need to multiply together (a1 + a0) and (b1 + b0).

So we do have some extra additions.

But the key is, when we have three multiplications instead of four.