VC++的FFT快速傅里叶变换编程设计+流程图+源代码(14)
/*输入序列对应的值*/
for(i=0;i<size_x;i++)
scanf("%lf %lf",&x[i].real,&x[i].img);
initW();
//计算W(0)~W(size_x-1)的值
fft(); //利用fft快速算法进行DFT变化
output(); //顺序输出size_x个fft的结果
return 0;
} /*进行基-2 FFT运算,蝶形算法。这个算法的思路就是先把计算过程分为log(size_x)/log(2)-1级（用i控制级数）然后把每一级蝶形单元分组（用j控制组的第一个元素起始下标）最后算出某一级某一组每一个蝶形单元（用k控制个数，共l个）。
*/
void fft()
{
int i=0,j=0,k=0,l=0;
complex up,down,product;
{
//算出j组中第k个蝶形单元
mul(x[j+k+l],W[(size_x/2/l)*k],&product); /*size/2/l是该级W的相邻上标差，l是该级该组取的W总个数*/
add(x[j+k],product,&up);
sub(x[j+k],product,&down);
x[j+k]=up;
//up为蝶形单元右上方的值