超详细易懂FFT（快速傅里叶变换）及代码实现

Trilarflagz · 2019-08-12 19:49:31 · 题解

博客食用更佳哦QAQ

前言

昨天学了一晚上，终于搞懂了FFT。希望能写一篇清楚易懂的题解分享给大家，也进一步加深自己的理解。 FFT算是数论中比较重要的东西，听起来就很高深的亚子。但其实学会了（哪怕并不能完全理解)，会实现代码，并知道怎么灵活运用 ~~（背板子）~~ 就行。接下来进入正题。

定义

FFT（Fast Fourier Transformation），中文名快速傅里叶变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

而在信奥中，一般用来加速多项式乘法。朴素高精度乘法的时间为O(n^2)，但FFT能将时间复杂度降到 O(nlog_2n)

学习FFT之前，需要了解一些有关复数和多项式的知识。

有关知识

多项式的两种表示方法

系数表示法

F[x]=y=a_0x^0+a_1x^1+a_2x^2+......a_nx^n

{a_0,a_1,a_2,...,a_n} 是这个多项式每一项的系数，所以这是多项式的系数表示法

点值表示法

在函数图像中，F[x]这个多项式可以被n个点唯一确定，即代入n个点作为x,分别解出对应的 y，得到n个式子。把这n条式子联立起来成为一个有n条方程的n元方程组，每一项的系数都可以解出来.（可类比二元一次方程）

也就是说，使用{(x_0,f[x_0]),(x_1,f[x_1]),...,(x_n,f[x_n])}就可以完整描述出这个多项式,这就是 多项式的点值表示法

多项式相乘

设两个多项式分别为f(x),g(x),我们要把这两个多项式相乘 (即求卷积)。

如果用系数表示法: 我们要枚举f的每一位的系数与g的每一位的系数相乘，多项式乘法时间复杂度O(n^2)，这也是我们所熟知的高精度乘法的原理。

如果用点值表示法:

$g[x]$={$(x_0,g[x_0])$,$(x_1,g[x_1])$,...,$(x_n,g[x_n])$} $f[x]*g[x]$={$(x_0,f[x_0]*g[x_0])$,$(x_1,f[x_1]*g[x_1])$,...,$(x_n,f[x_n]*g[x_n])$} 我们可以发现，如果两个多项式取相同的$x$，得到不同的$y$值，那么只需要$y$值对应相乘就可以了！复杂度只有枚举$x$的$O(n)

那么问题转换为将多项式系数表示法转化成点值表示法。

朴素系数转点值的算法叫DFT（离散傅里叶变换）,优化后为FFT（快速傅里叶变换），点值转系数的算法叫IDFT（离散傅里叶逆变换），优化后为IFFT(快速傅里叶逆变换)。之后我会分别介绍。

卷积

~~其实不理解卷积也没关系，但这里顺便提一下，可以跳过的~~ 卷积与傅里叶变换有着密切的关系。利用一点性质，即两函数的傅里叶变换的乘积等于它们卷积后的傅里叶变换，能使傅里叶分析中许多问题的处理得到简化。

F(g(x)*f(x)) = F(g(x))F(f(x))

其中F表示的是傅里叶变换

复数

高中数学会详细讲解，知道的可以跳过这一部分，没学过也没关系，看以下内容应该能很清楚的理解。

1.定义

数集拓展到实数范围内，仍有些运算无法进行。比如判别式小于0的一元二次方程仍无解，因此将数集再次扩充，达到复数范围。

复数z被定义为二元有序实数对(a,b),记为z=a+bi,这里a和b是实数，规定i是虚数单位。 (i^2=-1 即i=\sqrt{-1})

对于复数z=a+bi。实数a称为复数z的实部(real part),记作rez=a.实数b称为复数z的虚部(imaginary part)记作 Imz=b.

当虚部等于零时，这个复数可以视为实数。即当b=0时，z=a,这时复数成为实数；当且仅当a=b=0时，它是实数0；

当z的虚部不等于零时，实部等于零时，常称z为纯虚数。即当a=0且b≠0时，z=bi，我们就将其称为纯虚数。

将复数的实部与虚部的平方和的正的平方根的值称为该复数的模，记作∣z∣。

