参考 [快速傅里叶变换 (FFT):有史以来最巧妙的算法]
https://www.zhihu.com/zvideo/1514277241420312576
现在我们有个优势,我们可以随意选取这些点。我们假设取x1=1,
那么左上角两个值应当就是1和-1,进而第二行两个值,应当也是1和-1
最底下的x4,就是-1.
那么,x2和-x2就是i和-i了(虚数)
从另一个角度,我们实际上是解了一个方程
事实上我们知道x^4有4个根,这个能否做推广呢?
给定5阶方程 F(x) = x^5 + 2*x^4-x^3+x^2 。
我们需要n>=6个点,令n=2^3=8(取2的幂次)
我们可以得到如下。
我们需要先取n>=(d+1)个点,且满足 n = 2^k,这些点就应当是1的n个n次方根。
为什么可以这么玩呢?
我们需要一些前置知识。
1的n次方根可以被解释为复平面上沿着单位圆等距排布的一系列点。
任一相邻两点的夹角为2*pi/n
从而这些点的最简便的表示方法就是用,欧拉公式写作复指数(图片右上角)。
如下例子
w^0,w^1, w^2,... w^(n-1)
所以当我们说我们想在1的n次方根求值时,我们实际上是在1,w,...w^(n-1)次方上求值。
回到原来的问题:为啥n次方根就可以用于递归过程呢?
主要有2个原因:
首先我们要求所取的点是正负成对的,这里w^(j+n/2)=-w^j正好是这么一对。
另外一点,当我们平方,并且考虑对应的递归低阶奇/偶函数时,右图表现了平方以后的点在复平面的分布。这表明n次方的另一个好性质:平方以后,我们得到的正好是n/2个n/2次方根!
它们也是正负配对的,完美适合递归。
我们再平方,也可以得到n/4个n/4次方根,适用于下一层的递归,最终直到我们只剩下一个点。
How amzing!
现在我们终于可以介绍FFT算法了
FFT算法的输入是多项式的n个系数p[0],p[1],...p[n-1],其中n是2的幂次
我们取w=e^(2*pi*i/n)为1的n次方根。
递归的底层情况(终止条件)是n=1,此时我们只在一个点上求多项式的值。
而递归的主要命令,就是把多项式拆分成奇/偶函数部分,两部分即调用函数两次。
此时这两个子多项式函数都是n/2阶的,所以对应的求值点将是1的n/2次方根
我们假设递归调用得到的两部分函数值为ye和yo,
现在就是最精彩的部分了:
我们把这两部分函数值结合一些,计算出原多项式函数在对应的点的函数值,
我们之前看到了,结合起来的核心想法就是利用正负对,不过这里我们要为n次方根稍微改一改我们的表达式,
注意这里我们把下标改成从0开始。方便写程序。
我们知道xj此时应该写为w^j,所以公示改写如下,
我们之前也观察到,这里的正负点对是-w^j=w^(j+n/2),我们进而可以把第二个式子改写如下。
还有一个条件,ye和yo的第j个元素,正好对应了Pe(w^(2j))和Po(w^(2j)),因此我们可以把公式右侧全部写为ye和yo
写程序就容易多了,
这部分比较复杂,我们可以自己试着动笔写一写。
最终FFT输出的是原多项式在n个n次方根的值。
我们的输入P是系数表示的一个n-1阶多项式, n定义P的长度,我们假设n是2的幂次,
注意:FFT当然可以处理n不是2的幂次的情况,不过有亿点点复杂,n是2的幂次的情况已经足够代表FFT的核心想法了。
我们先写出递归的底层,n=1时直接输出P
此时n=1,P实际上就是0阶多项式,即常数,
当n>1,我们定义好w,然后就递归调用,首先我们把多项式分成奇/偶两部分,这实现起来很容易,
然后我们只需要对这两个n/2阶多项式调用FFT,记着两个输出为ye,yo,现在就可以把它们拼接起来了,我们初始化最终输出list为y=0,然后我们依右侧公式计算P在对应点的值,
最后,输出y,FFT大功告成!
这么多点子,最后就会聚成了这几行代码!
通过FFT,我们知道了怎么通过系数表示法转换为值表示法。
现在需要反过来,把值表示转换为系数表示。
我们一般称这个过程为插值。
这下要疯狂起来了。
未完待续,,,,
联系客服