MathOverflow is a question and answer site for professional mathematicians. 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

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ operations in $R$ for some $k >0$ . But could we compute $ f( X + \alpha ) $, or more generally compute $ f( \alpha X + \beta)$ in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$. Since the result is a polynomial in $X$ of degree at most $n$, I would guess there is a such way. But from the naive way, I can't just figure out a $O(n^2)$ algorithm to do this as follows: If $f(X) = \sum_{i=1}^n a_i X^i$, then one compute $g \leftarrow a_0, h \leftarrow \alpha X + \beta, g \leftarrow g+ a_{i+1} * h, h \leftarrow h* (\alpha X + \beta) $ for $0 \leq i \leq n-1$. In the $i$-th step, $g$ is a polynomial of degree $i$ and $h$ is a polynomial of degree $i+1$, so we need $O(i)$ operations in $R$ to compute $ g+ a_{i+1} * h$ and $h* (\alpha X + \beta) $, so the total operations needed is $O(n^2)$.

Is there any way to do so in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$? I don't really need to know how the algorithm works, I just need an explicit reference which says this is possible.

share|cite|improve this question

The answer is yes. You can do it using Fast Fourier Transform(FFT) to make FFT you need $n \log^k n$ operations. You not really need to know what FFT do. You need only to know that you can evaluate polynomial at some $n$ points using one FFT and you can calculate the polynomial from its values at $n$ points in one FFT.

The following algorithm should work: Using FFT evaluate $F(aX+b)$ at n points it is the same as to calculate F(X) at $n$ points. Next again using FFT you can calculate $F(aX+b)$.

share|cite|improve this answer
You might need to work in an extension of $R$ to make the FFT work (you need a primitive $n$th root of unity or so). – Emil Jeřábek May 9 '11 at 17:47
Yes, you are right I am litle bit simplifing the situation. I saw the paper which do it for arbitary algebra, but I can not remember where I saw it. – Klim Efremenko May 9 '11 at 20:03
Cantor and Kaltofen do polynomial multiplication over any algebra. Presumably the same form of FFT could be used here. – Emil Jeřábek May 10 '11 at 10:54

Your Answer


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

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