FFT

什么是 FFT？

$$f(x)=1+2x+3x^2+4x^3$$ $$g(x)=4+3x+2x^2+x^3$$

如何求 $f(x)\cdot g(x)$？逐项计算？$O(n^2)$

还有别的计算方式吗？插值法

找到 $n$ 个点 $(x,f(x))$，$(x,g(x))$ 则 $f(x)\cdot g(x)$ 由 $(x,f(x),g(x))$

找点时间复杂度？$O(n^2)$ 能否优化？

考虑把

$$f(x)=1+2x+3x^2+4x^3$$

奇次项与偶次项分离

$$f(x)=1+3x^2+x(2+4x^2)$$

令

$$f_e(x)=1+3x$$ $$f_o(x)=2+4x$$

则

$$f(x)=f_e(x^2)+x\cdot f_o(x^2)$$

发现一个有意思的：如果 $x$ 取 $1$ 和 $-1$，

则只要算一次 $f_e(x^2)$ 与 $f_o(x^2)$ 就得到两个插值点

注意 $1+3x$ 和 $2+4x$ 也可以用类似的思路继续划分

$$f_e(x)=1+3x=1+x\cdot (3)$$ $$f_e(1)=1+(1)\cdot 3=4f_e(-1)=1+(-1)\cdot 3=-2$$ $$f_o(x)=2+4x=2+x\cdot (4)$$ $$f_o(1)=2+(1)\cdot 4=6f_o(-1)=2+(-1)\cdot 4=-2$$

我们知道 $f_e(1)$ 和 $f_o(1)$ 可以得出 $f(1)$ 和 $f(-1)$ 的值，那么 $f_e(-1)$ 和 $f_o(-1)$ 有什么用呢？

注意到一个 $x^2$ 可以开根号得到两个值 $\sqrt{x}$ 和 $-\sqrt{x}$

他们平方值相同：$(\sqrt{x}{)}^2=(-\sqrt{x}{)}^2=x$

既然 $1$ 可以拆成两个平方根，可否有 $t^2=(-t{)}^2=-1$ 呢？

如果你学过复数，会立马思考到：$i^2=-1$！

于是可得：

$$f(1)=f_e(1)+f_o(1)=4+6=10$$ $$f(i)=f_e(-1)+i\cdot f_o(-1)=-2-2i$$ $$f(-1)=f_e(1)-f_o(1)=4-6=-2$$ $$f(-i)=f_o(-1)-i\cdot f_o(-1)=-2+2i$$

孩子们，是复数，我们有救了。

graph LR;
    subgraph A
    A1[1]
    A2[2]
    A3[3]
    A4[4]
    end
    subgraph Ae
    Ae1[1]
    Ae2[3]
    end
    A1-->Ae1
    A3-->Ae2
    subgraph Ao
    Ao1[2]
    Ao2[4]
    end
    A2-->Ao1
    A4-->Ao2
    
    subgraph Fe
    Fe1[1+3=4]
    Fe2[1-3=-2]
    end
    Ae1-->Fe1
    Ae1-->Fe2
    Ae2-->|-1|Fe2
    Ae2-->|1|Fe1
    subgraph Fo
    Fo1[2+4=6]
    Fo2[2-4=-2]
    end
    Ao1-->Fo1
    Ao1-->Fo2
    Ao2-->|-1|Fo2
    Ao2-->|1|Fo1
    subgraph F
    F1[4+6=10]
    F2["-2+(i)*(-2)=-2-2i"]
    F3[4-6=-2]
    F4["-2+(-i)*(-2)=-2+2i"]
    end
    Fe1-->F1
    Fe1-->F3
    Fe2-->F2
    Fe2-->F4
    Fo1-->|1|F1
    Fo1-->|-1|F3
    Fo2-->|i|F2
    Fo2-->|-i|F4

$f(1)=f_e(1)+f_o(1)$

$f(i)=f_e(-1)+i\cdot f_o(-1)$

$f(-1)=f_e(1)-f_o(1)$

$f(-i)=f_e(-1)-i\cdot f_o(-1)$

根据欧拉公式，这些点分别有另一种表示形式 $e^{\frac{k}{n}2\pi i}$

令 $e_n=e^{\frac{1}{n}2\pi i}$

则每个点分别为 $e_n^k$

根据图还能发现 2 个结论：

$e_{nk}^{mk}=e_n^m{e}_n^k=-e_n^{k+\frac{n}{2}}$

于是上面的方程变成

$f(e_n^k)=f_e(e_n^{2k})+e_n^k{f}_o(e_n^{2k})=f_e\left(e_{\frac{n}{2}}^k\right)+e_n^k{f}_o\left(e_{\frac{n}{2}}^k\right)$

$f(e_n^{k+\frac{n}{2}})=f_e(e_n^{(k+\frac{n}{2}{)}^2})+e_n^{k+\frac{n}{2}}{f}_o(e_n^{(k+\frac{n}{2}{)}^2})=f_e(e_n^{2k})+e_n^{k+\frac{n}{2}}{f}_o(e_n^{2k})=f_e\left(e_{\frac{n}{2}}^k\right)-e_n^k{f}_o\left(e_{\frac{n}{2}}^k\right)$

$(k<\frac{n}{2})$