快速傅里叶算法的原理实现及分析

1、快速傅里叶算法的原理实现及分析FFT的原理：多项式的表示：系数表示：A(x)=aj*xj;点值表示：A(x): ( x0, y0), ( x1, y1 ), ( xn-1, yn-1 ) ;其中yk = A( xk );求值计算的逆：对于任意n个点值对组成的集合 ( x0, y0), ( x1, y1 ), ( xn-1, yn-1 ) ，其中所有的xk都不同；那么存在唯一的次数界为n的多项式A(x)，满足yk = A( xk )，k = 0,1,n-1；【证明略】拉格朗日插值法：因此，n个点的求值运算与插值运算是定义完备的互逆运算，它们将多项式的系数表达与点值表达进行相互转化。当我们用系数表

2、达表示多项式时，多项式乘法的最直接算法所需运行时间为(n2)，但采用点值表达，运行时间仅为(n)。然而，我们通过对这两种表示法进行转换，采用系数表达求多项式乘积，可以使运行时间变为(nlogn)。FFT图解：C(w02n)C(w12n).C(w02n)C(w12n).C(w2n-12n)A(w02n),B(w02n)A(w12n),B(w12n)A(w2n-12n),B(w2n-12n)a0,a1,an-1b0,b1,bn-1c0,c1,cn-1加倍次数界：通过加入n个系数为0的高阶系数，把多项式A(x)和B(x)变为次数界为2n的多项式，并构造其系数表达；求值：通过应用2n阶的FFT计算出A

3、(x)和B(x)的长度为2n的点值表达。这些点值中包含了两个多项式在2n次单位根处的取值；逐点相乘：把A(x)的值和B(x)的值逐点相乘，可以计算出多项式C(x)=A(x)*B(x)的点值表达，这个表示中包含了C(x)在每个2n次单位根处的值；插值：通过对2n个点值对应用FFT，计算其逆DFT，就可以构造出多项式C(x)的系数表达； 执行第1步和第3步所需时间为(n)，执行第2步和第4步所需时间为(nlogn)。因此，一旦表明如何运用FFT，我们就已经证明了：当输入与输出多项式均采用系数表达时，我们就能在(nlogn)时间复杂度内，计算出两个次数界为n的多项式乘积。快速傅里叶变换：A0(x)

4、= a0+a2*x+a4*x2+an-2*x(n/2-1)A1(x) = a1+a3*x+a5*x2+an-1*x(n/2-1)而A(x) = A0(x2) + x*A1(x2)；伪代码：RECURSIVE-FFT(a)n = a.length/n is a power of 2if n=1return awn=2i/nw=1a0=(a0,a2,an-2)a1=(a1,a3,an-1)y0=RECURSIVE-FFT(a0)y1=RECURSIVE-FFT(a1)for k=0 to n/2-1yk=yk0+w*yk1yk+n/2=yk0-w*yk1w=w*wnreturn y/y is as

5、sumed to be a column vectorFFT的迭代实现：函数原型：注：在处理时，大小必须为2的幂；FFT的迭代实现：自底向上实现logn次每次n/2的蝴蝶操作，并用中间变量u、t减少计算次数，用count计算乘法/加法次数；逆FFT的实现：与FFT基本相同，注：此时wm是反向且最后须除以SIZE得到正解；其它小细节的实现：bit_reverse通过逆序操作使得可以自底向上进行FFT/IFFT操作；rev则是按照logn大小进行逆序；print输出多项式结果（实数多项式相乘仍得实数多项式，因此丢弃复数部分），同时也可以在debug时输出中间点对检查是否有误；测试用例及性能分析：小

6、测试时键盘输入检查正误，大数据时从文本读入随机数；小例子：随机数输入：性能分析：n825610242048819216384Count3630721536033792159744344064复数加法7261443072067584319488688128复数乘法7261443072067584319488688128数据拟合：则T(n)=1.5*nlogn-2.19e-12*n-3.15e-12*logn+9.48e-12；而e-121的情形下，其需要4NlogN-6N+8个乘法运算以及加法运算。最近有人导出更低的运算量：34/9*NlogN。（Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007）大多数尝试要降低或者证明FFT复杂度下限的人都把焦点放在复数资料输入的情况，因其为最简单的情形。但是，复数资料输入的FFT算法，与实数资料输入的FFT算法，离散余弦转换（DCT），离散哈特列转换（DHT），以及其他的