十分简明易懂的FFT（快速傅里叶变换）

快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
FFT（Fast Fourier Transformation） 是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

$FFT$FFT（Fast Fourier Transformation），中文名快速傅里叶变换，用来加速多项式乘法，
朴素高精度乘法时间$O(n^2)$O(n2)，但$FFT$FFT能$O(nlog{_2}n)$O(nlog2​n)的时间解决。

一、多项式的系数表示法和点值表示法

$FFT$FFT其实是一个用$O(nlog{_2}n)$O(nlog2​n)的时间将一个用系数表示的多项式转换成它的点值表示的算法

1.1 系数表示法

一个$n-1$n−1次$n$n项多项式$f(x)$f(x)可以表示为：$f(x)=\sum_{i=0}^{n-1}{a_i x^i}$f(x)=∑i=0n−1​ai​xi

也可以用每一项的系数来表示$f(x)$f(x)，即：$f(x)=\lbrace{a_0, a_1, a_2,\cdots, a_{n-1}}\rbrace$f(x)={a0​,a1​,a2​,⋯,an−1​}

1.2 点值表示法

• 把多项式放到平面直角坐标系里面，看成一个函数
• 把$n$n个不同的$x$x代入，会得出$n$n个不同的$y$y，在坐标系内就是$n$n个不同的点
• 那么这$n$n个点唯一确定该多项式，也就是有且仅有一个多项式满足$∀k,f(x_k)=y_k$∀k,f(xk​)=yk​
• 理由很简单，把$n$n条式子联立起来成为一个有$n$n条方程的$n$n元方程组，每一项的系数都可以解出来

那么$f(x)$f(x)还可以用 $f(x)=\lbrace(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_{n−1},f(x_{n−1}))\rbrace$f(x)={(x0​,f(x0​)),(x1​,f(x1​)),(x2​,f(x2​)),⋯,(xn−1​,f(xn−1​))} 来表示
这就是点值表示法。

1.3 高精度乘法下两种多项式表示法的区别

对于两个用系数表示的多项式，我们把它们相乘，设这两个多项式分别为 $A(x), B(x)$A(x),B(x)，
我们要枚举 $A$A 每一位系数 与 $B$B 每一位的系数相乘，那么系数表示法做多项式乘法时间复杂序 $O(n^2)$O(n2)。

但用两个点值表示的多项式相乘，只需要 $O(n)$O(n) 的时间。

理解如下：
设两个点值多项式分别为：
$f(x) = \lbrace(x_0,f(x_0)), (x_1,f(x_1)), (x_2,f(x_2)),\cdots,(x_{n-1},f(x_{n-1}))\rbrace$f(x)={(x0​,f(x0​)),(x1​,f(x1​)),(x2​,f(x2​)),⋯,(xn−1​,f(xn−1​))}
$g(x) = \lbrace(x_0,g(x_0)), (x_1,g(x_1)), (x_2,g(x_2)),\cdots,(x_{n-1},g(x_{n-1}))\rbrace$g(x)={(x0​,g(x0​)),(x1​,g(x1​)),(x2​,g(x2​)),⋯,(xn−1​,g(xn−1​))}

设它们的乘积是$h(x)$h(x)，那么：
$\bf h(x) = \lbrace (x_0, f(x_0)\cdot{g(x_0)}) , (x_1, f(x_1)\cdot{g(x_1)}), (x_2, f(x_2)\cdot{g(x_2)}) , \cdots, (x_{n-1}, f(x_{n-1})\cdot{g(x_{n-1})})\rbrace$h(x)={(x0​,f(x0​)⋅g(x0​)),(x1​,f(x1​)⋅g(x1​)),(x2​,f(x2​)⋅g(x2​)),⋯,(xn−1​,f(xn−1​)⋅g(xn−1​))}

所以这里的时间复杂度只有一个枚举的$O(n)$O(n)

• 朴素系数转点值的算法叫$DFT$DFT（离散傅里叶变换），点值转系数叫$IDFT$IDFT（离散傅里叶逆变换）

二、$DFT$DFT 前置知识&技能

2.1 复数

我们把形如a+bi（a,b均为实数）的数称为复数，其中a称为实部，b称为虚部，i称为虚数单位。当虚部等于零时，这个复数可以视为实数；当z的虚部不等于零时，实部等于零时，常称z为纯虚数。

