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

[evinda]

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)
  
  
  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)
  

 

[Future Bruno]

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.