#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <complex>
using namespace std;

extern "C" double currTime();

void FFT(	complex<double> *TD,  complex<double> *FD, 
			complex<double> *X1,  complex<double> *X2,
			complex<double> *W,	  int r);

void  initTestData(complex<double> data[],int len)
{
	int i;
	for (i=0;i<len;i++)
	{
		data[i].real((double)(rand() % 1000));
		data[i].imag((double)(rand() % 1000));
	}
}

void testSpeed_fft(int maxLen)
{
	int len,r,c;
	complex<double> *omega = new complex<double>[maxLen/2];
	complex<double> *TD =	 new complex<double>[maxLen];
	complex<double> *FD =	 new complex<double>[maxLen];
	complex<double> *X1 =	 new complex<double>[maxLen];
	complex<double> *X2 =    new complex<double>[maxLen];

	FILE *fp;
	double k,t1,t2,tmp1;
	if (X1==NULL || X2==NULL)
	{
		printf("No enough memory to alloc\n");
	}
	fp=fopen("benchmark.txt","wt");
	if (fp==NULL)
		return;

	fprintf(fp,"    len  \tTotal time\ttime/(n*log2(n)\n");
	for (r=6,len=64;len<=maxLen;len*=2,r++)
	{
		t1=0.0;t2=0.0;
		c=0;
		
		initTestData(TD,len);
		
		
		while (true)
		{
		
			tmp1=currTime();
			FFT(TD,FD,X1,X2,omega,r);
			t1+=currTime()-tmp1;
			c++;
			if (t1>0.001)
				break;
		}
		t1/=c;
		k=t1/(len*log10(len)/log10(2));
		fprintf(fp,"%8d,\t%.8f \t%.12f\n",len,t1,k);
	}
	fclose(fp);
	delete[] TD;
	delete[] FD;
	delete[] X1;
	delete[] X2;
	delete[] omega; 
}

int main()
{
	testSpeed_fft(2*1048576);
	return 0;
}