5
$\begingroup$

Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's algorithm for factorization but it takes $O(n^3)$ just to factorize and then $O(n)$ per point evaluation. Is there any other way to bring the complexity down considerably like to $n\log(q)$ where $q$ is the number of points I want to evaluate the polynomial at? Or possibly polynomial time? All the coefficients and the values of $x$ that the polynomial is to be evaluated at lie between the $0$ and $prime - 1$, the prime is of order $10^6$.

$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! 1. How many values of $x$? The best algorithm will likely depend on that. 2. What do you mean by "best"? Are you looking for something with the best asymptotic running time? A practical solution? Something that is easiest to implement? $\endgroup$ – D.W. Jul 3 '16 at 2:21
  • 1
    $\begingroup$ Doing the CodeChef contest problem codechef.com/JULY16/problems/POLYEVAL? Please don't ask us to solve your coding contest problem for you. If you're going to use material/problems from another source, you must credit/attribute the source. (Also, CodeChef prohibits from asking others to help you solve your problem; many consider asking us to tell you how to solve the contest problem to be cheating.) $\endgroup$ – D.W. Jul 11 '16 at 17:39
  • $\begingroup$ @D.W. with some search it's easy to find the concept behind it, what's difficult is the implementation! Thanks by the way for not spilling the beans before the contest. $\endgroup$ – Sahil Arora Jul 11 '16 at 20:57
9
$\begingroup$

No, $O(n \lg q)$ running time is not achievable. It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution. The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times. It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time. For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x_1,\dots,x_n$.

We're going to use divide-and-conquer. Define

$$\begin{align*} f_0(x) &= f(x) \bmod (x-x_1)(x-x_2)\cdots(x-x_{n/2})\\ f_1(x) &= f(x) \bmod (x-x_{n/2+1})\cdots(x-x_n) \end{align*}$$

Now we have

$$f(x_i) = \begin{cases} f_0(x_i) &\text{if }i\le n/2\\ f_1(x_i) &\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f_0(x)$ at the points $x_1,\dots,x_{n/2}$ and evaluate $f_1(x)$ at the points $x_{n/2+1},\dots,x_n$. We can do this by a recursive invocation of the same procedure. Since both $f_0(x)$ and $f_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f_0(x)$ and $f_1(x)$ from $f(x)$. This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$. Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic.

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.

$\endgroup$
  • 3
    $\begingroup$ I feel like the chapter "multi-point polynomial evaluation" describes the basic idea for a general evaluation algorithm using FFT, with runtime O(n log^2 n): dis.uniroma1.it/~sankowski/lecture4.pdf Not sure if it applicable to DFT as well. $\endgroup$ – Niklas B. Jul 11 '16 at 9:13
  • $\begingroup$ Thanks, NiklasB.! I've updated my answer based on that information. $\endgroup$ – D.W. Mar 6 at 21:32

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.