Sometime when you were a kid, maybe say third grade or so, you learned an Algorithm for multiplying two numbers. Maybe your third grade teacher didn't call it that, maybe that's not how you thought about it. But you learned a well defined set of rules for transforming input, namely two numbers into an output, namely their product. So, that is an algorithm for solving a computational problem. Let's pause and be precise about it. Many of the lectures in this course will follow a pattern. We'll define a computational problem. We'll say what the input is, and then we'll say what the desired output is. Then we will proceed to giving a solution, to giving an algorithm that transforms the input to the output. When the integer multiplication problem, the input is just two, n-digit numbers. So the length, n, of the two input integers x and y could be anything, but for motivation you might want to think of n as large, in the thousands or even more, perhaps we're implementing some kind of cryptographic application which has to manipulate very large numbers. We also need to explain what is desired output in this simple problem it's simply the product x times y. So a quick digression so back in 3rd grade around the same I was learning the Integer Multiplication Algorithm. I got a C in penmanship and I don't think my handwriting has improved much since. Many people tell me by the end of the course. They think of it fondly as a sort of acquired taste, but if you're feeling impatient, please note there are typed versions of these slides. Which I encourage you to use as you go through the lectures, if you don't want to take the time deciphering the handwriting. Returning to the Integer Multiplication problem, having now specified the problem precisely, the input, the desired output. We'll move on to discussing an algorithm that solves it, namely, the same algorithm you learned in third grade. The way we will assess the performance of this algorithm is through the number of basic operations that it performs. And for the moment, let's think of a basic operation as simply adding two single-digit numbers together or multiplying two single digit numbers. We're going to then move on to counting the number of these basic operations performed by the third grade algorithm. As a function of the number n of digits in the input. Here's the integer multiplication algorithm that you learned back in third grade Illustrated on a concrete example. Let's take say the numbers 1, 2, 3, 4 and 5, 6, 7, 8. As we go through this algorithm quickly, let me remind you that our focus should be on the number of basic operations this algorithm performs. As a function of the length of the input numbers. Which, in this particular example, is four digits long. So as you'll recall, we just compute one partial product for each digit of the second number. So we start by just multiplying 4 times the upper number 5, 6, 7, 8. So, you know, 4 times 8 is 32, 2 carry to 3, 4 times 7 is 28, with the 3 that's 31, write down the 1, carry the 3, and so on. When we do the next partial product, we do a shift effectively, we add a 0 at the end, and then we just do exactly the same thing. And so on for the final two partial products. [SOUND] And finally, we just add everything up. [SOUND], what you probably realized back in third grade, is that this algorithm is what we would call correct. That is, no matter what integers x and y you start with If you carry out this procedure, this algorithm. And all of your intermediate computations are done properly. Then the algorithm will eventually terminate with the product, x times y, of the two input numbers. You're never going to get a wrong answer. You're always going to get the actual product. Well, you probably didn't think about was the amount of time needed to carry out this algorithm out to its conclusion to termination. That is the number of basic operations, additions or multiplications of single digit numbers needed before finishing. So let's now quickly give an informal analyses of the number of operations required as a function of the input length n. Let's begin with the first partial product, the top row. How did we compute this number 22,712? Well we multiplied 4 times each of the numbers 5, 6, 7 and 8. So that was for basic operations. One for each digit at the top number, plus we had to do these carries. So those were some extra additions. But in any case, this is at most twice times the number of digits in the first number. At most two end basic operations to form this first partial product. And if you think about it there's nothing special about the first partial product. The same argument says that we need at most 2 n operations to form each of the partial products of which there are again n, one for each digit of the second number. Well if we need at most two n operations to compute each partial product and we have n partial products. That's a total of at most two n squared operations to form all of these blue numbers, all of the partial products. Now we're not done at that point. We still have to add all of those up to get the final answer, in this case 7,006,652. And that's final addition requires a comparable number of operations. Roughly, another say two n squared, at most operations. So, the upshot, the high level point that I want you to focus on, is that as we think about the input numbers getting bigger and bigger. That is as a function of n the number of digits in the input numbers. The number of operations that the Grade-School Multiplication Algorithm performs, grows like some constant. Roughly 4 say times n squared. That is it's quadratic in the input length n. For example, if you double the size of the input, if you double the number of digits in each of the two integers that you're given. Then the number of operations you will have to perform using this algorithm has to go up by a factor of four. Similarly, if you quadruple the input length, the number of operations going, is going to go up by a factor of 16, and so on. Now, depending on what type of third grader you were. You might well of accepted this procedure as the unique or at least the optimal way of multiplying two numbers together to form their product. Now if you want to be a serious algorithm designer. That kind of obedient tumidity is a quality you're going to have to grow out of. And early and extremely important textbook on the design and analysis of algorithms was by Aho, Hopcroft, and Ullman. It's about 40 years old now. And there's the following quote, which I absolutely adore. So after iterating through a number of the algorithm design paradigms covered in the textbook. They say the following, perhaps the most important principle of all, for the good algorithm designer is to refuse to be content. And I think this is a spot on comment. I might summarize it a little bit more succinctly. As, as an algorithm designer you should adopt as your Mantra the question, can we do better? This question is particularly apropos when your'e faced with a naive or straight-forward solution to a computation problem. Like for example, the third grade algorithm for integer multiplication. The question you perhaps did not ask yourself in third grade was, can we do better than the straight forward multiplication algorithm? And now is the time for an answer.
