3
$\begingroup$

For homework I've to give an algorithm that computes the coefficients of the polynomial $p(x)^n$ in time $O(n\log n)$, where $p(x)$ is a polynomial of degree 7.

As an hint I'm told to consider first the case where $n$ is a power of 2.

My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $n$ are the same as for $n/2$, only twice) but I'm pretty clueless about this one.

$\endgroup$
2
  • 1
    $\begingroup$ Couldn't you use an algorithm based on fast exponentiation? $\endgroup$
    – Nathaniel
    May 12 at 8:41
  • $\begingroup$ @Nathaniel Maybe, but I don't really see how $\endgroup$
    – RedYoel
    May 12 at 13:02
3
$\begingroup$

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$.

It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p_i(x)$, we can compute $p_{i+1}(x)$ in time complexity $O(d_i\log d_i)$ where $d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$.

We can know compute $p_k(x)$ by successively computing $p_1, p_2, …, p_{k-1}$. The total time complexity will be:

$$O\left(\sum\limits_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$

Now for the general case where $n$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $n$, like in fast exponentiation.

$\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.