fft.h

数值计算利用LU分解法来求解线性方程组,简明方便

///调换顺序
void change(complex *a,int m)
{
int nv,n,k,nv2,le;
int i;
complex t;
n=(int)pow(2,m);
nv=m;nv2=n/2;
le=nv2;
for(i=1;i<n-1;i++)
{
	if(i<=le)
	{
	t=a[le];
	a[le]=a[i];
	a[i]=t;
	}
	k=nv2;
	while(k<=le)
	{
	le=le-k;
	k=k/2;
	}
    le=le+k;
}
}
////fft-ifft
void fft(complex *a,int m,int flag)
{
	const double pai=3.1415926;
int n,le,k,N;
int i,j,l;
int ip;
double temp;
complex t;
N=(int)pow(2,m);
n=m;
le=1;
complex w;
for(i=0;i<n;i++)
{
complex u=complex(1,0);
k=le;
le=le*2;
temp=pai/k;
if (flag==1) w=complex(cos(temp),-sin(temp));
if (flag==-1) w=complex(cos(temp),sin(temp));
     for(j=0;j<k;j++)
	 {
         for(l=j;l<N;l+=le)
		 {
		 ip=l+k;
		 t=a[ip]*u;
		 a[ip]=a[l]-t;
		 a[l]=a[l]+t;
		 }
		 u=u*w;
	 
	 }
}
if(flag==1)
{
	for(i=0;i<N;i++) {a[i].real/=N;a[i].imag/=N;}

}
}