みけCATのにっき（仮）
つれづれなるまゝに、日くらし、PCにむかひて、心に移りゆくよしなし事を、そこはかとなく書きつくれば、あやしうこそものぐるほしけれ。
（本当か！？）
出典

高速離散フーリエ変換(仮)

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

高速離散フーリエ変換(仮)

投稿記事 by みけCAT » 11年前

●離散フーリエ変換
入力に三角関数を掛けたものの和をとっていくだけで、音声データをいい感じのグラフに変換できる。
実装も単純な二重ループで、超簡単。

●高速フーリエ変換
離散フーリエ変換とほぼ同じ出力を、超高速に計算できる。
矢印がいっぱい並んでたりするなど、複雑。コードのコピペは実運用には著作権などで向かないし…
オフトピック
●フーリエ変換
え？実数全体の広義積分？しかもネイピア数の四元数乗？といってもjだけだからオイラーの公式が応用できそうだけど、
積分には区間の最小値と最大値を使うから、大小関係がわからないと積分できなさそうだし…
意味わかんない…リスカしよ…
というわけで、離散フーリエ変換は遅い。高速フーリエ変換はわけわかんない。
では、なんとかして離散フーリエ変換と(ほぼ)同じ出力を比較的高速に計算できないだろうか？

まず、入力の要素数が2の非負整数乗の時は、
離散フーリエ変換に使う三角関数の値が限られた種類しかないことに気づきました。
さらによく見ると、位置によって法則がある周期で、符号のみ反転した同じ値が続いていることがわかりました。
同じ値ということは、最初だけ計算すればいいということです。
具体的には、次の図の赤枠で囲った部分のみを計算します。
krfh_zikken.png
高速離散フーリエ変換(仮)に繋がる実験
krfh_zikken.png (6.69 KiB) 閲覧数: 188 回
次に、足し算も工夫します。
セグメント木の技術を応用し、前の計算で同じ周期の場所は全部同じバッファに加算していきます。
そして、結果を得る際は周期1、周期2、周期4、...、周期N/2のバッファの適切な位置の値を適切に加算/減算すれば得られます。

このように考えて書いたコードがこちらです。
テスト用に途中計算のa,bの値も出力するようにしています。

CODE: 

const double ENNSYUURITU = 3.14159265358979323846264338327950288419716939937510582;

int getsinid(int i,int n) {
	if(i>=1;
	while(!(i&1)) {
		n>>=1;
		i>>=1;
	}
	return n;
}

std::vector risannfuuriehennkann2(
		std::vector >& debugout,
		const std::vector& data) {
	size_t N=data.size();
	std::vector result(N);
	debugout=std::vector >(N);
	if(N==2) {
		double a[2],b[2];
		a[0]=data.at(0)+data.at(1);
		b[0]=0;
		a[1]=data.at(0)-data.at(1);
		b[1]=0;
		debugout[0]=std::make_pair(a[0],b[0]);
		result[0]=a[0]*a[0]+b[0]*b[0];
		debugout[1]=std::make_pair(a[1],b[1]);
		result[1]=a[1]*a[1]+b[1]*b[1];
		return result;
	}

	double* abuf=new double[N];
	double* bbuf=new double[N];
	double* sintable=new double[N/4+1];
	for(size_t i=0;i(a,b);
		result[i]=a*a+b*b;
	}

	delete[] abuf;
	delete[] bbuf;
	delete[] sintable;
	return result;
}
実行時間と誤差を調べてみました。(コードは添付rfh_bench.cpp)
実行結果例(実行コマンドは略)

CODE: 

N=1024 seed=1381840516
単純な実装: 294 ms
今回の実装: 18 ms
最小誤差 出力: 0 a: 0 b: 0
最大誤差 出力: 4.9863e-010 a: 9.46798e-012 b: 9.14824e-012

N=2048 seed=1381840520
単純な実装: 1176 ms
今回の実装: 67 ms
最小誤差 出力: 0 a: 1.77636e-015 b: 0
最大誤差 出力: 1.44519e-009 a: 2.82121e-011 b: 2.31735e-011

N=4096 seed=1381840527
単純な実装: 4700 ms
今回の実装: 269 ms
最小誤差 出力: 0 a: 3.55271e-015 b: 0
最大誤差 出力: 1.01863e-008 a: 8.36025e-011 b: 8.30047e-011

N=8192 seed=1381840539
単純な実装: 18629 ms
今回の実装: 1089 ms
最小誤差 出力: 0 a: 0 b: 0
最大誤差 出力: 3.18942e-008 a: 2.19814e-010 b: 2.40291e-010
なんと、この環境では約17倍も高速になったようです。

さらに実験。昔書いたプログラムに今回の高速離散フーリエ変換(仮)を追加し、
実行速度を比較してみました。
[youtube][/youtube]
案の定離散フーリエ変換は超遅い・・・
そして、今回の高速離散フーリエ変換(仮)だと、なんとか2倍モードにしても60fpsに近い値が出ている！すごい！
・・・しかし、やはり高速フーリエ変換と比べたら圧倒的敗北です・・・

結論
やはり高速フーリエ変換よりは遅いですが、単純な離散フーリエ変換よりはかなり速く結果を求めることができました。
まだ改善の余地はあるのでしょうか？
また気が向いたら取り組んでみたいと思います。
添付ファイル

[拡張子 zip は無効化されているため、表示できません]

ページトップ
コメントはまだありません。