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. The sequence of steps will strike you as very mysterious. It'll seem like I'm pulling a rabbit out of the hat, and the rest of this video will develop more systematically what exactly this Karatsuba multiplication method is, and why it works. But what I want you to appreciate already on this slide is that the algorithm design space is far richer than you might expect. There's this dazzling array of options for how to actually solve problems like integer multiplication. Let me begin by introducing some notation for the first and second halves of the input numbers x and y. So the first half of x, that is 56- we're going to regard as a number in its own right called a. Similarly b will be 78, c will be 12, and d will be 34. 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. 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. Multiplying the expanded versions of x and y, we get an expression with three terms. One shifted by n, 10 raised to the power n, and the coefficient there is a times c. We have a term that's shifted by 10 to the n over 2, and that has a coefficient of ad and also plus bc. And bringing up the rear, we have the term b times d. We're going to be referring to this expression a number of times, so let me both circle it and just give it a shorthand. We're going to call this expression star. 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. 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. 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. So that's pretty cool, and this kind of showcases the ingenuity which bears fruit even in the simplest imageable computational problems. Now you should still be asking the question Yeah is crazy algorthim really faster than the grade school algorithm we learn in 3rd grade? Totally not obvious, we will answer that question a few lecture hense and we'll answer it in a special case of an entire toolbox I'll provide you with to analyze the running time of so called divide and conquer algorithms like Karatsuba multiplication, so stay tuned.
