CODEWITHSUNDEEP
algorithmrecursionlanguage-agnosticdivide-and-conquer
rw435
rw435

Reputation: 315

Naive Divide-and-Conquer Approach to Polynomial Multiplication

Given two polynomials A(x) = a0 + a1x + a2x2 + ... + an-1xn-1, and B(x), defined similarly with coefficients b0, b1 ... bn-1, we seek A(x) * B(x).

I'm examining a simple divide and conquer algorithm as a preface to learning Karatsuba's algorithm, and I understand the basic principle, namely:

Defining A(x) = M0(x) + M1(x)xn/2, where M1(x) = an-1xn/2-1 + an-2xn/2-2 + ... + an/2 (i.e. upper half coefficients) and M0(x) = an/2-1xn/2-1 + an/2-2xn/2-2 + ... + a0 (i.e. lower half coefficients), and B(x) = N0(x) + N1(x)xn/2, with N0(x) and N1(x) defined in a similar fashion to M0(x) and M1(x), respectively. Then we can rewrite A(x) * B(x) as (M1N1)xn + (M1N0 + M0N1)xn/2 + M0N0.

However, I'm have a little trouble understanding the "conquer" step in the pseudocode provided:

Function PolyMult(A, B, n, a, b)
    R = array[0 ... 2n - 1];
    if n = 1:
        R[0] = A[a] * B[b]; return R;
    R[0 ... n - 2] = PolyMult(A, B, n/2, a, b);
    R[n ... 2n - 2] = PolyMult(A, B, n/2, a + n/2, b + n/2);
    MN = PolyMult(A, B, n/2, a, b + n/2);
    NM = PolyMult(A, B, n/2, a + n/2, b);
    R[n/2 ... n + n /2 - 2] += MN + NM;
    return R;
End Function

Specifically, I'm unsure as to why the first n - 1 and last n - 1 terms of the resultant array can be directly initialized, whereas the middle n - 1 terms need to be computed with addition assignment. Could someone elaborate on this aspect of the algorithm?

In general, I believe I am missing some important intuition in regards to recursion or divide and conquer (seemingly both). What are important general paradigms when attempting to implement a recursive divide and conquer solution?

Upvotes: 3

Views: 1503

Answers (1)

aka.nice
aka.nice

Reputation: 9372

Hints: what is the (maximum) degree of polynomials M0,M1,N0,N1?

n/2-1

What is the (maximum) degree of each product M0*N0 M1*N1 M0*N1 m1*N0?

n - 2

Now the degree of M1*N1*x^n ?

2*n - 2

And what is the value of coefficients of M1*N1*x^n from degree 0 to n - 2 ?

0

So do they overlap with the coefficients of M0*N0 ?

no

Now the last part (M0*N1+M1*N0)*x^(n/2), what is the valuation and degree?

n/2 and n/2 + n - 2 respectively

Do these overlap partially with M0*N0 and M1*N1*x^n ?

yes

So you have to use += for the last part

Upvotes: 1

Related Questions