4
$\begingroup$

I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the coefficients stored in an array/vector).

I know the algorithm with $O(n^2)$ time complexity, which is based on Horner's method: $$a_0+(x+d)(a_1+(x+d)(a_2+...+(x+d)a_n))$$ However, it is not efficient enough for my needs. Is there an algorithm that is more efficient for solving this problem?

P.S. The coefficients and $d$ will always be integers, if that helps.

$\endgroup$
4
$\begingroup$

Use FFT. Suppose that $\deg P \leq n$ and we use FFT on $n$ points (usually $n$ would be the smallest power of 2 which is at least $\deg P$). Let $\omega$ be an $n$th root of unity. The Fourier coefficients of $Q(x) = P(x+d)$ are $$ \hat{Q}(m) = \sum_{i=0}^{n-1} Q(i) \omega^{mi} = \sum_{i=0}^{n-1} P(i+d) \omega^{mi} = \sum_{i=0}^{n-1} P(i) \omega^{m(i-d)} = \omega^{-md} \hat{P}(m). $$ This shows how to compute the Fourier transform of $Q$ from that of $P$ in linear time. Since FFT takes time $O(n\log n)$ (for suitable $n$), the overall running time is $O(n\log n)$. Choosing $n$ as indicated above, this becomes $O(\deg P \log \deg P)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.