Java/計算機科学/その他/FFT - mattyalib @ ウィキ

高速フーリエ変換

言語：Java
参照ライブラリ：Complex

public class FFT {
	/**
	 * 順変換。規格化は1/sqrt(n)
	 * @param f 変換前
	 * @return 変換後
	 */
	public static Complex[] exec(Complex[] f){
		int n = f.length;
		Complex[] ret = new Complex[n];
		Complex[] w = new Complex[n];
		for(int i=0; i<n; i++){
			w[i] = new Complex(Math.cos(2.0*Math.PI*i/(double)n), Math.sin(2.0*Math.PI*i/(double)n));
//			System.out.println(w[i]);
		}
 
		//ならびかえ
		for(int i=0; i<n; i++){
			int k = 0;
			for(int j=1; j<n; j*=2){
				k*=2;
				if((j&i)!=0) k+=1;
			}
			ret[i] = f[k];
		}
 
		Complex[] tmp = new Complex[n];
		for(int i=1; i<n; i*=2){
			for(int j=0; j<n; j+=(i*2)){
				for(int k=j; k<i+j; k++){
					tmp[k] =   ret[k].add( ret[k+i].mul(w[(n/i/2)*(k-j)]) );
					tmp[k+i] = ret[k].add( ret[k+i].mul(w[(n/i/2)*(k-j)+(n/2)]) );
				}
			}
			for(int j=0; j<n; j++){
				ret[j] = tmp[j];
			}
		}
 
		for(int i=0; i<n; i++){
			ret[i].muleq(1.0/Math.sqrt(n));
		}
		return ret;
	}
 
	/**
	 * 逆変換。規格化は1/sqrt(n)
	 * @param f 変換前
	 * @return 変換後
	 */
	public static Complex[] inv(Complex[] f){
		int n = f.length;
		Complex[] ret = new Complex[n];
		Complex[] w = new Complex[n];
		for(int i=0; i<n; i++){
			w[i] = new Complex(Math.cos(2.0*Math.PI*(-i)/(double)n), Math.sin(2.0*Math.PI*(-i)/(double)n));
		}
 
		//ならびかえ
		for(int i=0; i<n; i++){
			int k = 0;
			for(int j=1; j<n; j*=2){
				k*=2;
				if((j&i)!=0) k+=1;
			}
			ret[i] = f[k];
		}
 
		Complex[] tmp = new Complex[n];
		for(int i=1; i<n; i*=2){
			for(int j=0; j<n; j+=(i*2)){
				for(int k=j; k<i+j; k++){
					tmp[k] =   ret[k].add( ret[k+i].mul(w[(n/i/2)*(k-j)]) );
					tmp[k+i] = ret[k].add( ret[k+i].mul(w[(n/i/2)*(k-j)+(n/2)]) );
				}
			}
			for(int j=0; j<n; j++){
				ret[j] = tmp[j];
			}
		}
 
		for(int i=0; i<n; i++){
			ret[i].muleq(1.0/Math.sqrt(n));
		}
		return ret;
	}
 
}