#include <math.h>
#include <iostream.h>
#define M 4
#define pi 3.141592653
//#define fs 8000
struct compx{float real,imag;};
struct compx EE(struct compx,struct compx);
struct compx EE(struct compx a,struct compx b)
{
struct compx c;
c.real=a.real*b.real-a.imag*b.imag;
c.imag=a.real*b.imag+a.imag*b.real;
return c;
}
void FFT(struct compx *xin, int N)
{
int f,m,nm1,i,k,j=1,I;
struct compx v,w,t;
f=N;
for(m=1;(f=f/2)!=1;m++) {;}
nm1=N-1;
for(i=1;i<=nm1;i++)
{
if(i<j)
{
t=xin[j];xin[j]=xin[i];xin[i]=t;
}
k=N/2;
while(k<j) {j=j-k;k=k/2;}
j=j+k;
}
{
int le,lei,ip;
for(I=1;I<=m;I++)
{
le=int(pow(2,I));
lei=le/2;
v.real=1.0;
v.imag=0.0;
w.real=float(cos(pi/lei));
w.imag=float(-sin(pi/lei));
for(j=1;j<=lei;j++)
{
for(i=j;i<=N;i=i+le)
{
ip=i+lei;
t=EE(xin[ip],v);
xin[ip].real=xin[i].real-t.real;
xin[ip].imag=xin[i].imag-t.imag;
xin[i].real=xin[i].real+t.real;
xin[i].imag=xin[i].imag+t.imag;
}
v=EE(v,w);
}
}
}
}
void main()
{
struct compx x[M+1];
cout<<"The input array is:\n";
for(int i=1;i<=M;i++)
{
//x[i].real=float(cos(2*pi*i*3500/fs));
x[i].real=float(i);
x[i].imag=0;
cout<<x[i].real<<"+j*"<<x[i].imag<<"\n"<<endl;
}
struct compx *p=x;
FFT(p+1,M);
cout<<"The result of FFT:\n";
for(i=1;i<=M;i++)
cout<<x[i].real<<"+j*"<<x[i].imag<<"\n"<<endl;
}
