并行计算提升32K*32K点（32位浮点数） FFT计算速度（4核八线程E3处理器）

　　对32K*32K的随机数矩阵进行FFT变换，数的格式是32位浮点数。将产生的数据存放在堆上，对每一行数据进行N=32K的FFT，记录32K次fft的时间。

比较串行for循环和并行for循环的运行时间。

//并行计算
//调用openmp，通过g++ -fopenmp test.cpp -o out  编译程序
#pragma omp parallel for

    for(int i=;i<LEN;i++)

        fft(num[i],LEN,);

最终的运行时间：247，844，013 us

而串行fft,不调用openmp，它的运行时间为： 779，387，651 us

测试了，将32k*32k float型矩阵存储在堆上和栈上，并对比运行时间： 几乎没有区别。

查阅资料：栈的大小为1M， 大数组应该放在堆上，或者通过定义成全局变量/静态变量放在静态存储区。

fft算法：（该fft算法，不适合并行化处理，将来会寻找能够进行并行化的fft算法，继续改进）

void fft(complex<float> *x, int n, int inv)

{

	complex<float> u, w, t, tt;

	int m, nv2, nm1, l, le1, le, i, j, k, ip;

	m = int(log(double(n)) / log(2.) + 0.5);

	nv2 = n / 2;

	nm1 = n - 1;

	j = 0;

	for (i = 0; i<nm1; i++)

	{

		if (i >= j)   goto a;

		tt = x[j];

		x[j] = x[i];

		x[i] = tt;

	a:   k = nv2;

	b:

		if (k>j)  goto c;

		j = j - k;

		k = k / 2;

		goto b;

	c:   j = j + k;

	}

	for (l = 1; l <= m; l++){

		le = int(pow(2.0, double(l)));

		le1 = le / 2;

		u = complex<float>(1.0 , 0.0);

		w = complex<float>((float)cos(pi / le1), -(float)sin(pi / le1));

		if (inv != 0) w = conj(w);

		for (j = 0; j<le1; j++){

			for (i = j; i<n; i = le + i){

				ip = i + le1;

				t = x[ip] * u;

				x[ip] = x[i] - t;

				x[i] = x[i] + t;

			}

			u = u*w;

		}

	}

	if (inv != 0)  {

		for (i = 0; i<n; i++){

			x[i] = x[i] / float(n);

		}

	}

}