FFT（快速傅里叶变换）
目录
-
FFT（快速傅里叶变换）
- 前言
-
多项式的系数表示法和点值表示法
- 系数表示法
- 点值表示法
- 高精度乘法下两种多项式表示法的区别
前言
快速傅里叶变换 (fast Fourier transform, 即利用计算机计算离散傅里叶变换（DFT的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
也就是说 ：FFT用来加速两个多项式的乘法。
我水了一篇博客。
多项式的系数表示法和点值表示法
系数表示法
\(n - 1\ 次的 \(n\ 项多项式 \(f(x\ 可以表示为 \(f(x = \sum_{i= 0}^{n- 1} a_ix^i\
\[f(x = a_0 + a_1x^1 + a_2x^2+a_3x^3+\cdots+a_{n - 1}x^{n - 1}
\]
这就是我们平常最常用的 系数表示法
点值表示法
-
那么这 \(n\ 个点 唯一确定 该多项式，也就是 有且仅有 一个多项式满足 $∀k, f(x_k = y_k $ （这个其实跟插值差不多，大家可以看看这个拉格朗日插值法）
把多项式放到平面直角坐标系里面，看成一个函数
这就是 点值表示法
高精度乘法下两种多项式表示法的区别
系数表示的多项式，我们把它们相乘时。
但是点值表示法就不太一样了，只需要 \(O(n\ 的时间。
\[f(x = {(x_0 , f(x_0,(x_1 , f(x_1(x_2 , f(x_2 \cdots (x_n - 1 , f(x_n - 1} \newline
g(x = {(x_0 , g(x_0,(x_1 , g(x_1(x_2 , g(x_2 \cdots (x_n - 1 , g(x_n - 1}
\]
设他们的乘积是 \(h(x\ 则
\[h(x = {(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}}
\]
好像我们只用把系数表示法转换成点值表示法就可以 \(O(n\ 解决多项式乘法了
FFT