|
参考 [快速傅里叶变换 (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算法了 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，我们知道了怎么通过系数表示法转换为值表示法。 现在需要反过来，把值表示转换为系数表示。 我们一般称这个过程为插值。 这下要疯狂起来了。 未完待续，，，， |
|
|
推广到d阶多项式，F(x) = p0 + p1 *x + p2 * x^2 + ... + ... + pd * x^d
我们定义w = e^(2*pi*i/n)，那么不同i取值实际上就代表了不同的单位复n次方根。
