We’re rewarding the question askers & reputations are being recalculated! Read more.

New answers tagged

1

You should also look at what you actually want to achieve. The coefficients can grow very quickly, meaning that evaluating the polynomial can have large rounding errors. Given the roots, you can evaluate the polynomial quite quickly without knowing the coefficients, and with high precision.


21

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method. First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the ...


2

You already explained what to do when $k = 2$. Let's see what to do when $k = 3$. Let $P_i$ be the polynomial corresponding to $iS$ (for example, the solution for $k = 2$ is $(P_1^2 - P_2)/2$). We can construct the following table: $$ \begin{array}{c|ccc} & aaa & aab & abc \\\hline P_1^3 & 1 & 1 & 1 \\ 3P_2 P_1 & 3 & 1 & ...


Top 50 recent answers are included