The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
Karatsuba Multiplication
Loading...
Del curso dictado por Stanford University
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
2516 calificaciones
De la lección
Week 1
Introduction; "big-oh" notation and asymptotic analysis.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