即对于复数z=a+bi，它的模为∣z∣=\sqrt{(a^2+b^2)}

2.复数的几何意义

直接两张图搞定√ ~~(应该可以一目了然)~~

3.运算法则

加法法则:(a+bi)+(c+di)=(a+c)+(b+d)i; 减法法则:(a+bi)-(c+di)=(a-c)+(b-d)i; 注：复数加减满足平行四边形法则：

乘法法则:(a+bi)·(c+di)=(ac-bd)+(bc+ad)i

复数相乘一个重要法则：模长相乘，幅角相加。（这个定理很重要）

模长：这个向量的模长，即这个点到原点的距离。（不懂的可再看下向量的几何意义）。

幅角: 从原点出发、指向x轴正半轴的射线绕原点逆时针旋转至过这个点所经过的角。

在极坐标（可看成平面直角坐标系）下，复数可用模长r与幅角θ表示为(r,θ)。对于复数a+bi, r=\sqrt{a^2+b^2}，θ=arctan(b/a)。此时，复数相乘表现为模长相乘，幅角相加。

除法法则：(a+bi)÷(c+di)=[(ac+bd)/(c²+d²)]+[(bc-ad)/(c²+d²)]i

4. 共轭复数

一个复数z=a+bi的共轭复数为a−bi（实部不变，虚部取反），记为 \overline{z}=a-bi 。当复数模为1时（即|z|=1），与共轭复数互为倒数

证明：z*\overline{z}=a^2-b^2*i^2=a^2+b^2=|z|^2=1

FFT加速多项式乘法

由于多项式乘法用点值表示比用系数表示快的多，所以我们先要将系数表示法转化成点值表示法相乘，再将结果的点值表示法转化为系数表示法的过程。

第一个过程叫做FFT（快速傅里叶变换)，第二个过程叫IFFT（快速傅里叶逆变换） 在讲这两个过程之前，首先了解一个概念：

单位根

复数\omega满足\omega^n=1，称\omega是n次单位根

怎么找单位根？

单位圆:圆心为原点、1为半径的圆把单位圆n等分，取这n个点（或点表示的向量）所表示的复数（即分别以这n个点的横坐标为实部、纵坐标为虚部，所构成的虚数），即为n次单位根。

下图包含了当n=8时，所有的8次单位根，分别记为\omega_8^1,\omega_8^2.....,\omega_8^8 (图中圆的半径是1，w表示\omega,且下标8已省略）

~~图是我自己画的，可能有点丑QWQ~~ 由此我们知道如何找单位根啦从点(1,0)开始（即\omega_n^1）,逆时针将这n个点从0开始编号，第k个点对应的虚数记作\omega_n^k

由复数相乘法则：模长相乘幅角相加
可得：

(\omega_n^1)^k=\omega_n^k

根据每个复数的幅角，可以计算出所对应的点/向量。

(cos⁡$\frac{k}{n}2π$,sins⁡$\frac{k}{n}2π$)，即为复数 cos⁡⁡$\frac{k}{n}2π$+i sin⁡$\frac{k}{n}2π

单位根的性质

建议记住，因为对之后的分析很重要！！

1.\omega_n^k=\omega_{2n}^{2k}

2.\omega_n^k=-\omega_{n}^{k+\frac n 2}

3.\omega_n^0=\omega_{n}^n=1

至于怎么证明，就是复数相乘时模长相乘幅角相加的原则。或者你直接观察图也可以很显然的得出结论。

DFT（离散傅里叶变换）

对于任意多项式系数表示转点值表示，例如F[x]=y=a_0x^0+a_1x^1+a_2x^2+......+a_nx^n ，可以随便取任意n个x值代入计算,但这样时间复杂度是O(n^2)

所以伟大数学家傅里叶取了一些特殊的点代入，从而进行优化。

他规定了点值表示中的n个x为n个模长为1的复数。这n个复数不是随机的，而是单位根。

把上述的n个复数（单位根）\omega_n^0,\omega_n^1.....,\omega_n^{n-1}代入多项式，能得到一种特殊的点值表示，这种点值表示就叫DFT（离散傅里叶变换）。

FFT（快速傅里叶变换）

虽然DFT能把多项式转换成点值但它仍然是暴力代入n个数，复杂度仍然是O(n2)，所以它只是快速傅里叶变换的朴素版。

所以我们要考虑利用单位根的性质，加速我们的运算，得到FFT（快速傅里叶变换）

对于多项式 A(x)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}，将A(x)的每一项按照下标的奇偶分成两部分：