初中数学老师会告诉你没有 $\sqrt{-1}$−1​， 但仅限 $R$R 实数域
扩展至复数集 $C$C，定义 $i^2 = -1$i2=−1，一个复数 $z$z 可以表示为 $z = a + bi(a, b∈R)$z=a+bi(a,b∈R)
其中 $a$a 为实部，$b$b 为虚部，$i$i 称为虚数单位

• 在复数集中就可以用 $i$i 表示负数的平方根，如 $\sqrt{-7} = \sqrt{7}i$−7​=7​i

还可以把复数看作复平面直角坐标系上的一个点，比如下面：

这个点$(2 , 3)$(2,3) 表示的就是复数 $2 + 3i$2+3i，或者想象它代表的向量$(2, 3)$(2,3)

一个复数$z$z 的模定义为它到原点的距离，记为$|z| = \sqrt{a^2 + b^3}$∣z∣=a2+b3​
一个复数 $z = a + bi$z=a+bi 的共轭复数为 $a - bi$a−bi(虚部取反)，记为 $\overline z = a - bi$z=a−bi

2.2 复数的运算

设两个复数分别为$z_1=a+bi, z_2=c+di$z1​=a+bi,z2​=c+di 那么，

$z_1 + z_2 = (a + c) + (b + d)i$z1​+z2​=(a+c)+(b+d)i
$z_1\cdot z_2 = (ac - bd) + (ad + bc)i$z1​⋅z2​=(ac−bd)+(ad+bc)i

复数相加也满足平行四边形法则：

即 $AB + AD = AC$AB+AD=AC

复数相乘还有一个值得注意的小性质： 模长相乘，极角相加
$(a_1, \theta_1 ) \cdot (a_2, \theta_2) = (a_1 a_2, \theta_1 + \theta_2)$(a1​,θ1​)⋅(a2​,θ2​)=(a1​a2​,θ1​+θ2​)

三、$DFT$DFT （离散傅里叶变换）

• 一定注意从这里开始所有的nn都默认为22的整数次幂

对于任意系数多项式转点值，当然可以随便取任意$n$n个$x$x值代入计算，
但是暴力计算 $x_k^0, x_k^1, \cdots, x_k^{n-1} (k \in [0,n))$xk0​,xk1​,⋯,xkn−1​(k∈[0,n)) 当然是$O(n^2)$O(n2) 的时间。

其实可以代入一组神奇的$x$x，代入后不用做那么多的次方运算，这些 $x$x 当然不是乱取的，而且取这些 $x$x 值应该就是 傅里叶 的主意了。

考虑一下，如果我们代入一些$x$x，使每个$x$x的若干次方等于 $1$1，我们就不用做全部的运算了。
$\bf \pm 1$±1 是可以的，考虑虚数的话 $\pm i$±i 也可以，但只有这四个数远远不够。

• 傅里叶说：这个圆圈上面的点都可以做到
  

以原点为圆心，画一个半径为$1$1的单位圆，那么单位圆上所有的点都可以经过若干次次方得到$1$1，
傅里叶说还要把它给nn等分了，比如此时$n=8$n=8

橙色点为 $n = 8$n=8时要取的点，从$(1, 0)$(1,0) 点开始，
逆时针从 $0$0 号开始标号，标到 $7$7 号记偏号为 $k$k 的点代表的复数为$\omega _n^k$ωnk​，
那么由模长相乘，极角相加可知 $(\omega _n^1)^k = \omega _n^k$(ωn1​)k=ωnk​，其中 $(\omega _n^1)$(ωn1​) 称为 $n$n次单位根，而且每一个$\omega$ω 都可以求出
$\omega _n^k = \cos({\frac k n}2\pi) + i\sin({\frac k n}2\pi)$ωnk​=cos(nk​2π)+isin(nk​2π)

或者说也可以认这样解释这条式子：

注意${sin^2}θ+{cos^2}θ=1$sin2θ+cos2θ=1什么的，就容易理解了

那么 $\omega_n^0，\omega_n^1，\cdots，\omega_n^{n-1}$ωn0​，ωn1​，⋯，ωnn−1​ 即为我们要代入的 $x_0，x_1, x_2，\cdots，x_{n-1}$x0​，x1​,x2​，⋯，xn−1​

3.1 单位根的一些性质

推$FFT$FFT 的过程需要用到 $\omega$ω 的一些性质
$\omega _n ^k = \omega _2n ^2k$ωnk​=ω2​n2k

