#include "stdafx.h"
#include "dft.h"


void CDFT::DFT_MAIN (complex *f, complex *F,int N ){
	int n,k;
	complex wn;
	wn=exp(-complex(0.0,1.0)*2.0*M_PI/(double)N);
	for (k=0; k<N; k++) {
			F[k]=complex(0.0,0.0);
			for (n=0; n<N; n++)
				F[k]=F[k]+f[n]*(wn^((double)n*(double)k));
		}
	}
void CDFT::IDFT_MAIN (complex *F, complex *f,int N){
	int n,k;
	complex wn;
	wn=exp(complex(0.0,1.0)*2.0*M_PI/(double)N);
	for (k=0; k<N; k++) {
			f[k]=complex(0.0,0.0);
			for (n=0; n<N; n++)
				f[k]=f[k]+F[n]*(wn^((double)n*(double)k));
			f[k]=f[k]/(double)N;
		}
	}
void CDFT::DFT (double *f,complex *F,int N){
		int i;
		complex *x=(complex *)malloc(sizeof(complex)*N);
		for (i=0;i<N;i++)
			x[i]=*(f+i);
		DFT_MAIN (x,F,N);
	}
void CDFT::IDFT (complex *F,double *f,int N){
		int i;
		complex *x=(complex *)malloc(sizeof(complex)*N);
		IDFT_MAIN(F,x,N);
		for (i=0;i<N;i++)
			*(f+i)=x[i].re();
	}

/*debug
void main(){
	double xn[9];
	complex Xk[9];
	int i;
	for (i=0;i<9;i++)
	{
		xn[i]=(double)i;
	}
	CDFT::DFT(xn,Xk,9);
	for (i=0;i<9;i++)
		Xk[i].print();
	double xn1[9];
	CDFT::IDFT(Xk,xn1,9);
	for (i=0;i<9;i++)
		cout<<xn1[i]<<endl;
}
//debug*/