-1
$\begingroup$

Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need the value $P(x) \bmod M$?

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 6 '16 at 13:13
  • $\begingroup$ Note that "better than O(NM)" is a nonsensical phrase. I guess you mean o(NM), whatever that means precisely with two variables. $\endgroup$ – Raphael Jul 6 '16 at 22:21
  • $\begingroup$ 1. What's the source for this problem? In what context did you run across it? 2. What research have you done? Have you looked on Wikipedia and in standard textbooks? Did you search for related questions here? We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. A quick search on this site immediately turns up cs.stackexchange.com/q/60239/755, which looks highly relevant. $\endgroup$ – D.W. Jul 6 '16 at 22:54
  • $\begingroup$ Taken from a live programming contest: codechef.com/JULY16/problems/POLYEVAL $\endgroup$ – D.W. Jul 11 '16 at 17:41
2
$\begingroup$

The answer given at Multi-point evaluations of a polynomial mod p actually answers the question.

Given a primitive root g of M, it is possible to evaluate $P (g^0), P (g^1), \ldots, P (g^{M-1})$ in $O (\max (N, M) \log \max (N, M))$ steps, and then you just rearrange the resulting values and add $P (0)$ which is just the constant coefficient of the polynomial $P$.

Thanks D.W. for the link. The answer given there says that for an arbitrary set of points evaluating all the polynomial values faster than $N$ times number of points can't be done, but of course the result above is useful whenever the number of points is substantially more than $N \log N$.

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