![]() And the number of problems that we have, 1 of them at level 0, 3 instead of 4 at level 1, 3 to the i. So at log base 2 of n level, all the problems are of size 1. At level i, our problems are of size n over 2 to the i, just like they were in the other divide and conquer problem. When we break it down, we have three problems of size n over 2, again, rather than 4. That extra multiplication makes a big difference. And also the same way we'd do it if we did a straight naive problem, okay? So we get the same result, three multiplications instead of four multiplications. Which is the exact same result we got doing it in the more naive divide and conquer. We just end up with 4 x to the sixth + 11 x to the fifth + 20 x to the fourth + 3 x cubed + 20 x squared + 11x + 4. If we simplify that middle portion, and all of it. (24x squared + 52x + 24), okay? Add that in the second term. And then, our final result for A(x) B(x) is D1E1 times x to the fourth +, now what do we do here? We take that (D1 + D0) (E1 + E0). So, so far, how many multiplications have we done? Three. And then we multiply those two polynomials together, yielding 24 x squared + 52x + 24. Instead we're going to sum together D1 and D0. But now we won't compute D1 E0 and D0 E1. We're going to compute D0 E0, again just like we did before. We're going to compute D1 E1, again, just like we did before. The key is what we're going to actually do in terms of the subproblems. We're going to go ahead and pull out D1 and D0 like we did before. We're going to have 4 x cubed + 3 x squared + 2x +1. Why does this matter? Well, why it matters is because we are reducing the number of problems at each level. But the key is, when we have three multiplications instead of four. And then we need to multiply together (a1 + a0) and (b1 + b0). We need to compute a0 b0, even again, though we use it only twice. We need to compute a1 b1, even though we use it twice. The key here though, is how many multiplications are needed. Which is exactly what's there to begin with. And then he subtracted out the a1b1 and the a0b0, so he's left with a1b0 + a0b1. So he added together, (a1 + a0) (b1 + b0). So basically what he did is he re-wrote that inner term, a1b0 + a0b1 as something slightly more complicated. Karatsuba's insight was that there was a way to re-write C(x), so that you only needed to do three multiplications. This is how we did the divide and conquer in fact in our last video. We need to multiply a1 times b0, a0 times b1, and a0 times b0. ![]() So we'll notice here we need four multiplications. And B(x) = b1x + b0, and then C(x) is, what would match in there? a1b1x squared + (a1b0 + a0b1)x + a0b0. So if we look at A(x) it's just a very simple polynomial, a1x + a0. Karatsuba, a grad student, heard the problem, went away, came back a week later with a solution. So there was a lower bound of n squared, doing polynomial multiplication. And Komolgorov theorized that n squared was the best that one could do. So he was a graduate student of Komolgorov, a famous Russian mathematician. This problem, this approach was invented by Karatsuba in the early 1960s. ![]() If we cant solve problem, divide it into parts, and solve one part at a time.In this video we'll look at creating a faster divide and conquer algorithm in order to solve the polynomial multiplication problem. The moral for problem solvers is different. The brothers decided that they should stay together and succed together. Then the old man untied the bundle and broke thstick ine by one. They all tried, but no one could break the bundle. So he gathered them together and shows them seven stiks that he had tied together abd told them that anyone who could break the bundle would inherit everything. He was afraid that when he died, his land and his possesions would be divided among his seven sons, and that they would quarrel with one another. There was an old man who was a rich farmer and seven sons.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |