main.java

快速傅立叶变换算法的实现

package ex4_fast_fourier_transform;

import java.io.IOException;
import java.math.BigDecimal;
/*
 * This program is the achieve of the Fast_Fourier_Transform.
 * The time cost is O(nlogn).
 * The space cost is O(n^2).
 */
public class Main {
	int[] a;// a[] stores the coefficients of the first polynomial with a bigger
	// size
	int[] b;// b[] stores the coefficients of the second polynomial with a
	// bigger size
	int n;// n stores the highest coefficient of the polynomial
	String[] as;// as[] get the data in Filereader
	int m;// m=2^h is the smallest number which is bigger than 2n+1;
	Complex_number[] V;// V[] is the first [p(1),.....,p(w^(n-1)]]
	Complex_number w;// w is the primitive nth root of unity
	Complex_number[] V2;// V[] is the second [p(1),.....,p(w^(n-1)]]
	BigDecimal   fi;//fi is used to transform double to the nearest number which has one decimal

	public Main() throws IOException {
		StringBuffer sb = new StringBuffer();//sb and s are for output
		String s;
		Fileoutput out = new Fileoutput();
		Filereader file = new Filereader("data_ex4_fft\\data3.txt");
		n = file.getn();
		as = new String[n * 2 + 3];
		as = file.getlist();
		m = getm(n);
		V = new Complex_number[m];
		V2 = new Complex_number[m];
		for (int i = 0; i < V.length; i++) {
			V[i] = new Complex_number();
			V2[i] = new Complex_number();
		}
		w = new Complex_number();

		w.real = Math.cos(Math.PI * 2 / m);
		w.imagi = Math.sin(Math.PI * 2 / m);

		a = new int[m];
		b = new int[m];
		for (int i = 0; i < a.length; i++) {
			if (i < n + 1) {
				a[i] = Integer.parseInt(as[n + 1 - i]);
			} else {
				a[i] = 0;
			}
		}
		for (int i = 0; i < b.length; i++) {
			if (i < n + 1) {
				b[i] = Integer.parseInt(as[n * 2 + 2 - i]);
			} else {
				b[i] = 0;
			}
		}
		for (int i = 0; i < V.length; i++) {
			V[i].real = a[i];
			V[i].imagi = 0;
		}
		V = Fast_Fourier_Transform(m, V, w);
		for (int i = 0; i < V2.length; i++) {
			V2[i].real = b[i];
			V2[i].imagi = 0;
		}
		V2 = Fast_Fourier_Transform(m, V2, w);
		// multiply the two polynomials' points
		for (int i = 0; i < m; i++) {
			V2[i] = V2[i].mult(V[i]);
		}
		// w=1/w
		w.imagi = -w.imagi;
		w.real = w.real;
		V2 = Fast_Fourier_Transform(m, V2, w);
		double p = 1;
		double q = m;
		Complex_number t = new Complex_number(p / q, 0);
		for (int i = 0; i < V2.length; i++) {
			V2[i] = V2[i].mult(t);
		}
		for (int i = 2*n; i >=0; i--) {
			fi=new BigDecimal(V2[i].real);
			fi=fi.setScale(0,BigDecimal.ROUND_HALF_UP);//this can expansion to any size you want
			System.out.println("A[" + i + "]=" + fi);
			sb.append(fi+" ");
		}
		s=sb.toString().trim();
		out.output(s, "data_ex4_fft\\result3.txt");
	}

	// return m (m=2^h is the smallest number which is bigger than 2n+1)
	public int getm(int n) {
		int i = 1;
		while (i < 2 * n + 1) {
			i = i * 2;
		}
		return i;
	}

	public Complex_number[] Fast_Fourier_Transform(int n, Complex_number[] a,
			Complex_number w) {
		if (n == 1) {
			return a;
		} else {
			Complex_number[] U = new Complex_number[n / 2];
			Complex_number[] W = new Complex_number[n / 2];
			Complex_number[] a1 = new Complex_number[n / 2];
			Complex_number[] a2 = new Complex_number[n / 2];
			for (int i = 0; i < a1.length; i++) {
				a1[i] = new Complex_number(a[i * 2].real, a[i * 2].imagi);
				a2[i] = new Complex_number(a[i * 2 + 1].real,
						a[i * 2 + 1].imagi);
			}
			for (int i = 0; i < U.length; i++) {
				U[i] = new Complex_number();
			}
			for (int i = 0; i < W.length; i++) {
				W[i] = new Complex_number();
			}
			Complex_number v = new Complex_number();// v=w*w
			v = w.mult(w);
			U = Fast_Fourier_Transform(n / 2, a1, v);
			W = Fast_Fourier_Transform(n / 2, a2, v);
			double angle;
			if (w.real < 0) {
				angle = Math.atan(w.imagi / w.real) + Math.PI;
			} else {
				angle = Math.atan(w.imagi / w.real);
			}
			for (int i = 0; i <= n / 2 - 1; i++) {
				// calculate v= w^i
				double p = i;
				v.real = Math.cos(angle * p);
				v.imagi = Math.sin(angle * p);
				Complex_number temp1 = new Complex_number();
				Complex_number temp2 = new Complex_number(-1, 0);
				temp1 = v.mult(W[i]);
				a[i] = U[i].add(temp1);
				temp2 = temp1.mult(temp2);
				a[i + n / 2] = U[i].add(temp2);
			}
			return a;
		}
	}

	public static void main(String[] argvs) throws IOException {
		new Main();
	}
}