fft.java

多项式乘法运算的最短时间带价算法

/*********************************************
 *   实验五：快速傅立叶变换求多项式乘积
 *
 * 输入文件：data5.txt第一行为n的值
 *第二行为第一个多项式系数序列   第三行为第二个多项式系数序列
 *系数序列的格式为：an,an-1,an-2 ,…, a1,a0
 *数据对应教材P225 题9.7的数据
 *输入为2的n次方-1次多项式
 *输出文件：result5.txt
 *格式为结果多项式的系数序列。
 *序列格式为：an,an-1,an-2 ,…, a1,a0
 *
 *	stormchaser
 *wupeng5050309691
 *   2008.1.6
 *******************************************/
import java.io.*;
import java.util.Scanner;



public class FFT {
	class Complex {
		double real, imagine;
		Complex(double r, double i) {
			real = r;
			imagine = i;
		}

		
		public Complex add(Complex c) {
			return new Complex(real+c.real, imagine+c.imagine);
		}
		public Complex sub(Complex c) {
			return new Complex(real-c.real, imagine-c.imagine);
		}

		public Complex mult(Complex c) {
			return new Complex(real*c.real-imagine*c.imagine, imagine*c.real+real*c.imagine);
		}
		public Complex mult(double d) {
			return new Complex(real*d, imagine*d);
		}
		public Complex gong_e() {
			return new Complex(real, -imagine);
		}
	}
	int n = 0;
	Complex Res[];
	Complex in1[], in2[];
	String str_result="";
	
	//读文件
	public void readFile(String FileName) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(FileName));
		String firstLine = in.readLine();
		n = Integer.valueOf(firstLine) + 1;
		n =n* 2;
		String secondLine = in.readLine();
		String thirdLine = in.readLine();
		Scanner sc = new Scanner(secondLine);
		Scanner sc2 = new Scanner(thirdLine);
		in1 = new Complex[n];
		in2 = new Complex[n];
		for (int i = n/2-1; i >=0; i--) {
			in1[i] = new Complex(sc.nextInt(), 0);
			in2[i] = new Complex(sc2.nextInt(), 0);
		}
		for (int i=n/2;i<n;i++)
		{
		in1[i] = new Complex(0, 0);
		in2[i] = new Complex(0, 0);
		}
	}
	//写文件
	public void WriteFile(String Filename) {
		try {
			FileWriter out = new FileWriter(Filename);
			try {
				out.write(str_result);
			} finally {
				out.close();
			}
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}
	//傅立叶变换
	public Complex[] FT(int num,Complex input[]) {
		if (num <= 1)
		{
			return input;
		}
		int half=num/2;
		Complex wj = new Complex(1, 0);
		Complex w_m = new Complex(Math.cos(Math.PI*2/num), Math.sin(Math.PI*2/num));
		Complex U[] = new Complex[num-half];
		Complex W[] = new Complex[half];
		for (int i = 0; i < num; i++) {
			if (i % 2 == 0)
				U[i / 2] = input[i];
			else
				W[i / 2] = input[i];
		}
		Complex E[] = FT(num-half,U);
		Complex O[] = FT(half,W);
		Complex Result[] = new Complex[num];
		for (int k = 0; k < half; k++) {
			Result[k] = E[k].add(O[k].mult(wj));
			Result[k + num / 2] = E[k].sub(O[k].mult(wj));
			wj = wj.mult(w_m);
		}
		return Result;
	}
//反变换
	public Complex[] iFT(int num,Complex input[]) {
		Complex Result[] = new Complex[num];
		for (int i = 0; i < num; i++) 
			Result[i] = input[i].gong_e();	
		Result = FT(num,Result);
		for (int i = 0; i < num; i++)
			Result[i] = Result[i].gong_e();		
		for (int i = 0; i < num; i++)
			Result[i] = Result[i].mult(1.0 / num);	
		return Result;
	}
public int dtoi(double d)
{
	if(d>(((int)d)+0.5))
		return (int)d+1;
	else return ((int)d);
	}

	//构造函数
	public FFT(String inFileName, String outFileName) throws IOException  {		
		readFile(inFileName);
		in1 = FT(n,in1);
		in2 = FT(n,in2);
		Res = new Complex[n];
		for (int i = 0; i < n; i++) {
			Res[i] = in1[i].mult(in2[i]);
		}
		Res = iFT(n,Res);
		for (int i = n-2; i >=0; i--) {
			str_result=str_result+(dtoi(Res[i].real) + " ");
		}
		WriteFile(outFileName);
		System.out.println("输出为:");
		System.out.println(str_result);
	}

	// 主函数
	public static void main(String[] args) throws IOException {
		FFT test = new FFT("data5.dat", "result5.dat");
		System.out.println("输出文件已保存");
}


}