Fourier变换应用小记

大整数问题一直很头疼，采用乘法原理的结果复杂度为O(n2)，最近看傅里叶变换有尝试用傅里叶变换加以改进。

$$ a=(a_{N-1}a_{N-2}…a_{1}a_{0}){10}=a{N-1}10^{N-1}+…+a_{0}10^{0}] [b=(b_{N-1}b_{N-2}…b_{1}b_{0}){10}=b{N-1}10^{N-1}+…+b_{0}10^{0} $$

两个式子的乘积

c=ab=c2N−2102N−2+c2N−3102N−3+…+c1101+c0100

ck=∑i+j=kaibj,(i=0,…,N−1)

这种算法的时间复杂度为O(n2)。

逆天的是，ck居然逆天的等于ak和bk点的卷积。我们知道，卷积可以通过傅里叶变换的方式转化为普通乘法（函数卷积的傅里叶变换是函数傅里叶变换的乘积）。 于是，我们有： （1）求ai和bj的傅里叶变换（离散）Ai和Bj （2）Ai和Bj逐项相乘得到Ck （3）对Ck求傅里叶逆变换，得到ck （4）进位，出结果

对复向量xN−1,…,x1,x0，离散傅里叶变换为：

Xk=N−1∑n=0xne−2iπnkN,(k=0,…,N−1)

逆变换公式为：

xk=1NN−1∑k=0Xke−2iπknN,(n=0,…,N−1)

例： 三位数（N=3）a=456,b=987，求c=ab。 结果为：c=450072。共 6 位数字，N扩展到23=8。

a7,a6,a5,a4,a3,a2,a1,a0=0,0,0,0,0,4,5,6

b7,b6,b5,b4,b3,b2,b1,b0=0,0,0,0,0,9,8,7

ω=e−2iπN=e−2iπ8=e−iπ4=cos(−π4)+isin(−π4)=√22−i√22≈0.7−0.7i

为了方便：

ω8=ω0=1 ω9=ω1≈0.7−0.7i ω10=ω2=−i ω11=ω3≈−0.7−0.7i ω12=ω4=−1 ω13=ω5≈−0.7+0.7i ω14=ω6=i ω15=ω7≈0.7+0.7i

注意到当n>2时，an=0，于是

A0=a0×ω0×0+a1×ω1×0+a2×ω2×0=6×ω0+5×ω0+4×ω0=15 

A1=a0×ω0×1+a1×ω1×1+a2×ω2×1=6×ω0+5×ω1+4×ω2= 

A2=a0×ω0×0+a1×ω1×2+a2×ω2×2=6×ω0+5×ω2+4×ω4= 

A3=a0×ω0×0+a1×ω1×3+a2×ω2×3=6×ω0+5×ω3+4×ω6= 

A4=a0×ω0×0+a1×ω1×4+a2×ω2×4=6×ω0+5×ω4+4×ω8= 

A5=a0×ω0×0+a1×ω1×5+a2×ω2×5=6×ω0+5×ω5+4×ω10= 

A6=a0×ω0×0+a1×ω1×6+a2×ω2×6=6×ω0+5×ω6+4×ω12= 

A7=a0×ω0×0+a1×ω1×7+a2×ω2×7=6×ω0+5×ω7+4×ω14=

同样，当n>2时，bn=0，于是

B0=b0×ω0×0+b1×ω1×0+b2×ω2×0=7×ω0+8×ω0+9×ω0=24 

B1=b0×ω0×1+b1×ω1×1+b2×ω2×1=7×ω0+8×ω1+9×ω2= 

B2=b0×ω0×2+b1×ω1×2+b2×ω2×2=7×ω0+8×ω2+9×ω4= 

B3=b0×ω0×3+b1×ω1×3+b2×ω2×3=7×ω0+8×ω3+9×ω6= 

B4=b0×ω0×4+b1×ω1×4+b2×ω2×4=7×ω0+8×ω4+9×ω8= 

B5=b0×ω0×5+b1×ω1×5+b2×ω2×5=7×ω0+8×ω5+9×ω10= 

B6=b0×ω0×6+b1×ω1×6+b2×ω2×6=7×ω0+8×ω6+9×ω12= 

B7=b0×ω0×7+b1×ω1×7+b2×ω2×7=7×ω0+8×ω7+9×ω14=

于是得到Ai和Bi

A7,A6,A5,A4,A3,A2,A1,A0=,,,,,,,15 

B7,B6,B5,B4,B3,B2,B1,B0=,,,,,,,24

再求Ai和Bi的点积得到Ck：

C7,C6,C5,C4,C3,C2,C1,C0=,,,,,,,360

求Ck的离散傅里叶逆变换，令

ω=e2iπN=e2iπ8=eiπ4=cos(π4)+isin(π4)=√22+i√22≈0.7+0.7i

为了方便：

ω8=ω0=1 

ω9=ω1≈0.7+0.7i 

ω10=ω2=−i 

ω11=ω3≈−0.7−0.7i 

ω12=ω4=−1 

ω13=ω5≈−0.7+0.7i 

ω14=ω6=i 

ω15=ω7≈0.7+0.7i

于是计算ci得到：

于是获得ci，，于是ci就是大整数的计算结果。 但是可惜离散傅里叶变换的时间复杂度还是O(n2)。关键在于：直接进行离散傅里叶变换的计算复杂度是O(N2)。快速傅里叶变换可以计算出与直接计算相同的结果，但只需要O(NlogN)的计算复杂度。

部分运算结果没有写完，时间问题，改日再补。