- #1

evinda

Gold Member

MHB

- 3,836

- 0

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