FFT 快速傅里叶变换C++实现

#include
#include
#include
#include
using namespace std;

#define pi 3.1415926

struct complex{
public:
	double r;
	double i;
	complex（double R=0double I=0）:r（R）i（I） {}
	void setValue（double Rdouble I）{
		r=R;i=I;
	}
	double abs（）{
		return r*r+i*i;
	}
	complex operator+（const complex &a）{
		return complex（r+a.ri+a.i）;
	}
	complex operator-（const complex &a）{
		return complex（r-a.ri-a.i）;
	}
	complex operator*（const complex &a）{
		return complex（r*a.r-i*a.ir*a.i+i*a.r）;
	}
	int operator!=（const complex &a）{
		return a.r==r? （a.i==i? 1:0）:0;
	}
	void print（）{
		if（r>=0） printf（“ %.4lf“r）;
		else printf（“%.4lf“r）;
		if（i>=0） printf（“+%.4lfi“i）;
		else printf（“%.4lfi“i）;
	}
};

//旋转因子
complex W（int nint k）{
	return complex（cos（2*pi*k/n）-sin（2*pi*k/n））;
}

//L=log2（N）
int computeL（int N）{
	int L=0;
	while（N）{
		L=L+1;
		N=N>>1;
	}
	return L-1;
}

int reverse（int nint L）{
	int res=0;
	for（