A(x)=a_0x^0+a_2x^2+...+a_{n-2}x^{n-2}+x(a_1x^0+a_3x^2+...+a_{n-1}x^{n-2})

设两个多项式 A_0(x)和A_1(x)，令：

A_0(x)=a_0x^0+a_2x^1+...+a_{n-2}x^{n/2-1}

A_1(x)=a_1x^0+a_3x^1+...+a_{n-1}x^{n/2-1}

显然，A(x)=A_0(x^2)+x*A_1(x^2)

假设k<n，代入x=ω_n^k（n次单位根）：

A(\omega_n^k)$$=A_0(\omega_n^{2k})+\omega_n^{k}*A_1(\omega_n^{2k})$$=A_0(\omega_\frac n2^{k})+\omega_n^{k}*A_1(\omega_\frac n 2^{k})

A(\omega_n^{k+\frac n 2})=A_0(\omega_n^{2k+n})+\omega_n^{k+\frac n 2}*A_1(\omega_n^{2k+n})$$=A_0(\omega_\frac n2^{k})-\omega_n^{k}*A_1(\omega_\frac n 2^{k})

考虑A1(x)和A2(x)分别在(\omega_\frac n 2^{1},\omega_\frac n 2^{2},\omega_\frac n 2^{3},...,\omega_\frac n 2^{\frac n 2-1})的点值表示已经求出，就可以O(n)求出A(x)在(\omega_n ^{1},\omega_n ^{2},\omega_n ^{3},...,\omega_n ^{n-1})处的点值表示。

这个操作叫蝴蝶变换。

而A1(x)和A2(x)是规模缩小了一半的子问题，所以不断向下递归分治。当n=1的时候返回。

注：这个过程一定要求每层都可以分成两大小相等的部分，所以多项式最高次项一定是2的幂，不是的话直接在最高次项补零QAQ。

时间复杂度O(nlog_2n)

IFFT（快速傅里叶逆变换）

我们已经将两个多项式从系数表示法转化成点值表示法相乘后，还要将结果从点值表示法转化为系数表示法，也就是IFFT（快速傅里叶逆变换）

首先思考一个问题，为什么要把\omega_n^k（单位根）作为x代入？

当然是因为离散傅里叶变换特殊的性质，而这也和IFFT有关。

一个重要结论

把多项式A(x)的离散傅里叶变换结果作为另一个多项式B(x)的系数，取单位根的倒数即\omega_n^0,\omega_n^{-1}.....,\omega_n^{1-n}作为x代入B(x)，得到的每个数再除以n，得到的是A(x)的各项系数，这就实现了傅里叶变换的逆变换了。

相当于在FFT基础上再搞一次FFT。

证明~~（个人觉得写的非常清楚，不想看的跳过吧）~~~~

设(y_0,y_1,y_2,...,y_{n-1})为多项式

设多项式$B(x)=y_0+y_1x+y_2x^2+...+y_{n-1}x^{n-1}

把离散傅里叶变换的\omega_n^0,\omega_n^1.....,\omega_n^{n-1}这n个单位根的倒数，即\omega_n^0,\omega_n^{-1}.....,\omega_n^{1-n}作为x代入B(x), 得到一个新的离散傅里叶变换(z_0,z_1,z_2,...,z_{n-1})

z_k$=$\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i

=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j*(\omega_n^i)^j)(ω_n^{-k})^i

=\sum_{j=0}^{n-1}a_j*(\sum_{i=0}^{n-1}(\omega_n^i)^{j-k})

当j-k=0时，\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}=n

否则，通过等比数列求和可知：

\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}

=\frac{(ω_n^{j-k})^n-1}{ω_n^{j-k}-1}=\frac{(ω_n^{n})^{j-k}-1}{ω_n^{j-k}-1}=\frac{1-1}{ω_n^{j-k}-1}=0
（因为\omega_n^n=\omega_n^0=1）

