One detail I'm glossing over for simplicity, is that I've assumed that n

is an even integer. Now, if n is an odd integer, you can

apply this exact same recursive approach to integer multiplication.

In the straightforward way, so if n was 9 then you would decompose one of these

input numbers into say the first five digits and the later four digits and you

would proceed in exactly the same way. Now the point of the expression star is

if we look at it despite being the product of just elementary algebra, it

suggests a recursive approach to multiplying two numbers.

If we care about the product Of X and Y, why not, instead, compute this expression

star, which involves only the products of smaller numbers, A, B, C and D.

You'll notice, staring at the expression star, there are 4 relevant products, each

involving a pair of these smaller numbers.

Namely AC, AD, BC, and BD . So why not compute each of those four

products recursively. After all, the inputs will be smaller.

And then once our four recursive calls come back to us with the answer, we can

formulate the rest of expression star in the obvious way.

We just pad a times c with n zeros at the end.

We add up a, d, and bc, using the grade school algorithm, and pad the result with

n over two zeros, and then we just sum up these returns, again using the grade

school addition, and algorithm. So the one detail missing, that I've

glossed over, required to turn this idea into a bonafide recursive algorithm,

would be to specify a base case. As I hope you all know, recursive

algorithms need a base case. If the input is sufficiently small, then

you just immediately compute the answer rather than recursing further.

Of course, recursive algorithms need a base case so they don't keep calling

themselves til the rest of time. So for integer multiplication, which the

base case, well, if you're given two numbers that have the just one digit

each. Then you just multiply them in one basic

operation and return the result. So, what I hope is clear at the moment is

that there is indeed a recursive approach to solving the integer multiplication

algorithm resulting in an algorithm which looks quite different than the one you

learned in third grade, but which nevertheless you could code up quite

easily in your favorite programming language.

Now, what you shouldn't have any intuition about is whether or not this is

a good idea or a completely crackpot idea.

Is this algorithm faster or slower than the grade school algorithm?

You'll just have to wait to find out the answer to that question.

Let's now refine this recursive algorithm, resulting in the full-blown

Karatsuba multiplication algorithm. To explain the optimization behind

Karatsuba multiplication, let's recall the expression we were calling star on

the previous slide. So, this just expressed the product of x

and y in terms of the smaller numbers a, b, c, and d.

In this straight forward recursive algorithm we made four recursive calls to

compute the four products which seemed necessary to value, to compute the

expression star. But if you think about it, there's really

only three quantities in star that we care about, the three relevant

coefficients. We care about the numbers ad and bc.

Not per se, but only in as much as we care about their sum, AD plus BC.

So this motivates the question, if there's only 3 quantities that we care

about, can we get away with only 3 rather than 4 recursive calls.

It turns out that we can and here's how we do it.