FFT、NTT 算法浅析
FFT(快速傅里叶变换)和 NTT(快速数论变换)的浅显讲解。
前言
FFT(快速傅里叶变换)和 NTT(快速数论变换),常用于高效解决多项式乘法问题。初次听见这两个名字时,你可能会觉得这两个算法很厉害,但是很难,我也是这么认为的。就让我来为你浅显易懂地讲解这两个算法(以理解为主,严谨证明较少)。
前置知识
你需要了解分治、多项式、函数、复数的相关概念。为了学习 NTT,还需了解数论中的素数、取模、同余等概念,之后便可进入本文的学习。
FFT 的目标
两个多项式 和 要相乘,朴素的做法是逐项分别相乘,时间复杂度 。FFT 就是一种优化的算法,使得多项式相乘的时间复杂度降至 。
FFT 的大致原理
先介绍以下几个基本结论或者定理:
- 平面上给定 个点( 坐标互不相同),可以唯一确定一个次数不超过 的多项式。
- 一个次数不超过 的多项式 可以被视作一个次数不超过 的多项式 ,只要 到 均为 就行了。
- 长度为 和 的多项式相乘,其结果长度不超过 。
FFT 的做法就是:对于两个多项式 ,取 个不同的 坐标(其中 ),对于每一个 坐标求出其对应的多项式值 和 ,这样我们就有了 个点。然后把同样 坐标的两个点的 坐标相乘,产生乘积 个点,之后我们通过乘积的 个点还原出多项式,即为 的结果。
FFT 的高妙之处在于,通过选取合适的 坐标,使得产生 个点以及把 个点还原成多项式的过程都在 的时间内完成。
单位根
初次接触单位根,可能不知道它是干什么用的,但是这玩意确实在 FFT 中有很大用处。
一个数满足 ,就称它为 次单位根。本文用 表示其中逆时针走一步的那个单位根,全部 个单位根就是 。当 时,单位根为 ,当 时,单位根为 。
单位根的分布在复平面上是有规律的,以 次单位根为例,如下图, 个单位根都分布在单位圆上,且把这个圆平均分。

