0:02

If you want to multiply two integers, is there a better method than the one we

learned back in third grade? To give you the final answer to this

question, you'll have to wait until I provide you with a toolbox for analyzing

Divide and Conquer algorithm a few lectures hence.

What I want to do in this lecture is convince you that the algorithm design

space is surprisingly rich. There are certainly other interesting

methods of multiplying two integers beyond what we learned in third grade.

And the highlight of this lecture will be something called Karatsuba

multiplication. Let me introduce you to Karatsuba

multiplication through a concrete example.

I am going to take the same pair of integers we studied last lecture, 1, 2,

3, 4, 5, 6, 7, 8. I am going to execute a sequence of steps

resulting in their products. But, that sequence of steps is going to

look very different than the one we undertook during the grade school

algorithm, yet we'll arrive at exactly the same answer.

1:53

I'm going to do a sequence of operations involving only these double digit numbers

a b c and d. And then after a few such operations I

will collect all of the terms together in a magical way resulting in the product of

x and y. First let me compute the product of a

times c and also the product of b times d.

I'm going to skip the elementary calculations, and just tell you the

answer. So you can verify that a times c is 672,

where as b times d is 2652. Next I'm going to do something even still

more inscrutable. I'm going to take the sum of a and b.

I'm going to take the sum of c and d. And then I'm going to compute the product

of those two sums. That boils down to computing the product

of 134 and 46. Mainly at 6164.

Now, I'm going to subtract our first two products from the results of this

computation. That is, I'm going to take 6164.

Subtract 2652, and subtract 672. You should check that if you subtract the

results of the first 2 steps from the result of the 3rd step, you get 2840.

Now, I claim that I can take the results of step 1, 2 and 4 and combine them into

super simple way to produce the product of X and Y.

Here's how I do it. I start with the first product, ac.

And I pad it with four zeros. I take the results of the second step,

and I don't pad it with any zeros at all. And I take the result of the fourth step,

and I pad it with two zeros. If we add up these three quantities, from

right to left. We get two, five, six.

Six, zero, zero, seven. If you go back to the previous lecture

you'll note that this is exactly the same output as the great school algorithm,

that this is in fact the product of one, two, the, three, four and five, six,

seven, eight. So let me reiterate that you should not

have any intuitions for the computations I just did, you should not understand

what just went down on this slide. Rather I hope you feel some mixture of

bafflement and intrigue but, more the point I hope you appreciate that the

third grade algorithm is not the only game in town.

There's fundamentally different algorithms for multiplying integers than

what you learned as a kid. Once you realize that, once you realize

how rich the space of algorithms is, you have to wonder Can we do better than that

third grade algorithm? In fact, does this algorithm already do

better that the third grade algorithm? Before I explain full-blown Karatsuba

multiplication, let me begin by explaining a simpler, more

straightforward recursive approach. To integer multiplication.

Now, I am assuming you have a bit of programming background.

In particular, that you know what recursive algorithms are.

That is, algorithms which invoke themselves as a subroutine with a smaller

input. So, how might you approach the integer

multiplication problem recursively? Well the input are two digits.

Each two numbers. Each has two digits.

So to call the algorithm recursively you need to perform inputs that have smaller

size, less digits. Well, we already were doing that in the

computations on the previous slide. For example the number 5678 we treated

the first half of digits as 56 as a number in its own right and similarly 78.

5:33

In general, given a number x with n digits.

In can be expressed decomposed, in terms of two, n over two digit numbers.

Namely as A, the first half of the digits shifted appropriately.

That is multiplied by ten raised to the power, n over two.

Plus the second half of the digits b. In our example, we had a equal to 56, 78

was b. N was 4, so 10 to the n over 2 was 100,

and then c and d were 12 and 34. What I want to do next is illuminate the

relevant recursive calls. To do that, let's look at the product, x

times y. Express it in terms of these smaller

numbers, a, b, c, and d, and do an elementary computation.

6:52

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.

10:31

The first coefficient a c and the third coefficient b d, we compute exactly as

before, recursively. Next, rather than recursively computing a

d or b c, we're going to recursively compute the product of a plus b and c

plus d. If we expand this out, this is the same

thing as computing ac plus ad plus bc plus bd.

Now, here is the key observation in Karatsuba Multiplication, and it's really

a trick that goes back to the early 19th Century mathematician, Gauss.

Let's look at the quantity we computed in step 3 and subtract from it.

The two quantities that we already computed in steps one and two.

11:17

Subtracting out the result of step one cancels the a c term.

Subtracting out the result of step two, cancels out the bd term, leaving us with

exactly what we wanted all along, the middle coefficient a d plus b c.

And now in the same that on the previous slide we have a straightforward recursive

algorithm making four recursive calls, and then combining them in the obvious

way. Here we have a straightforward recursive

algorithm that makes only three recursive calls.

And on top of the recursive calls does just great school addition and

subtraction. So you do this particular difference

between the three recursively computed products and then you do the shifts, the

padding by zeros, and the final sum as before.