所以

z_k=n*a_k

a_k=\frac {z_k} n

得证。

怎么求单位根的倒数呢？

单位根的倒数其实就是它的共轭复数。~~不明白的可以看看前面共轭复数的介绍~~

到现在你已经完全学会FFT了，但写递归还是可能会超时，所以我们需要优化

优化：迭代FFT

在进行FFT时，我们要把各个系数不断分组并放到两侧，一个系数原来的位置和最终的位置的规律如下。

初始位置：\omega_n^0 \omega_n^1 \omega_n^2 \omega_n^3 \omega_n^4 \omega_n^5 \omega_n^6 \omega_n^7

第一轮后：\omega_n^0 \omega_n^2 \omega_n^4 \omega_n^6|\omega_n^1 \omega_n^3 \omega_n^7 \omega_n^5

第二轮后：\omega_n^0 \omega_n^4|\omega_n^2 \omega_n^6|\omega_n^1 \omega_n^5|\omega_n^3 \omega_n^7

“|”代表分组界限把每个位置用二进制表现出来。

位置x上的数，最后所在的位置是“x二进制翻转得到的数”，例如4(100）最后到了1（001）。5(101)最后不变为5(101)，3(011)最后到了6(110)。

所以我们先把每个数放到最后的位置上，然后不断向上还原，同时求出点值表示就可以啦。

迭代版FFT就比之前的递归版快多了,真O(nlog_2n)绝妙算法

代码实现FFT

下面是本人写的FFT加速高精度乘法的代码（并有详细注释）：

#include<bits/stdc++.h>
using namespace std;
//complex是stl自带的定义复数的容器 
typedef complex<double> cp;
#define N 2097153
//pie表示圆周率π 
const double pie=acos(-1);
int n;
cp a[N],b[N];
int rev[N],ans[N];
char s1[N],s2[N];
//读入优化 
int read(){
    int sum=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
//初始化每个位置最终到达的位置 
{
    int len=1<<k;
    for(int i=0;i<len;i++)
    rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}
//a表示要操作的系数，n表示序列长度
//若flag为1，则表示FFT，为-1则为IFFT(需要求倒数） 
void fft(cp *a,int n,int flag){ 
    for(int i=0;i<n;i++)
    {
     //i小于rev[i]时才交换，防止同一个元素交换两次，回到它原来的位置。 
      if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
    {
    cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1 
     for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
     {
      cp w(1,0);
       for(int k=j;k<j+h;k++)//只扫左半部分，得到右半部分的答案
       {
         cp x=a[k];
         cp y=w*a[k+h];
         a[k]=x+y;  //这两步是蝴蝶变换 
         a[k+h]=x-y;
         w*=wn; //求w_n^k 
       }
     }
     }
     //判断是否是FFT还是IFFT 
     if(flag==-1)
     for(int i=0;i<n;i++)
     a[i]/=n;
}
int main(){
    n=read(); 
    scanf("%s%s",s1,s2);
    //读入的数的每一位看成多项式的一项，保存在复数的实部 
    for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
    for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
    //k表示转化成二进制的位数 
    int k=1,s=2;
    while((1<<k)<2*n-1)k++,s<<=1;
    init(k);
    //FFT 把a的系数表示转化为点值表示 
    fft(a,s,1);
    //FFT 把b的系数表示转化为点值表示 
    fft(b,s,1);
    //FFT 两个多项式的点值表示相乘 
    for(int i=0;i<s;i++)
    a[i]*=b[i];
    //IFFT 把这个点值表示转化为系数表示 
    fft(a,s,-1);
    //保存答案的每一位(注意进位） 
    for(int i=0;i<s;i++)
    {
    //取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
    ans[i]+=(int)(a[i].real()+0.5);
    ans[i+1]+=ans[i]/10;
    ans[i]%=10;
    }
    while(!ans[s]&&s>-1)s--;
    if(s==-1)printf("0");
    else
    for(int i=s;i>=0;i--)
    printf("%d",ans[i]);
    return 0;
}

后记

这篇博客写了一天，终于写完了，完结撒花✿✿ヽ(°▽°)ノ✿ FWT我来啦！！！