单位根有哪些性质呢?假设从 开始,逆时针走到下一个单位根,叫做走一步。那么 就是走半圈,数值会变成原来的相反数。走完整整一圈,我们又回到了起点。这些独特的性质正是 FFT 的关键。
那么什么运算可以从一个单位根走一步到达另一个单位根呢?把复数看成从原点出发的向量,你会发现复数的乘法运算就是模长相乘,辐角相加(前置知识中假设你已经了解复数相关运算,这里不再详细介绍)。因此乘以一个 ,相当于逆时针旋转 ,就是所谓的走一步。
上面不是提到会选取 个 坐标吗?傅里叶这个大佬非常的聪明,选取了复数集中的单位根作为上面提到的 坐标。由于有 个 坐标,就会选取 个 次单位根。并且单位根的特殊性质,可以使得它们大大减小 FFT 的计算量。
FFT 的分治思路
考虑求一个多项式 以 次单位根作为 输入的情况下,多项式的值(这里 是 的幂)。把多项式按照下标的奇偶性拆成两部分: 以及 。
设三个函数 ,,。然后发现,这个 可以由后面两个式子算出来,也就是 。你可以自己算一下,这个等式是成立的。这样我们就把求长度为 的多项式的值转化成求两个长度为 的多项式的值,最后合并起来,这就是典型的分治思想。
你可能会疑惑:算一次 要用 的时间复杂度,有 个单位根要算,总时间复杂度 ,不是反而更慢了吗?不是这样的,FFT 中不是逐个把单位根代入多项式去算,而是同时算这 个单位根的值,时间复杂度也是 。假设你知道两个长为 的子式子分别以 作为 的情况下,多项式的值,一共 个,是有办法求出长为 的父式子分别以 作为 的情况下,多项式的值。求这个的时间复杂度是 。和归并排序类似,都是分成两个规模为一半的子问题,合并耗时 ,因此总时间复杂度依然为 。
蝴蝶运算
蝴蝶运算是 FFT 最核心以及最难理解的操作,非常重要。上面提到 FFT 可以 合并两个子问题的结果,就是通过蝴蝶运算进行的。
介绍以下基本的结论或定理:
- (理由:根据图像,“分成 份,走 步”和“分成 份,走 步”,走到的地方是一样的)
- (理由:根据图像,从一半开始走 步和从起点开始走 步,走到的位置相反)
然后呢,把 和 分别代入上文提到的式子 中。
第一个值代入:
第二个值代入:
先算 。
至此,对于任意 ,我们都能在计算完所有 规模的子问题的情况下, 同时计算出 和 的值。这样的 一共有 个,因此合并过程的时间复杂度为 。
逆 FFT
我们已经解决了对于每一个 坐标求出其对应的多项式值,还需解决通过每一个 坐标对应的多项式值还原出多项式。这需要用到逆 FFT。
你可能会想:既然正向 FFT 是把系数变成点值,那么反过来还原系数,是不是得重新发明一种算法?其实不用。把单位根反过来走,再把每个结果除以 ,就能用几乎同一套 FFT 算法完成还原。为什么这样做是对的呢?
设原来的多项式为 ,正向 FFT 算出的第 个点值记作 。把多项式展开,就有:
现在假设我们要找回第 个系数 。把所有点值 分别乘以 ,再加起来:
先看括号里的东西。如果 ,每一项都是 ,加起来就是 ;如果 ,这一项会沿着单位圆等间隔地转,转满一圈后总和为 。比如走四个方向时,。哪怕不是恰好把每个单位根都走一遍,只要不是一直待在 ,绕圈得到的数加起来仍然为 。于是,别的系数全都互相抵消,只剩下 :
这也解释了为什么单位根要反方向走:正向计算时, 对第 个点值的贡献带着 ;还原 时乘上 ,指数就变成了 。当 时,两次旋转正好抵消;其他系数则沿圆周转动,相加后消失。如果还照着原来的方向走,指数就会变成 ,不能按原来的下标把系数找回来。
这里的 就是 的倒数,也就是它的共轭复数。在单位圆上乘以它,相当于顺时针走一步。所以实现逆 FFT 时,只要把正向 FFT 中用到的单位根换成反方向的单位根,再对输出的每个数除以 即可。除以 不是额外的技巧:目标系数在上面的求和中被保留了 次,所以必须除以 ,才能从 得到 。
FFT 的具体实现
上面我们提到的分治做法用递归做起来比较容易理解,但是时间和空间常数较大,可以把它改成自底向上递推的形式。
看一个序列 ,按照奇偶性分成两组,分别是 和 。接着分,是 、、、。再分一次得到单个元素,顺序就是 。
转换成二进制形式,原始序列:。
最终序列:。
发现什么规律了吗?每个数在二进制下都前后反转了!因此我们可以通过这个快速求出原始序列对应的最终序列。
for(int i=1,j=0;i<n;i++){
int bit=n>>1;
for(;j&bit;bit>>=1)j^=bit;
j^=bit;//这是一种计算出二进制下反转后数字的神奇方式
if(i<j)swap(a[i],a[j]);//把原数字和反转后数字调换位置
}
从 一直到 枚举多项式的长度,先算小规模问题,之后根据小规模问题的答案合并出大规模问题的答案。代码中的 a 数组就是暂存答案用的。
以下是完整参考代码:
#include<bits/stdc++.h>
using namespace std;
using cd=complex<double>;
const double pi=acos(-1.0);
const int N=3e6+5;
int n,m,a[N],b[N],siz=1;
cd aa[N],bb[N],c[N<<1];
void fft(cd *a,int f){
for(int i=1,j=0;i<siz;i++){//奇偶拆分
int bit=siz>>1;
for(;j&bit;bit>>=1)j^=bit;
j^=bit;
if(i<j)swap(a[i],a[j]);
}
for(int len=2;len<=siz;len<<=1){
double angle=pi*2/len*f;//一次旋转的角度
cd wlen(cos(angle),sin(angle));//单位根
//这里的cos和sin相当于在x和y轴上投影
for(int i=0;i<siz;i+=len){//起始位置
cd w(1,0);//旋转因子
int mid=len>>1;
for(int j=0;j<mid;j++){//蝴蝶运算
cd u=a[i+j];
cd v=a[i+j+mid]*w;
a[i+j]=u+v;
a[i+j+mid]=u-v;
w*=wlen;//走一步
}
}
}
if(f==-1)//逆FFT
for(int i=0;i<siz;i++)
a[i]/=siz;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
n++,m++;
while(siz<n+m-1)siz<<=1;
for(int i=0;i<n;i++)cin>>a[i],aa[i]=cd(a[i],0);
for(int i=0;i<m;i++)cin>>b[i],bb[i]=cd(b[i],0);
fft(aa,1);
fft(bb,1);
for(int i=0;i<siz;i++)
c[i]=aa[i]*bb[i];
fft(c,-1);
for(int i=0;i<n+m-1;i++)
cout<<(int)(c[i].real()+0.5)<<' ';
return 0;
}
模意义下的改进:NTT
前面我们已经讲完了 FFT,现在来看 NTT。你可能会觉得,名字都变了,算法是不是也要从头学一遍?其实不用。NTT 可以理解成把 FFT 中的复数运算,换成模一个质数后的整数运算。奇偶拆分、蝴蝶运算、最后的逆变换,思路几乎一样。最大的疑问反而是:FFT 用复平面上的单位根转圈,模意义下哪来的圆?
先别管圆长什么样。回想一下,前面推蝴蝶运算时,我们真正用到的是单位根的几个性质:走 步回到 ,中途不提前回到 ;走半圈到 ;每走两步相当于小一半问题中的一步。如果模意义下也能找出满足这些性质的数,那么原来的推导就仍然成立。NTT 中的数不是真的排在复平面的圆上,“走一步”只是一种帮助理解乘方和取模的比喻。
模意义下怎样转圈
先用小一点的模数看看。模 时,取 ,不断乘 并取模:
发现了吗?它把 到 都走了一遍,第 步才回到 。我们称 为模 的原根。一般地,对于质数 ,如果 的幂模 后能遍历 ,也就是说最早在第 步回到 ,那么 就是模 的原根。这个“最早在第几步回到 ”也叫做 的阶。
这里有个很像 FFT 的现象:上面序列的前半段是 ,后半段是 ,对应的数相加都是 。在模 下,它们的和就是 ,所以后半段正好是前半段的相反数。这可不是巧合:
为什么走到一半一定是 呢?设 是模奇质数 的原根,令 。再走半圈就回到 ,因此 。因为 是质数, 只能说明 或 。但如果半圈就走回 , 就不配叫原根了,因此只能是 。这和复数单位根走半圈变成相反数,是同一个蝴蝶运算需要的性质。
原根和模数的来历
模 的例子虽好,却没法做很长的 NTT。实际写代码时常选模数 ,它是质数,而且:
是模 的原根,它转完整一圈需要 步。假设我们只需要长度为 的变换,也就是想要一个“走 步一圈”的单位根,该怎么办?每一步不要只走原来的 步,而是跳 步:
这样走 步,就是把 乘了 次,正好回到 。而且中途不会提前回去:假如走了 步就回到 ,那么 ;由于 原本必须走满 步才能回到 ,只能有 。所以 的阶恰好是 ,而不只是“走 步时碰巧回来了”。
注意这里要求 能整除 ,否则“每次跳 步”就没法这样构造。例如长度 时,直接取 ,不必非要用 步的大圈。又因为 中有 这个因子,前面讲的二分蝴蝶运算可以支持 ,其中 。 是这个模数下二的幂长度的上限,不是每次都必须取的长度。做多项式乘法时,仍然选取不小于结果长度的最小的二的幂,只是这个长度还不能超过 。
你可能会继续问:上面说的几个性质真的都有吗?当 是大于 的二的幂时,由于 ,有:
另外,把大圈每两步合成一步,就有:
这不就是前面推 FFT 蝴蝶运算用到的两个式子吗?因此,在 NTT 中照样先算 和 ,再通过一加一减得到父问题的两个值。只不过现在每次加、减、乘都要对 取模。
逆 NTT
逆 FFT 用反方向的单位根,最后除以 ;逆 NTT 也是一样的。模意义下的“反方向走一步”就是乘以 的乘法逆元,记作 ,它满足 。由于 ,也可以把它写成 。
不过在模 下,“除以 ”可不能直接用普通整数除法,而应该乘以 的模 逆元。因为 且 是质数,费马小定理给出:
原理和前面的逆 FFT 完全一致:反方向走使其他系数相互抵消,目标系数剩下 份;乘以 ,才能把它还原成一份。这里也能用前文的等比数列验证:对于非目标系数,取 ,则 ,因此 。因为模质数时非零的 有逆元,所以括号中的和仍是 。
NTT 的具体实现
如果你已经写过 FFT,实现 NTT 时保留位反转和蝴蝶运算的框架,把 complex<double> 改成模 的整数,把按角度计算的单位根改成快速幂计算的单位根,再把所有运算改成取模即可。下面这段代码的输入和常见 FFT 乘法模板一样:先输入两个多项式的次数,再输入系数;输出的每个系数都是模 的结果。
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5,P=998244353;
int n,m,a[N],b[N],c[N<<1],siz=1,inv;
int qpow(int a,int b){//快速幂
long long res=1;
while(b){
if(b&1)res=(res*a)%P;
a=(1ll*a*a)%P;
b>>=1;
}
return res;
}
void fft(int *a,int f){
for(int i=1,j=0;i<siz;i++){//奇偶拆分
int bit=siz>>1;
for(;j&bit;bit>>=1)j^=bit;
j^=bit;
if(i<j)swap(a[i],a[j]);
}
for(int len=2;len<=siz;len<<=1){
int omega=qpow(3,(P-1)/len);//单位根
if(f==-1)omega=qpow(omega,P-2);//逆单位根
for(int i=0;i<siz;i+=len){//起始位置
int w=1,mid=len>>1;
for(int j=0;j<mid;j++){//蝴蝶运算
int u=a[i+j];
int v=(1ll*a[i+j+mid]*w)%P;
a[i+j]=u+v;
if(a[i+j]>=P)a[i+j]-=P;
a[i+j+mid]=u-v;
if(a[i+j+mid]<0)a[i+j+mid]+=P;
w=(1ll*w*omega)%P;
}
}
}
if(f==-1)
for(int i=0;i<siz;i++)
a[i]=(1ll*a[i]*inv)%P;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
n++,m++;
while(siz<n+m-1)siz<<=1;
inv=qpow(siz,P-2);//计算P的逆元
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
fft(a,1);
fft(b,1);
for(int i=0;i<siz;i++)
c[i]=(1ll*a[i]*b[i])%P;
fft(c,-1);
for(int i=0;i<n+m-1;i++)
cout<<c[i]<<' ';
return 0;
}
后记
至此,你已经理解了 FFT(快速傅里叶变换)和 NTT(快速数论变换),可以去做题了。