🚀 go-pugleaf

> ==> Wu_Jie(�ã���)                           ˵��: 
> c�������æ����һ����
> лл��

��ʽ�㷨���ݹ���ã������in[]�С�û�м�鳤���Dz��ǻ�2�ġ�
void FFT(complex in[],int len)
{ int i,j,k;
  complex temp1;
  complex x,y;
  if(len>2)
	{ 
	  for(i=0,j=0;i<len;i++) //divide to Two
	     {
		if(i-i/2*2)
		{ temp1=in[j];
		 for(k=j;k<len-1;k++)
		 in[k]=in[k+1];
		 in[len-1]=temp1;}
		 else {
			j++;}
	     }
	 FFT(in,len/2);
	 FFT(in+len/2,len/2);
	 for(i=0;i<len/2;i++)
	   {  x=in[i];
	      y=in[i+len/2];
	      in[i]=x+y*pow(exp(complex(0,-2*PI/len)),i);
	      in[i+len/2]=x-y*pow(exp(complex(0,-2*PI/len)),i);
	   }
	}
 else{  x=in[0];
	y=in[1];
	in[0]=x+y;
	in[1]=x-y;
	}
}

--
�� ��Դ: �й�ƴ�BBSվ [bbs.ustc.edu.cn]