So basically what we're doing, I'm sorry, the D sub zero and E sub zero. First thing we'll do, is multiply together the D sub one and E sub one.
Algorithm divide and conquer algorithm plus#
So we're going to be going from b sub l, b sub l plus one, b sub l plus two, etc. And b sub l is the coefficient in B, that we're interested in. So A and B are our arrays of coefficients, n is the size of the problem, a sub l is the first coefficient that we're interested in.
And our base case is that if n of size 1, we're going to multiply together A at a sub l, plus B at b sub l. So we're going to compute a resulting array, from 0 to 2n-2, so is all the results coefficients. Now, how long's this take to run? We're going to look at that in a moment. If we sum this all together, we get 4 x to the 6th, plus 11 x to the 5th, plus 20 x to the 4th, plus 30 x cubed, plus 20 x squared, plus 11x plus 4. Now we've done all four of those computations, AB is just D1 E1, 4 x squared + 11x + 6 times x to the 4th, plus the sum of D1 E0 and D0 E1, times x squared, plus finally D0 E0. Similarly, we calculate D1 E0, D0 E1, and D0 E0. So multiplying together, 4x + 3, times x plus 2, gives us 4 x squared + 11x + 6. X cubed plus 2 x squared just becomes x plus 2. Similarly, we're going to break up the top half of B of x.
And we're going to break up A of x into the top half, 4x plus 3, and the bottom half, 2x plus 1. So we have, n is 4, so we have degree three polynomials. Plus, then, in order to take the results and do our addition that's going to take order n time. Each of them takes time T of n over 2 ecause the problem is broken in half. Why 4? 4, because we're breaking into 4 subproblems. Its run time is T of n, equals 4 T of n over 2. So it gives us a divide and conquer problem. And so, now we can go ahead and use a recursive solution to solve this problem. Those are all polynomials of degree n over 2. The key here is that, we now just need to calculate D1 E1, D1 E0, D0 E1, and D0 E0. And that then yields for terms, D sub 1 E sub 1 times x sub n, D sub 1 E sub 0 + D sub 0 E sub 1 times x sub n/2 + D sub 0 E sub 0. When we do our multiplication, then, we just multiply together D 1, x sub n over 2 plus D 0 and E 1 times x sub n over 2 plus E 0. Again, where E sub 1 of x is the high terms, E sub 0 of x is the low terms.
So we break that into E sub 1 of x, and E sub 0 of x. So we have two parallel sub polynomials, the high and the low. D sub 1 of x, since we've pulled out x sub n over 2 terms, it's lowest term is actually, just a sub n over 2. So A(x) is going to be D sub one of X ,times x sub n over 2, plus d sub 0 of x, the bottom half. The idea is, we're going to take our long polynomial and we're going to break it in two parts. So let's look at a naive divide and conquer algorithm, to solve polynomial multiplication problem.
0 kommentar(er)
