FFT快速傅里叶变换

快速傅里叶变换——FFTyL2013-9我们关心的问题快速解决多项式乘法问题衍生问题——高精度乘法问题的描述记一个多项式次数界为n的多项式A(x)则其中a为每一项的系数注意最高次系数为n-110)(njjjxaxA问题的描述两个多项式相乘我们记一般形式为C的次数界为A与B次数界的和普通的时间复杂度为O(n^2))()()(xBxAxCPART1——中心思想1点值与插值2N次单位复数根3FFT4演示转换思路普通的相乘方法提出概念：点值，插值ijjijibac01点值与插值2N次单位复数根3FFT4演示点值一个次数界为n的多项式A(x)的点值表达就是一个由n个点值对所组成的集合：其中每一个x都不相同，且E.G.多项式的一个合法点值表达是)},(,),,(),,{(111100nnyxyxyx)(kkxAy23)(2xxxA)}12,5(),2,0{(1点值与插值2N次单位复数根3FFT4演示插值插值运算是点值运算的逆运算假设我们得到了一个有n个点值对的点值表达那我们可以确定唯一的一个次数界为n的多项式1点值与插值2N次单位复数根3FFT4演示多项式乘法我们来探究一下如何用点值与插值来完成多项式乘法我们确定一组x，求得A与B的点值表达那我们可以得知C的点值表达通过插值运算，我们可以知道多项式C的系数)},(,),,(),,{(:111100nnyxyxyxA)},(,),,(),,{(:111100nnyxyxyxB)},(,),,(),,{(:111111000nnnyyxyyxyyxC1点值与插值2N次单位复数根3FFT4演示注意的地方设A与B的次数界均为n则C的次数界为2n则我们要找出2n个x来求点值表达否则不可以进行插值运算1点值与插值2N次单位复数根3FFT4演示算法流程对于次数界均为n的多项式A与B1点值运算构造长度为2n的点值表达2逐点相乘计算出C的点值表达3插值运算通过C的点值表达求出多项式C的每项系数1点值与插值2N次单位复数根3FFT4演示时间复杂度可以证明，若选取n个x计算点值与插值的时间复杂度均为O(N^2)本质上没有解决时间的问题但我们可以巧妙的选择这些数来优化时间复杂度。1点值与插值2N次单位复数根3FFT4演示PART2——N次单位复数根及其性质1点值与插值2N次单位复数根3FFT4演示N次单位复数根n次单位复数根是满足的复数w。n次单位复数根根恰好有n个，对于k=0,1,...,n-1，这些根是。为了解释这个表达式，我们利用复数的指数形式的定义：下一页图说明n个单位复数根均匀地分布在以复平面的原点为圆心的单位半径的圆周上。1nwnike/2)sin()cos(uiueiu1点值与插值2N次单位复数根3FFT4演示N次单位复数根28w18w08w78w68w58w48wii38w},,,,{N1210nnnnn次单位复数根为我们记1点值与插值2N次单位复数根3FFT4演示性质我们需要N次单位复数根我们首先来探究这些根的性质1点值与插值2N次单位复数根3FFT4演示性质1——主n次单位根我们称为主n次单位根同时注意到，n次单位复数根都是经过旋转而得到的每次旋转都是一定角度n次单位复数根可视为公比为主n次单位根的等比数列1nnwwninin1点值与插值2N次单位复数根3FFT4演示性质2——群的性质因为所以推论10nnnwwnkjnkjnknjn)(nknknwwknknww22)(1点值与插值2N次单位复数根3FFT4演示11nnnww性质3——消去引理&折半引理....消去引理：推论：折半引理：如果n0为偶数，那么n次单位复数根的平方的集合就是n/2次单位复数根的集合。证明：可以知道的平方相同。kndkdnww122/wwnn)2/(nknknww与222222/)()(knknnnknnknnknknknww2/2)(1点值与插值2N次单位复数根3FFT4演示性质4——求和引理求和引理：对于任意整数n≥1和不能被n整除的非负整数k，有等比数列求和所以注意k不能是n的倍数，否则分母为0100)(njjknw011)1(11)(11)()(10knkknknnknnknnjjkn——FFT及其关键算法1点值与插值2N次单位复数根3FFT4演示DFT——离散傅里叶变换我们希望计算次数界为n的多项式在n次单位复数根处的值（共n个）接下来定义结果yy即为a的离散傅里叶变换（DFT）我们也可记为10)(njjjxaxA10)(njkjnjknkwawAy)(aDFTyn1点值与插值2N次单位复数根3FFT4演示FFT——快速傅里叶变换大前提：n为2的整数幂（方便计算）利用复数单位根复数根的特殊性质我们可以在时间内计算出FFT利用了分治策略)lg(nnO)(aDFTn1点值与插值2N次单位复数根3FFT4演示PART3.1——点值运算1点值与插值2N次单位复数根3FFT4演示分治策略如何求出单个数x的函数值A(x)？我们定义两个新多项式观察两个多项式的特点1分别拥有奇数下标的系数与偶数下标的系数2次数界变为n/2（缩小了一半）12/12531]1[12/22420]0[)()(nnnnxaxaxaaxAxaxaxaaxA1点值与插值2N次单位复数根3FFT4演示分治策略对于一个数x，求A(x)则根据上两个多项式)()()(2]1[2]0[xxAxAxAy1点值与插值2N次单位复数根3FFT4演示分治策略至此我们成功的转换了问题原问题：求一个多项式A(x)在的函数值。现问题：求两个多项式在的函数值。110,,,nnnn)(A)(]1[]0[xxA与212120)(,,)(,)(nnnn1点值与插值2N次单位复数根3FFT4演示分治策略现问题：求两个多项式在的函数值。根据折半引理，并不是n个不同的值，而是由n/2个n/2次单位复数根组成，而每个根恰好出现2次于是，我们递归地对n/2的多项式A[0](x)与A[1](x)在n/2个n/2次单位复数根进行求值)(A)(]1[]0[xxA与212120)(,,)(,)(nnnn212120)(,,)(,)(nnnn1点值与插值2N次单位复数根3FFT4演示程序实现1点值与插值2N次单位复数根3FFT4演示我们关心的程序实现问题1/2：规定程序递归出口3/4/12：定义主n次单位根，更新w值5/6/7/8：定义两个多项式并递归求解13：返回DFT9/10/11：递归结束后的处理工作1点值与插值2N次单位复数根3FFT4演示递归结束后的处理工作10：11：)()()(2]1[2]0[]1[]0[knknknknkknkkwAwAwwAywyy)()()()()()2/(2]1[)2/(2]0[2]1[)2/(2]0[]1[)2/(]0[]1[]0[)2/(nknnknnknnknknnknknknknkkknknkwAwAwwAwAwwAywyywyy1点值与插值2N次单位复数根3FFT4演示FFT时间复杂度对于运行时间有以下的递归式所以采用FFT，我们可以在O(nlgn)时间内实现点值运算（求出次数界为n的多项式在n次单位复数根处的值）。)lg()()2/(2)(nnOnOnTnT1点值与插值2N次单位复数根3FFT4演示PART3.2——插值运算1点值与插值2N次单位复数根3FFT4演示矩阵乘积我们可以把点值运算表示成一个矩阵方程我们把DFT写成矩阵乘积y=Vna13210)1)(1()1(3)1(21)1(3963)1(2642132113210111111111nnnnnnnnnnnnnnnnnnnnnnnnnnaaaaa1点值与插值2N次单位复数根3FFT4演示逆矩阵到此为止我们把插值运算改写成y与的逆矩阵的乘积1nnVyaaVy1nVnV1点值与插值2N次单位复数根3FFT4演示逆矩阵定理：证明比较冗长。我们证明，其中In为n*n的单位矩阵。考虑中(j,j')处的元素：如果j=j'，则此和为1否则根据求和引理，此和为0./),(1nwkjVkjnn处元素为的nnnIVV11nnVV10)(101/))(/(][nkjjknnkjknkjnjjnnnwwnwVV1点值与插值2N次单位复数根3FFT4演示逆DFT给定矩阵，可以推导出：通过比较DFT的运算我们可以看到，对FFT作以下修改就可以计算出逆DFT：把a与y互换，用，再把计算结果的每个元素除以n。于是我们也可以在O(nlgn)时间内算出逆DFT。1nV)(1yDFTn101nkkjnkjwyna10njkjnjkwaynnww代替11点值与插值2N次单位复数根3FFT4演示PART4——标程演示1点值与插值2N次单位复数根3FFT4演示程序实现优化因为像伪代码中，赋值数组是不切实际的但我们发现，a中的应用的系数是有规律的所以根据位移与起始点的不同来优化FFT的实现1点值与插值2N次单位复数根3FFT4演示程序实现优化(a0,a1,a2,a3,a4,a5,a6,a7)(a0,a2,a4,a6)(a1,a3,a5,a7)(a0,a4)(a2,a6)(a1,a5)(a3,a7)(a0)(a4)(a2)(a6)(a1)(a5)(a3)(a7)1点值与插值2N次单位复数根3FFT4演示typeNode=recordx,y:double;end;arr=array[0..200000]ofNode;operator+(a,b:Node)c:Node;beginc.x:=a.x+b.x;c.y:=a.y+b.y;end;operator-(a,b:Node)c:Node;beginc.x:=a.x-b.x;c.y:=a.y-b.y;end;operator*(a,b:Node)c:Node;beginc.x:=a.x*b.x-a.y*b.y;c.y:=a.x*b.y+a.y*b.x;end;//定义复数类型，复数运算procedureDft(vara:arr;s,t:longint);//a答案数组，s起始量，t位移量beginif(nt)=1thenexit;Dft(a,s,t+1);Dft(a,s+1t,t+1);fori:=0ton(t+1)-1dobeginj:=s+i(t+1);wt:=w[i(t)]*a[j+1t];tt[i]:=a[j]+wt;tt[i+n(t+1)]:=a[j]-wt;end;fori:=0tont-1doa[s+it]:=tt[i];end;1点值与插值2N次单位复数根3FFT4演示beginn:=1;cin(a);cin(b);fori:=0ton-1dow[i].x:=cos(pi*i*2/n);fori:=0ton-1dow[i].y:=sin(pi*i*2/n);Dft(a,0,0);Dft(b,0,0);//DFTfori:=0ton-1doa[i]:=a[i