它位表示的点（或向量） 表示的复数是相同的，证明如下：
$\omega _n ^k = \cos{_n^k}2\pi + i \sin{_n^k}2\pi = \cos{_2n^2k}2\pi + i \sin{_2n^2k}2\pi = \omega _2n ^2k$ωnk​=cosnk​2π+isinnk​2π=cos2​n2k2π+isin2​n2k2π=ω2​n2k

$\bf \omega_n^{k+\frac n 2} = -\omega _n ^k$ωnk+2n​​=−ωnk​

$\omega_n^0 = \omega_n^n = 1$ωn0​=ωnn​=1

$e^{ix} = \cos x + i \sin x$eix=cosx+isinx
$e^{i\pi} = \cos \pi + i \sin \pi = -1 \longrightarrow e^{i\pi} +1 = 0$eiπ=cosπ+isinπ=−1⟶eiπ+1=0

3.2 $FFT$FFT （快速傅里叶变换）

虽然 $DFT$DFT 搞出来一堆很牛逼的 $ω$ω 作为代入多项式的 $x$x 值

但只是代入这类特殊xx值法的变换叫做 $DFT$DFT 而已，还是要代入单位根暴力计算

• $DFT$DFT 还是暴力 $O(n^2)$O(n2)

但 $DFT$DFT 可以分治来做，于是 $FFT$FFT(快速傅里叶变换) 就出来了。

首先设一个多项式$A(x)$A(x)
$A(x)=\sum_{i=0}^{n-1} a_i{x^i} = a_0 + a_1x+a_2x^2 + \cdots + a_n x^{n-1}$A(x)=i=0∑n−1​ai​xi=a0​+a1​x+a2​x2+⋯+an​xn−1

按 $A(x)$A(x) 下标的奇偶性把 $A(x)$A(x) 分成两半，右边再提一个$x$x

两边好像非常相似，于是再设两个多项式$A_1(x)，A_2(x)$A1​(x)，A2​(x)，令

比较明显得出:
$A(x) = A_1(x^2) + xA_2(x^2)$A(x)=A1​(x2)+xA2​(x2)

再设 $k < \frac n 2$k<2n​，把 $\omega _n^k$ωnk​ 作为 $x$x 代入$A(x)$A(x)：

那么对于 $A(\omega_n^{k+\frac n 2})$A(ωnk+2n​​) 的话，代入 $\omega_n^{k+\frac n 2}$ωnk+2n​​

我们可以发现

$A(\omega_n^{k})$A(ωnk​) 和 $A(\omega_n^{k+\frac n 2})$A(ωnk+2n​​) 两个多项式后面 一坨只有符号不同，
也就是说，如果已知 $A_1(\omega^k_{\frac n 2})$A1​(ω2n​k​) 和 $A_2(\omega^k_{\frac n 2})$A2​(ω2n​k​) 的值，
我们就可以同时知道 $A_1(\omega^k_{n})$A1​(ωnk​) 和 $A_1(\omega_n^{k+\frac n 2})$A1​(ωnk+2n​​)

每次回溯时只扫当前前面一半的序列，即可得出后面一半序列的答案
$n == 1$n==1 时只有一个常数项，直接 $return$return
时间复杂序$O(n \log _2 n)$O(nlog2​n)

3.3 $IFFT$IFFT （快速傅里叶逆变换）

想一下，我们不仅要会$FFT$FFT，还要会 $IFFT$IFFT（快速傅里叶逆变换）

我们把两个多项式相乘 （也叫求卷积），做完两遍$FFT$FFT 也知道了积的多项式的点值表示，
可我们平时系数表示的多项式，点值表示没有意义。

• 怎么把点值表示的多项式快速转回系数表示法？

• $IDFT$IDFT 暴力$O(n^2)$O(n2) 做? 其实也可以 $FFT$FFT 用 $O(n log_2 n)$O(nlog2​n)的时间搞

你有没有想过为什么傅里叶是把$\omega_n^k$ωnk​ 作为$x$x 代入而不是别的什么数？

• 一个多项式在分治的过程中乘上单位根的共轭复数，分治完的每一项除以 $n$n 即为原多项式的每一项系数

本文：《十分简明易懂的FFT（快速傅里叶变换）》

《小学生都能看懂的FFT！！！》

《浅入浅出理解傅里叶变换》
《如何理解离散傅里叶变换（一）实数形式傅里叶变换》
《快速傅里叶变换（FFT）》

《网上找的纯C实现的FFT,与matlab计算结果完全一样》
《用c语言实现的FFT》