博客

代码根据csdn论坛上一位达人的C++代码改编：

public class FFT {

	/** Creates a new instance of FFT */
	public FFT(int _ex) {

		ex = _ex;
		N = (int) Math.pow(2, ex);
		omegaRe = new double[N];
		omegaIm = new double[N];
		for (int k = 0; k < N; k++) {
			omegaRe[k] = Math.cos(2 * Math.PI / N * k);
			omegaIm[k] = Math.sin(-2 * Math.PI / N * k);
		}
	}

	double omegaRe[];
	double omegaIm[];
	int ex;
	int N;

	public int rev(int x) {
		int in = x;
		int ret = 0;
		for (int i = 0; i < ex; i++) {
			ret = ret | (in % 2 << ex - i - 1);
			in = in >> 1;
		}
		return ret;
	}

	public void fft(double[] inputRe, double[] inputIm, double[] outputRe,
			double[] outputIm) {

		assert (inputRe.length >= N);
		assert (inputRe.length == inputIm.length);
		assert (outputRe.length == outputIm.length);
		assert (inputR