# Tag Info

## Hot answers tagged fast-fourier-transform

3

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

2

The product $$V=\prod_{i<j}(a_j-a_i)$$ is the determinant of the Vandermonde matrix of the numbers $a_1,a_2,...,a_n$. The square of this number is the discriminant $D$ of the polynomial $$p(x)=\prod_i(x-a_i)$$ This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod_ip'(a_i)$$ You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it ...

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 & ... 2 If P, Q, R \in \mathbb{R}[X], R = PQ, then for any x \in \mathbb{R}, R(x) = P(x)\times Q(x). It means that if the value representation of P is [(x_1, P(x_1)); (x_2, P(x_2)); …, (x_n, P(x_n))] and the value representation of Q is [(x_1, Q(x_1)); (x_2, Q(x_2)); …, (x_n, Q(x_n))], then the value representation of R is [(x_1, P(x_1)Q(x_1)); (x_2,... 1 For a set S = \{s_1,\dotsc,s_n\}. Construct a polynomial P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}. Multiply the polynomial by itself three times, i.e., P(x) \cdot P(x) \cdot P(x). Let this polynomial be Q(x) Claim: The coefficient of x^T in Q(x) is non-zero if and only if there exist three values in S that sum to T. Proof: [You may want to ... 1 For testing, you can use SageMath very easily; you had erros on$$A(x_0) = 0, A(x_1) = 16, A(x_2) = 85, A(x_3)=208, \\B(x_0) = -1, \color{red}{B(x_1) = -2}, \color{red}{B(x_2) = -5},\color{red}{B(x_3) = 8} R = PolynomialRing(QQ, 'x') A = 3 *x^2-4*x+1 B = x -2 a0 = A(1) a1 = A(3) a2 = A(6) a3 = A(9) b0 = B(1) b1 = B(3) ...

Only top voted, non community-wiki answers of a minimum length are eligible