#include     <math.h>
#include     <stdio.h>
#include     <stdlib.h>
#include     "Ccomplex.h"
#include<ctime> 


const float pi=3.1415926;

void FFT(comp* xin,int z)
{
    int f,m,LH,nm,i,k,j,L;
    double p , ps ;
    int le,B,ip;
    comp v,w,t;

    LH=z/2;
    f=z;
    for(m=1;(f=f/2)!=1;m++){;}
    nm=z-2;    
    j=z/2;
    for(i=1;i<=nm;i++)
	{

        if(i<j){t=xin[j];xin[j]=xin[i];xin[i]=t;}
        k=LH;
        while(j>=k){j=j-k;k=k/2;}
        j=j+k;
	}


    for(L=1;L<=m;L++)
	{  
        le=pow(2,L);
        B=le/2; 

        for(j=0;j<=B-1;j++)
		{
             p=pow(2,m-L)*j;
             ps=2*pi/z*p;
             w.input(cos(ps),-sin(ps));
   
             for(i=j;i<=z-1;i=i+le)
			 { 
                  ip=i+B;
                  t=xin[ip]*w;
                  xin[ip]=xin[i]-t;
                  xin[i]=xin[i]+t;
			 }
		}
	}
   
return ;
} 





void IFFT(comp* xin,int z)
{
    int f,m,LH,nm,i,k,j,L;
    double p , ps ;
    int le,B,ip;
    comp v,w,t;

    LH=z/2;
    f=z;
    for(m=1;(f=f/2)!=1;m++){;}
    nm=z-2;    
    j=z/2;
    for(i=1;i<=nm;i++)
	{

        if(i<j){t=xin[j];xin[j]=xin[i];xin[i]=t;}
        k=LH;
        while(j>=k){j=j-k;k=k/2;}
        j=j+k;
	}


    for(L=1;L<=m;L++)
	{  
        le=pow(2,L);
        B=le/2; 

        for(j=0;j<=B-1;j++)
		{
             p=pow(2,m-L)*j;
             ps=2*pi/z*p;
             w.input(cos(ps),-sin(ps));
   
             for(i=j;i<=z-1;i=i+le)
			 { 
                  ip=i+B;
	              w.input(w.getreal(),-1*w.getimag());
                  t=xin[ip]*w;
                  w.input(w.getreal(),-1*w.getimag());
                  xin[ip]=xin[i]-t;
                  xin[i]=xin[i]+t;
			 }
		}
	}

 	comp tem;
	tem.input(z,0);
    for(i=0;i<z;i++)
       xin[i]=xin[i]/tem;
	
return ;
}

void FFT2(comp* xin[],int h,int l )
{
	comp* temp;
	temp=new comp[h];
	for(int i=0;i<h;i++)
		FFT(xin[i],l);
	
	for(i=0;i<l;i++)
	{
        for(int j=0;j<h;j++)
			temp[j]=xin[j][i];
		FFT(temp,h);
		for(j=0;j<h;j++)
			xin[j][i]=temp[j];
	}
		

}

void IFFT2(comp* xin[],int h,int l )
{
	comp* temp;
	temp=new comp[h];
	for(int i=0;i<h;i++)
		IFFT(xin[i],l);
	
	for(i=0;i<l;i++)
	{
        for(int j=0;j<h;j++)
			temp[j]=xin[j][i];
		IFFT(temp,h);
		for(j=0;j<h;j++)
			xin[j][i]=temp[j];
	}
		

}


void main()
{
	
	
	
	comp x[2][2],y[8];
	y[0].input(32,43);
	y[1].input(21,432);
	y[2].input(1,4);
	y[3].input(65,12);
	y[4].input(2321,12);
	y[5].input(3,7);
	y[6].input(33,45);
	y[7].input(43,44);
	FFT(y,8);
	
	IFFT(y,8);


	x[0][0].input(23,44);
	x[0][1].input(2,45);
	x[1][0].input(34,190);
	x[1][1].input(5,8);
	comp *p_number[2];
        p_number[0] = x[0];
        p_number[1] = x[1];
	FFT2(p_number,2,2);
        IFFT2(p_number,2,2);


	
}