1.4「Stanford Algorithms」Karatsub

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.

如果您想将两个整数相乘，是否有比我们三年级中学到的更好的方法？为了给您这个问题的最终答案，您将不得不等到我为您提供一个用于分析分而治之算法的工具箱后再进行一些演讲。

在本讲座中，我想做的是使您确信算法设计空间非常丰富。

当然，还有其他有趣的方法可以将两个整数相乘，这超出了我们三年级所学的内容。

本次演讲的重点是所谓的唐津乘法。

让我通过一个具体的例子向您介绍唐津乘法。

我将采用上一堂课学习的同一对整数，即1、2、3、4、5、6、7、8。

我将执行一系列步骤以生成他们的产品。

但是，这一系列步骤看起来与我们在小学算法中所采取的步骤非常不同，但是我们将得到完全相同的答案。

步骤的顺序会让您感到非常神秘。

好像我要把兔子从帽子里摘下来一样，该视频的其余部分将更系统地开发此Karatsuba乘法方法的确切含义以及其工作原理。

但是我希望您在这张幻灯片上已经意识到，算法设计空间比您预期的要丰富得多。

对于如何真正解决整数乘法之类的问题，有一系列令人眼花azz乱的选项。

首先，让我为输入数字x和y的前半部分和后半部分引入一些符号。

因此，x的前半部分即56，我们将自己视为一个称为a的数字。

类似地，b为78，c为12，d为34。

我将执行仅涉及这些两位数字abc和d的一系列操作。

然后，经过几次这样的运算，我将以一种神奇的方式将所有项收集在一起，得出x和y的乘积。

首先，让我计算乘以c的乘积，以及乘以b乘以d的乘积。

我将跳过基本计算，只告诉您答案。

因此，您可以验证c等于672，而b等于d等于2652。

接下来，我将做一些更加难以理解的事情。

我将取a和b的总和。

我将取c和d之和。

然后，我将计算这两个和的乘积。

归结为计算134和46的乘积。

主要在6164。

现在，我将从计算结果中减去前两个乘积。

也就是说，我要录入6164。

减去2652，再减去672。

您应该检查一下，如果从第3步的结果中减去前2步的结果，则得到2840。

现在，我声称我可以采用步骤1、2和4的结果，并将它们组合成超简单的方式来产生X和Y的乘积。

这是我的方法。

我从第一个产品AC开始。

我用四个零填充。

我采用第二步的结果，并且根本不使用零填充它。

然后我执行第四步的结果，并用两个零填充。

如果我们将这三个量加起来，则从右到左。

我们得到二，五，六。

六，零，零，七。

如果您返回上一课，您会注意到这与出色算法的输出完全相同，实际上这是1、2，the，3、4和5、6、7、8的乘积。

因此，让我重申一下，您不应对我刚才所做的计算有任何直觉，您也不应了解这张幻灯片上的内容。

相反，我希望您感到困惑和阴谋诡计，但是，更重要的是，我希望您理解三年级算法并不是城里唯一的游戏。

与您小时候学到的算法相比，根本上有各种不同的算法可用于乘以整数。

一旦意识到这一点，一旦意识到算法的空间有多丰富，就必须怀疑我们能做得比该三年级算法更好吗？实际上，该算法是否已经比三年级算法做得更好？在我解释成熟的唐津乘法之前，让我开始解释一个更简单，更直接的递归方法。

进行整数乘法。

现在，我假设您有一定的编程背景。

特别是，您知道什么是递归算法。

即，以较小的输入将自己作为子例程调用的算法。

那么，您将如何递归地解决整数乘法问题呢？那么输入是两位数。

每两个数字。

每个都有两位数字。

因此，要递归地调用该算法，您需要执行较小尺寸，较少数字的输入。

好吧，我们已经在上一张幻灯片的计算中做到了。

例如，数字5678我们将数字的前半部分本身视为数字56，类似地将其视为78。

通常，给定一个带有n位数字的数字x。

In可以用两个数字n上的n表示分解。

即，A的前半部分数字适当地移位。

那乘以十的幂，即n乘以2。

加上数字的后半部分b。

在我们的示例中，我们等于56，78为b。

N是4，所以10到2上的n是100，然后c和d是12和34。

我接下来要做的是阐明相关的递归调用。

为此，让我们看乘积x，乘以y。

用这些较小的数字a，b，c和d表示它，并进行基本计算。

乘以x和y的扩展版本，我们得到一个包含三项的表达式。

