1.3「Stanford Algorithms」Integer

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.

有时候，当您还是个孩子的时候，比如说三年级左右，您学习了一种将两个数字相乘的算法。

也许您的三年级老师没有这么称呼，也许那不是您的想法。

但是您了解了一套明确定义的规则，用于将输入（即两个数字）转换为输出（即它们的乘积）。

因此，这是用于解决计算问题的算法。

让我们暂停一下，并保持精确。

本课程中的许多讲座将遵循一种模式。

我们将定义一个计算问题。

我们先说输入是什么，然后再说期望的输出是什么。

然后，我们将继续给出解决方案，给出一种将输入转换为输出的算法。

当出现整数乘法问题时，输入的只是两个n位数字。

因此，两个输入整数x和y的长度n可以是任何长度，但是出于动机，您可能想将n视为数千个甚至更大的整数，也许我们正在实现某种加密应用程序，该应用程序具有操纵非常大的数字。

我们还需要解释这个简单问题中所需的输出是x乘以y。

如此迅速地离题，回到了三年级，我正在学习整数乘法算法。

我的笔法为C，从那以后我的笔迹就没有改善。

课程结束时很多人告诉我。

他们喜欢将其视为一种后天的味觉，但如果您不耐烦，请注意，这些幻灯片有打字版本。

如果您不想花时间破译笔迹，我鼓励您在讲课时使用它。

回到整数乘法问题，现在已经精确地指定了问题，即输入，所需的输出。

我们将继续讨论解决该问题的算法，即与您三年级学习的算法相同的算法。

我们评估该算法性能的方法是通过其执行的基本操作数量。

现在，让我们考虑一下基本操作，即简单地将两个个位数相加或将两个个位数相乘。

然后，我们将继续计算由三年级算法执行的这些基本操作的数量。

作为输入中数字n的函数。

这是您在三年级中学到的整数乘法算法，在一个具体示例中进行了说明。

假设数字1、2、3、4和5、6、7、8

在快速浏览此算法时，让我提醒您，我们的重点应该放在该算法执行的基本运算上。

根据输入数字的长度。

在此特定示例中，它是四位数长。

因此，您会记得，我们只需为第二个数字的每个数字计算一个部分乘积。

因此，我们首先乘以最高数字5、6、7、8的4倍。

因此，您知道，4乘8是32，2乘以3，4乘7是28，用3乘以31，记下1，乘以3，依此类推。

当我们做下一个部分乘积时，我们有效地进行了移位，在末尾加了0，然后我们做的完全相同。

最后两个部分产品依此类推。

[声音]最后，我们将所有内容加起来。

[声音]，您可能在三年级时就意识到，这种算法就是我们所说的正确算法。

也就是说，无论以x和y为整数，如果执行此过程，都将使用此算法。

并且您的所有中间计算都已正确完成。

然后，该算法最终将以两个输入数字的乘积x x y终止。

您永远不会得到错误的答案。

您将始终获得实际的产品。

好吧，您可能根本没有考虑过执行此算法以得出终止结论所需的时间。

那是完成之前所需的基本运算，个位数的加法或乘法的数量。

因此，现在让我们快速地根据输入长度n非正式地分析所需的操作数。

让我们从第一个部分产品开始，第一行。

我们如何计算这个数字22,712？好吧，我们将数字5、6、7和8分别乘以4倍。

这就是基本操作。

最高位的每个数字一位，此外，我们还必须进行这些进位。

所以这些是一些额外的补充。

但是无论如何，这最多是第一个数字中位数的两倍。

至多两个结束基本操作以形成此第一部分产品。

而且，如果您考虑一下，第一个部分产品也没什么特别的。

同一个论点说，我们最多需要2个n运算来形成每个有n的部分乘积，第二个数的每个数字一个。

好吧，如果我们最多需要两个n次运算来计算每个部分乘积，而我们有n个部分乘积。

这总共是最多两个n平方运算，以形成所有这些蓝色数字以及所有部分乘积。

现在我们还没有完成。

我们仍然必须将所有这些加起来以获得最终答案，在本例中为7,006,652。

这是最后的添加，需要相当数量的操作。

粗略地说，最多只能说两个n平方。

因此，我要您重点关注的结果是更高的水平，即当我们考虑输入数字越来越大时。

这是输入数字中n位数字的函数。

成绩学校乘法算法执行的运算数量像某些常数一样增长。

大约有4个说乘以n的平方。

这就是输入长度n的平方。

例如，如果将输入的大小加倍，则将获得的两个整数中的每个整数的位数加倍。

然后，使用该算法必须执行的操作数必须增加四倍。

同样，如果将输入长度增加三倍，则要执行的操作数将增加16倍，依此类推。

现在，取决于您是三年级学生的类型。

您可能会接受此过程，因为它是将两个数字相乘以形成其乘积的唯一或至少是最佳方法。

现在，如果您想成为一名认真的算法设计师。

那种顺从的团圆是您将必须成长的一种品质。

关于算法设计和分析的早期且极为重要的教科书是Aho，Hopcroft和Ullman撰写的。

现在大约40岁了。

以下是我绝对喜欢的报价。

因此，在遍历教科书中涵盖的许多算法设计范例之后。

他们说，对于优秀的算法设计人员来说，以下可能是最重要的原则是拒绝满足。

我认为这是值得评论的地方。

我可能会更简洁地总结一下。

作为算法设计者，您应该采用问题作为口头禅，我们能做得更好吗？当您面对计算问题的幼稚或直接解决方案时，此问题特别合适。

例如，用于整数乘法的三年级算法。

您也许在三年级没有问过自己的问题是，我们能做得比直接乘法算法好吗？现在是答案的时候了。