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.

Â