将n移1，将n乘幂10，系数乘以c。

我们有一个术语，将10移至2上的n，并且具有ad系数和bc系数。

提起后部，我们有项b乘以d。

我们将多次引用此表达式，所以让我都圈一下并给它一个简写。

我们将这个表情称为星号。

为了简单起见，我要介绍的一个细节是，我假设n是偶数整数。

现在，如果n是一个奇数整数，则可以将这种完全相同的递归方法应用于整数乘法。

以简单的方式，因此，如果n为9，则可以将这些输入数字之一分解为前五位和后四位，然后以完全相同的方式进行操作。

现在，如果仅考虑基本代数的乘积，便可以看成星的意思，它表明了将两个数相乘的递归方法。

如果我们关心X和Y的乘积，为什么不计算这个表示星，它只涉及较小数的乘积A，B，C和D。

您会注意到，盯着表情明星，有4种相关产品，每一种都涉及一对较小的数字。

即AC，AD，BC和BD。

因此，为什么不递归计算这四个产品中的每一个。

毕竟，输入将较小。

然后，一旦我们的四个递归调用返回答案，我们就可以用明显的方式来表达其余的表达星。

我们只用末尾n个零填充一次c。

我们使用年级算法将a，d和bc相加，并用两个零上的n填充结果，然后再次使用年级加法和算法对这些收益求和。

因此，我已经掩盖了将这个想法变成一种真正的递归算法所需要的一个细节缺失，那就是指定一个基本案例。

我希望大家都知道，递归算法需要一个基本案例。

如果输入足够小，则只需立即计算答案，而无需进一步递归。

当然，递归算法需要一个基本案例，因此它们不会在剩余时间内一直调用自己。

因此，对于整数乘法，这是基本情况，如果给定两个数字，每个数字只有一位。

然后，您只需将它们乘以一个基本运算并返回结果。

因此，我希望目前很清楚的是，确实有一种递归方法可以解决整数乘法算法，从而使该算法看起来与您三年级学习的算法完全不同，但是您仍然可以很轻松地编写代码用您最喜欢的编程语言。

现在，您不应该有任何直觉，这是一个好主意还是一个完全的“疯子”主意。

该算法比小学算法快还是慢？您只需要等待找出该问题的答案即可。

现在，让我们改进此递归算法，以形成成熟的Karatsuba乘法算法。

为了解释唐津乘法的优化，让我们回想一下上一张幻灯片中我们称之为星号的表达式。

因此，这只是用较小的数字a，b，c和d表示x和y的乘积。

在这种简单的递归算法中，我们进行了四个递归调用，以计算似乎有价值的四个乘积，以计算表达式星。

但是，如果考虑一下，我们实际上只关心三个恒星，三个相关系数。

我们关心数字ad和bc。

本身不是，而是在我们关心它们的总和时，AD和BC。

因此，这引发了一个问题，如果我们只关心3个数量，那么能否仅用3个而不是4个递归调用就可以摆脱。

事实证明，我们可以做到，这就是我们的方法。

我们递归地计算出第一个系数ac和第三个系数bd。

接下来，我们将递归计算加号b与c加d的乘积，而不是递归地计算ad或bc。

如果我们将其扩展，这与计算ac加ad加bc加bd相同。

现在，这是唐津乘法的关键发现，它的确是一种技巧，可以追溯到19世纪初的数学家高斯。

让我们看一下我们在步骤3中计算出的数量并从中减去。

我们已经在步骤1和2中计算出的两个量。

减去步骤1的结果将取消ac项。

减去第二步的结果，就消除了bd项，剩下的就是我们一直想要的东西，即中间系数ad加b c。

现在，与上一张幻灯片相同，我们有一个简单的递归算法，它进行四个递归调用，然后以明显的方式组合它们。

在这里，我们有一个简单的递归算法，该算法仅进行三个递归调用。

除递归调用外，还可以进行很好的加减法运算。

因此，您需要在三个递归计算的乘积之间进行这种特殊的区别，然后像以前一样进行平移，零填充以及最后的总和。

因此，这很酷，这种展示方式即使在最简单的可成像计算问题中也能发挥成果。

现在您仍然应该问一个问题，是不是真的比我们三年级学习的小学算法更快呢？完全不明显，我们将在几个讲义上回答这个问题，我们将在整个工具箱的特殊情况下回答这个问题，我将为您提供该工具箱，以分析所谓的分治法（例如Karatsuba乘法）的运行时间，因此敬请关注。