9 ms·
@utopcell do you have a reference for incremental FFT? I'm not sure if I understand what your implying. Given a polynomial f(X), obtaining f's evaluations over
by rencrisa 4y ago
@utopcell do you have a reference for incremental FFT? I'm not sure if I understand what your implying.
Given a polynomial f(X), obtaining f's evaluations over the n-th roots of unity takes O(nlogn) using FFT. Are you stating that obtaining g(X) != f(X) evaluations over the n-th roots of unity should take O(n) time assuming some precomputation derived in the FFT for f?
- utopcell 4y agoIf X_k is the coefficient for the sample window (x_0, x_1, .., x_{n-1}) and X'_k is the coefficient for window (x_1, .., x_n) then X'_k = (X_k + x_n - x_0)exp(2pik/n).