Multiply polynomials

Question

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 Θ(n^(lg3). 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{ length(P), length(Q)} and we let m=ceil(n/2).

Then P=A x^m+B, where A=p_m+p_(m+1) x+ .... + p_(n-1) x^(n-1-m), B=p_0+p_1 x+ ...s+p_(m-1)x^(m-1) and Q=Cx^m+D, where C=q_m+q_(m+1) x+ ...+ q_(n-1) x^(n-1-m) and D=q_0+q_1 x+ ... + q_(n-1) x^(n-1)=q_0+q_1 x+ ... + 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 (link)

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 a,b,c,d are vectors, right?

Could you explain me why we make these recursive calls:

 tmp1=Algorithm(a+b,c+d)
 tmp2=Algorithm(a,c)
 tmp3=Algorithm(b,d)

I haven't really understood it... Also, how could we elsewhise shift a number to the left by a specific number of digits?

It should be mentioned somewhere that this algorithm is known as Karatsuba multiplication. — Lutz Lehmann
I'm voting to close this question as off-topic because it appears to be about math in general, not about programming. — TylerH

Asad Saeeduddin Asad Saeeduddin · Accepted Answer · 2015-06-09T22:13:13

Let's say you have two polynomials of maximum degree n, and you want to find the polynomial that is their product. Furthermore, you want to use a divide and conquer approach in order to optimize your solution.

How can we break the problem of multiplying two polynomials of degree n into analogous subproblems that involve less work? Well, we can turn them into a larger number of smaller polynomials. Given a polynomial of degree n, you can turn it into two smaller polynomials by following the reasoning below.

Given a polynomial P of degree n as follows:

enter image description here

Let:

enter image description here

We can factor out x^m from the "second half" of the polynomial. Or, continuing with our notation:

enter image description here

Or, if we let:

enter image description here

We have:

enter image description here

We've managed to express our polynomial of degree n in terms of two smaller polynomials, of degree m. Why is this useful?

Well, let us return to the original problem for a second. Recalling that we are given two polynomials to find the product of, let us split them as seen above. Let A, B denote the first and second "halves" of the first polynomial P, and let C, D denote the two halves of the second polynomial Q.*

Rearranging the product of P and Q:

enter image description here

Awesome! We've managed to express the product of our two large polynomials as a sum of three products of smaller...well...polynomials. That's not so great, is it. So when you want to compute AC, or BD, or (A+C)(B+D), you have the same problem you started out with: "take these two polynomials and multiply them".

But this is the very problem we are solving! Assuming our method is properly implemented to return (the coefficient vector of) the product of two polynomials, we can just pass it the three products we need to compute. This is why you have three recursive calls to Algorithm, for each of A, C, B, D and A+B, C+D.

Finally, regarding the left shift: I am fairly certain this is referring to leftward shifting within the coefficient vector, and not bitwise left shift. Since the index within the coefficient vector represents the power of x of the term the coefficient applies to, we can represent multiplication of some polynomial by a given power of x by shifting the terms in its coefficient vector leftwards by a corresponding amount.

*Note that both polynomials are treated as having the exact same degree, i.e. the degree of the higher order polynomial, among P and Q. All the missing terms in the other polynomial have coefficient zero.

Multiply polynomials

2 Answers