By Long Luo
之前的文章 快速傅里叶变换(FFT)算法 和 快速傅里叶变换(FFT)算法的实现及优化 详细介绍了 FFT 的具体实现及其实现。
FFT 优点很多,但缺点也很明显。例如单位复根的实部和虚部分别是一个正弦及余弦函数,有大量浮点数计算,计算量很大,而且浮点数运算产生的误差会比较大。
如果我们操作的对象都是整数的话,其实数学家已经发现了一个更好的方法:快速数论变换 (Number Theoretic Transform) 。
快速数论变换(NTT)
FFT 的本质是什么?
是什么让 FFT 做到了 O(nlogn) 的复杂度?
那有没有什么其他的东西也拥有单位根的这些性质呢?
答案当然是有的,原根就具有和单位根一样的性质。
所以快速数论变换 NTT 就是以数论为基础的具有循环卷积性质的,用有限域上的单位根来取代复平面上的单位根的 FFT。
原根
仿照单位复数根的形式,也将原根的取值看成一个圆,不过这个圆上只有有限个点,每个点表达的是模数的剩余系中的值。
在 FFT 中,我们总共用到了单位复根的这些性质:
- n 个单位复根互不相同;
- ωnk=ω2n2k;
- ωnk=−ωnk+n/2;
- ωna×ωnb=ωna+b。
我们发现原根具有和单位复根一样的性质,简单证明:
令 n 为大于 1 的 2 的幂,p 为素数且 n∣(p−1),g 为 p 的一个原根。
我们设 gn=gnp−1:
-
gnn=gn⋅np−1=gp−1
-
gn2n=g2p−1
-
ganak=ganak(p−1)=gnk(p−1)=gnk
显然
-
gnn≡1(modp)
-
gn2n≡−1(modp)
-
(gnk+2n)2=gn2k+n≡gn2k(modp)
证毕。
所以将 gnk 和 gnk+2n 带入本质上和将 ωnk 和 ωnk+2n 带入的操作无异。
利用Vandermonde矩阵性质,类似 NTT 那样,我们可以从 NTT 变换得到逆变换 INTT 变换,设 x(n) 为整数序列,则有:
NTT : X(m)=i=0∑Nx(n)amn(modM)
INTT : X(m)=N−1i=0∑Nx(n)a−mn(modM)
这里 N−1,a−mn(modM) 为模意义下的乘法逆元。
当然, NTT 也是有自己的缺点的:比如不能够处理小数的情况,以及不能够处理没有模数的情况。对于模数的选取也有一定的要求,首先是必须要有原根,其次是必须要是 2 的较高幂次的倍数。