Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have two polynomials of degree $d$. However, I do not have equations for them. I simply have $d + 1$ distinct points on each polynomial. How would I find the product of these polynomials without deriving an equation for them/finding their coefficients? I would want the product of these polynomials to be represented through $2d+1$ distinct points.

Example: Let $A(x)$ represent the first polynomial, let $B(x)$ represent the second, and $C(x)$ be the product of these polynomials, where $$A(x) = A\left(x_0\right), A\left(x_1\right), \ldots ,A\left(x_d\right)\\ B\left(x\right) = B\left(x_0\right), B\left(x_1\right), \ldots,B\left(x_d\right)\\ C\left(x\right) = B\left(x\right) A\left(x\right) $$

How would I find $C\left(x\right)$ without converting $A\left(x\right)$ and $B\left(x\right)$ into coefficient form? Why would this take $\mathcal{O}\left(n\right)$ time rather than $\mathcal{O}(n^2)$ time? (like multiplying in coefficient form does).

share|cite|improve this question
If degree of $A(x), B(x)$ is $d,$ then degree of $C(x)$ is at most $2d.$ You have to represent $C(x)$ using $2d+1$ points. – user2468 May 12 '12 at 18:12
You treat them like vector implementation (not matrices). You would have for polynomials of degree $n$, $n$ multiplications and $n-1$ addition for product. – Kirthi Raman May 12 '12 at 18:25
up vote 3 down vote accepted

You can not recover $C(x)$ from values at $d+1$ points.As in your previous question (couple of hours ago), you need $2d+1$ points to fully characterize a degree $2d$ polynomial.

Let $A(x)$ and $B(x)$ be degree $d$ polynomials. Assume we know the values of $A(x)$ and $B(x)$ at $2d+1$ distinct points: $$\{ A(x_1), A(x_2), \ldots, A(x_{2d+1}) \},\\ \{ B(x_1), B(x_2), \ldots, B(x_{2d+1}) \}.$$ To find $C(x) = A(x) B(x),$ use the fact that $C(x_i) = A(x_i) B(x_i)$ for any $x_i,$ and compute the following pointwise product: $$\{ A(x_1)B(x_1), A(x_2)B(x_2), \ldots, A(x_{2d+1})B(x_{2d+1}) \}.\tag{1} $$ You can easily interpolate $C(x)$ from $(1).$ Computing $(1)$ requires $\mathcal O(d)$ operations. Interpolating $C(x)$ from $(1)$ will cost more, e.g. $\mathcal O(d^2)$ naively, and something like $\mathcal O(d \log d)$ using fast polynomial arithmetic.

share|cite|improve this answer
How do you get the extra $d + 1$ points if each polynomial is represented with just $d$ points? Wouldn't that require to make $\Theta (n)$ evaluations of the polynomials, each taking $\Theta (n)$ time, making the entire procedure take $\Theta (n^2)$ time? – Kelmikra Jul 18 '15 at 22:22

If you represent $A(x)$ as a vector $[a_0, a_1, \dots a_d]$ and $B(x)$ as $[b_0, b_1, \dots b_d]$. Then to find $C(x) = A(x) * B(x)$ is equivalent to

$$ A^{T} B = A B^{T} = \sum_{i=0}^d a_i b_i$$

share|cite|improve this answer
I don't understand this answer at all. Aren't $A^TB$ and $AB^T$ a matrix and a scalar respectively? How does this help you find $C(x)$? – Rahul May 12 '12 at 21:51
Computationally if you store them as a vector, that is equivalent to what J.D. has answered. (If one has written a program in any language one would know) – Kirthi Raman May 13 '12 at 0:36
Don't you need $2d + 1$ points to find $C$, as explained in user2468's answer? – Kelmikra Jul 18 '15 at 22:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.