#include "math.h"
#include "iostream.h"
#define pi 3.141592654
void fft(double *x)
{
	int i,j,k,i1,i2,i3,i4;
	int n1=15;
	int n=16,m=4,n4;
	double xt,e,t1,t2,a,ss,cc;
   for(j=0,i=0;i<n1;i++)
   {
      if(i<j)
	  {
       xt=x[j];
	   x[j]=x[i];
	   x[i]=xt;
	  }
	  k=n/2;
	  while(k<(j+1))
	  {
	  j=j-k;
	  k=k/2;
	  }
      j=j+k;
   }
   for(i=0;i<n;i+=2)
   {
   xt=x[i];
   x[i]=xt+x[i+1];
   x[i+1]=xt-x[i+1];
   }
   int n2=1;
   for(k=2;k<=m;k++)
   {
	n4=n2;
	n2=2*n4;
	n1=2*n2;
	e=2*pi/n1;
	for(i=0;i<n;i+=n1)
	{
		xt=x[i];
		x[i]=xt+x[i+n2];
		x[i+n2]=xt-x[i+n2];
		x[i+n2+n4]=-x[i+n2+n4];
		a=e;
		for(j=1;j<=(n4-1);j++)
		{
		i1=i+j;
		i2=i-j+n2;
		i3=i+j+n2;
		i4=i-j+n1;
		cc=cos(a);
		ss=sin(a);
		a=a+e;
		t1=cc*x[i3]+ss*x[i4];
        t2=ss*x[i3]-cc*x[i4];
		x[i4]=x[i2]-t2;
		x[i3]=-x[i2]-t2;
		x[i2]=x[i1]-t1;
		x[i1]=x[i1]+t1;
		}
	}

   }


}
void main()
{
  
  double xa[16]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
  fft(xa);
  for(int i=0;i<16;i++)
  {

	  cout<<xa[i]<<endl;

  } 
}