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.