How to Multiply Two Polynomials Using Divide-and-Conquer Algorithms?

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Polynomials
In summary, the conversation discusses how to multiply two linear polynomials using only three multiplications and gives a divide-and-conquer algorithm for multiplying two polynomials of degree-bound $n$ that runs in time $\Theta(n^{\lg 3})$. The algorithm involves dividing the input polynomial coefficients into a high half and a low half and using recursive calls to calculate the product of the two half-size polynomials. The bitwise left shift operator can be used to shift a number to the left by a specific number of digits.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)
  • Show how to multiply two linear polynomials $ax+b$ and $cx+d$ using only three multiplications.
  • Give a divide-and-conquer algorithms for multiplying two polynomials of degree-bound $n$ that runs in time $\Theta(n^{\lg 3})$. The algorithm should divide the input polynomial coefficients into a high half and a low half.

  • $(ax+b)(cx+d)=ac x^2+((a+b)(c+d)-ac-bd)x+bd$
    $$$$
  • We let $p$ and $q$ be the vectors of coefficients of the first and second polynomial $P$ and $Q$, respectively.
    We assume that both of these vectors are of length $n=\max \{ \text{length}(P), \text{length}(Q) \}$ and we let $m=\lfloor \frac{n}{2} \rfloor$.
    Then $P=A x^m+B$, where $A=p_m+p_{m+1} x+ \dots + p_{n-1} x^{n-1-m}$, $B=p_0+p_1 x+ \dots+p_{m-1}x^{m-1}$ and $Q=Cx^m+D$, where $C=q_m+q_{m+1} x+ \dots+ q_{n-1} x^{n-1-m}$ and $D=q_0+q_1 x+ \dots+ q_{n-1} x^{n-1}=q_0+q_1 x+ \dots+ q_{m-1} x^{m-1}$.

    Using the previous result, it holds that $(Ax^m+B)(Cx^m+D)=AC x^{2m}+((A+B)(C+D)-AC-BD) x^m+BD (1)$.

    I found the following algorithm (http://www.eecis.udel.edu/~saunders/courses/621/99f/p17a/p17.pdf)

    Code:
    Algorithm(p,q){
       n=size(p)
       m=ceil(n/2)
       if n==1 return p*q
       else{
             a=p[m,n-1]
             b=p[0,m-1]
             c=q[m,n-1]
             d=q[0,m-1]
             tmp1=Algorithm(a+b,c+d)
             tmp2=Algorithm(a,c)
             tmp3=Algorithm(b,d)
       return tmp2<<n+(tmp1-tmp2-tmp3)<<m+tmp3

    So we suppose that [m] a,b,c,d [/m] are vectors, right?
    Could you explain me why we make these recursive calls:
    [m]
    tmp1=Algorithm(a+b,c+d)
    tmp2=Algorithm(a,c)
    tmp3=Algorithm(b,d)
    [/m]

    I haven't really understood it... Also, how could we elsewhise shift a number to the left by a specific number of digits? (Thinking)
 
Technology news on Phys.org
  • #2
Yes, a, b, c, and d are vectors of polynomial coefficients. The recursive calls are used to divide the input polynomials into their high and low halves. The idea is that if you multiply two half-size polynomials, you can use the result to calculate the product of the two full-size polynomials.To shift a number to the left by a specific number of digits, you can use the bitwise left shift operator (<<). This operator shifts the bits of the number to the left by the specified amount. For example, 3 << 2 would shift the number 3 to the left by 2 digits, resulting in 12.
 

FAQ: How to Multiply Two Polynomials Using Divide-and-Conquer Algorithms?

1. What is the definition of multiplying two polynomials?

Multiplying two polynomials is the process of multiplying each term in one polynomial by each term in the other polynomial, and then simplifying the resulting polynomial by combining like terms.

2. How do you multiply two polynomials with multiple variables?

To multiply two polynomials with multiple variables, you must use the distributive property and multiply each term in one polynomial by each term in the other polynomial. Then, combine like terms and simplify the resulting polynomial.

3. Can you explain the FOIL method for multiplying two binomials?

The FOIL method is a mnemonic device used to remember the steps for multiplying two binomials. It stands for First, Outer, Inner, Last. First, multiply the first terms in each binomial. Then, multiply the outer terms, followed by the inner terms. Lastly, multiply the last terms. Finally, combine like terms and simplify the resulting polynomial.

4. What is the difference between multiplying polynomials and multiplying monomials?

Multiplying monomials involves multiplying coefficients and adding exponents, while multiplying polynomials involves multiplying each term in one polynomial by each term in the other polynomial and combining like terms. Additionally, polynomials can have multiple variables, whereas monomials only have one variable.

5. Can you provide an example of multiplying two polynomials?

Yes, for example, to multiply (x+2)(x+3), we would use the FOIL method and get x^2+3x+2x+6. Combining like terms, the final result would be x^2+5x+6.

Similar threads

Replies
1
Views
743
Replies
1
Views
1K
Replies
5
Views
2K
Replies
1
Views
2K
Replies
27
Views
6K
Replies
17
Views
1K
Replies
9
Views
2K
Replies
1
Views
1K
Replies
5
Views
1K
Replies
10
Views
2K
Back
Top