高速フーリエ変換

フーリエ変換

F(t) = \sum_{0 \le i \lt n}{f(\omega_n^i)t^i}

逆変換

f(x) = \frac{1}{n}\sum_{0 \le i \lt n}{F(\omega_n^{-i})x^i}

各 $i$ について、 $\sum{f(\omega_n^i)}$ を高速に求める方法があればいい

f(x) = \sum_{0 \le i \lt n}{c_ix^i} \\ f_0(x^2) = \sum_{0 \le i \lt \frac{n}{2}}{c_{2i}x^i} \\ f_1(x^2) = x\sum_{0 \le i \lt \frac{n}{2}}{c_{2i+1}x^i} \\ f(x) = f_0(x^2) + f_1(x^2)

f(\omega_n^{i}) = f_0(\omega_n^{2i}) + f_1(\omega_n^{2i}) \\ = f_0(\omega_{n / 2}^i) + f_1(\omega_{n / 2}^i)

F(t) = \sum_{0 \le i \lt n}{f(\omega_n^i)t^i} \\ = \sum_{0 \le i \lt n}{(f_0(\omega_{n / 2}^i) + f_1(\omega_{n / 2}^i))t^i} \\ = \sum_{0 \le i \lt \frac{n}{2}}{...} + \sum_{0 \le i \lt \frac{n}{2}}{...} \\ = \sum_{0 \le i \lt \frac{n}{2}}{...} + t^{n/2}\sum_{0 \le i \lt \frac{n}{2}}{...} \\ = (1+t^{n/2})(\sum_{0 \le i \lt \frac{n}{2}}{...}) \\ = (1+t^{n/2})(\sum_{0 \le i \lt \frac{n}{2}}{f_0(\omega_{n / 2}^i)t^i} + \sum_{0 \le i \lt \frac{n}{2}}{f_1(\omega_{n / 2}^i)t^i}) \\