omega.java

用java编写的用蝶式算法实现的fft

package project;

public class Omega {
	private int[] result;
	
	public Omega(int[] array1, int[] array2) {
		
		int[] a1 = Reverse_LengthDouble(array1);
		Complex[] V1 = Recusive_FFT(a1);
		int[] a2 = Reverse_LengthDouble(array2);
		Complex[] V2 = Recusive_FFT(a2);

		if (V1.length != V2.length) {
			System.out.println("Error!");
			System.exit(0);
		}

		Complex[] V = new Complex[V1.length];
		for (int i = 0; i < V1.length; i++)
			V[i] = Complex.multiply(V1[i], V2[i]);
		Complex[] r;
		r = Ob_Recusive_FFT(V);

		this.result = new int[r.length];
		for (int i = 0; i < this.result.length; i++)
			this.result[i] = ((int) r[r.length - i - 1].getReal() / r.length);
	}

	public int[] Reverse_LengthDouble(int[] a) {
		int n = a.length;
		int[] r = new int[n * 2];
		for (int i = 0; i < n; i++)
			r[n - i - 1] = a[i];
		return r;
	}
	
	public void PaintArray(int[] a) {
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i]);
	}

	public void PaintArray(Complex[] a) {
		for (int i = 0; i < a.length; i++)
			System.out.print((int) a[i].getReal() / a.length);
	}

	public Complex[] Ob_Recusive_FFT(Complex[] y) {
		int n = y.length;
		Complex[] a = new Complex[n];
		if (n == 1) {
			Complex[] p = new Complex[1];
			p[0] = new Complex(y[0]);
			return p;
		}
		Complex Wn = new Complex();
		Complex w = new Complex(1, 0);
		Wn.setReal(Math.cos(Math.PI * 2 / n));
		Wn.setImag(Math.sin(Math.PI * 2 / n));
		Wn = Complex.divide(new Complex(1, 0), Wn);

		Complex[] y1 = new Complex[n / 2];
		Complex[] y2 = new Complex[n / 2];
		int j = 0;
		int k = 0;
		for (int i = 0; i < y.length; i++) {
			if (i % 2 == 0) {
				y1[j] = new Complex(y[i]);
				j++;
			} else {
				y2[k] = new Complex(y[i]);
				k++;
			}
		}
		Complex[] a1 = Ob_Recusive_FFT(y1);
		Complex[] a2 = Ob_Recusive_FFT(y2);
		for (k = 0; k < n / 2; k++) {
			a[k] = Complex.add(a1[k], Complex.multiply(a2[k], w));
			a[k + n / 2] = Complex.minus(a1[k], Complex.multiply(a2[k], w));
			w = Complex.multiply(w, Wn);
		}
		return a;
	}

	public Complex[] Recusive_FFT(int[] a) {
		int n = a.length;
		if (n == 1) {
			Complex[] p = new Complex[1];
			p[0] = new Complex(a[0], 0);
			return p;
		}
		Complex[] y = new Complex[n];
		Complex Wn = new Complex();
		Complex w = new Complex(1, 0);
		Wn.setReal(Math.cos(Math.PI * 2 / n));
		Wn.setImag(Math.sin(Math.PI * 2 / n));
		int[] a1 = new int[n / 2];
		int[] a2 = new int[n / 2];
		int j = 0;
		int k = 0;
		for (int i = 0; i < a.length; i++) {
			if (i % 2 == 0) {
				a1[j] = a[i];
				j++;
			} else {
				a2[k] = a[i];
				k++;
			}
		}
		Complex[] y1 = Recusive_FFT(a1);
		Complex[] y2 = Recusive_FFT(a2);
		for (k = 0; k < n / 2; k++) {
			y[k] = Complex.add(y1[k], Complex.multiply(y2[k], w));
			y[k + n / 2] = Complex.minus(y1[k], Complex.multiply(y2[k], w));
			w = Complex.multiply(w, Wn);
		}
		return y;
	}

	public int[] getResult() {
		return result;
	}
}