fft.java

一个用JAVA实现的快速傅里叶变换算法小程序

import java.io.*;
import java.util.*;

public class FFT {
	public static ArrayList<ArrayList<Integer>> a,b;
	public static int all;
	
   	public static ArrayList<ArrayList<Integer>> FFT(
			ArrayList<ArrayList<Integer>> array, int step, int begin, int total){
		if(total == 1){
			ArrayList<ArrayList<Integer>> oddarray = new ArrayList<ArrayList<Integer>>();
			oddarray.add(array.get(begin));
			return oddarray;
		}
		else{
			ArrayList<ArrayList<Integer>> u = FFT(array, step*2, begin, total/2);
			ArrayList<ArrayList<Integer>> w = FFT(array, step*2, begin+Math.abs(step), total/2);
		
			ArrayList<ArrayList<Integer>> newarray = new ArrayList<ArrayList<Integer>>();
			for(int j=0; j<total; j++) newarray.add(new ArrayList<Integer>());
			for(int j=0; j<total/2; j++){
				ArrayList<Integer> result1 = new ArrayList<Integer>();
				ArrayList<Integer> result2 = new ArrayList<Integer>();
				for(int i=0; i<all/2; i++){
					result1.add(u.get(j).get(i) + Handle(w.get(j), step*j).get(i));
					result2.add(u.get(j).get(i) - Handle(w.get(j), step*j).get(i));
				}
				newarray.set(j, result1);
				newarray.set(j+total/2, result2);	
			}
			return newarray;
		}
	}
	
	public static ArrayList<Integer> Mul(ArrayList<Integer> array1,ArrayList<Integer> array2){
		int size = array1.size();
		ArrayList<Integer> mularray = new ArrayList<Integer>();
		for(int i = 0;i < size;i++) {
			mularray.add(0);
		}
		
		for(int i = 0;i < size;i++){
			mularray.add(0);
			for(int j = 0;j < size;j++) mularray.set(j, 
					mularray.get(j)+Handle(array2,i).get(j)*array1.get(i));
		}
	return mularray;	
	}
	
	public static ArrayList<Integer> Handle(ArrayList<Integer> h,int step){
		ArrayList<Integer> temp = new ArrayList<Integer>();
		for(int i=0; i<all/2; i++) temp.add(0);
	    for(int i=0; i<all/2; i++){
	    	if(i+step >= 0){ 
	    		if(i+step < all/2) temp.set(i+step, h.get(i));
	    	else {
	    		if(i+step < all) temp.set(i+step-all/2, -h.get(i));
	    		else temp.set(i+step-all, h.get(i));
	    		}
	    	}
	    	else{
	    		if(i+step >= -all/2) temp.set(i+step+all/2, -h.get(i));
	    		else{
	    			if(i+step >= -all) temp.set(i+step+all, h.get(i));
	    			else temp.set(i+step+3*all/2, -h.get(i));
	    		}
	    	}
	    }
	    return temp;
	}
	
	//递归
	public static void main(String arg[]) throws FileNotFoundException{
		Input();
		
		PrintWriter out = new PrintWriter(new File("result5.dat"));
		
		ArrayList<ArrayList<Integer>> p = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> q = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> finalresult = new ArrayList<ArrayList<Integer>>();
		
		p = FFT(a,1,0,all);
		q = FFT(b,1,0,all);

		for(int i = 0;i < p.size();i++)	result.add(Mul(p.get(i),q.get(i)));
		
		finalresult = FFT(result,-1,0,all);
		for(int i = 0;i < p.size();i++)
			for(int j =0;j < all/2;j++) 
				finalresult.get(i).set(j,finalresult.get(i).get(j)/all);
			
		for(int i = p.size()-2;i > 0;i--) {
			out.print(finalresult.get(i).get(0));
			out.print(",");
		}
		out.print(finalresult.get(0).get(0));
		out.close();
	}
	
	public static void Input(){
		try {
			a = new ArrayList<ArrayList<Integer>>();
			b = new ArrayList<ArrayList<Integer>>();
			
			File file = new File("data5.dat");
			Scanner s = new Scanner(file);
			all = 2*Integer.parseInt(s.nextLine())+2;
			String[] t1,t2;
			String str = s.nextLine();
			t1 = str.split(" ");
			str = s.nextLine();
			t2 = str.split(" ");
			
			//建立矩阵
			for(String s1 : t1){
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(Integer.parseInt(s1));
				for(int i=0; i<all/2-1; i++) list.add(0);
				a.add(0, list);
			}
			ArrayList<Integer> tempalist1 = new ArrayList<Integer>();
			for(int i = 0;i < all/2;i++) tempalist1.add(0);
			for(int i = 0;i < t2.length;i++) a.add(tempalist1);
			
			for(String s2 : t2){
				ArrayList<Integer> list = new ArrayList<Integer>();
				list.add(Integer.parseInt(s2));
				for(int i = 0;i < all/2-1;i++) list.add(0);
				b.add(0,list);
			}
			ArrayList<Integer> tempalist2 = new ArrayList<Integer>();
			for(int i = 0;i < all/2;i++) tempalist2.add(0);
			for(int i = 0;i < t1.length;i++) b.add(tempalist2);	
			
			
		} catch (FileNotFoundException e) {
			System.out.print("输出结果到result.txt时发生错误!\n");
		}
	}
	
}