質問: 高速フーリエ変換でデータ数が2のべき乗でない時 こんにちは。現在、フーリエ変換について勉強しているのですが、ちょっとわからないことがあったので質問させていただきました。 質問内容は高速フーリエ変換についてで、cooley&tukeyのアルゴリズムを利用すると、データが2の冪乗個のときは計算量をо(nlogn)に減らせる事ができるというものでした。 しかしデータが2の冪乗個でないとき。例えばn=5000くらいのときはデータを切り取って無理やりn=4096(=2^12)みたいな感じにすれば良いんですよね? やっぱりその時って、n=5000で通常の離散フーリエ変換したときと周波数値に誤差が出ると思うのですが、それはどうやったら計算できるのでしょうか。。。 どなたかご教授していただければ幸いです。
回答: 実際のところ, n = mn と 2数の積に分解できれば n点のフーリエ変換は m点のフーリエ変換 (のようなもの) と n点のフーリエ変換 (のようなもの) を連続して行うことで求まり, その時の計算量は o(n*(m+n)) となります. これを繰り返すと, 結局 n = p1^e1 p2^e2 ... pk^ek と素因数分解できたときに計算量は o(n(e1 p1 + e2 p2 + ... + ek pk)) と表されることになります. n = 2^n のときにこの分解が最も効率よくなり, o(n log n) となります. そうでないときには効率が落ちるのですが, それはそれでそれなりに計算できます. 例えば n = 5000 = 2^3 * 5^4 だと 5点に対するフーリエ変換を 4回, 2点に対するフーリエ変換を 3回行うことになり, その時の計算量はおよそ 5000*(5*4+2*3) = 5000*26 に比例します. 一方 n = 4096 に対する高速フーリエ変換は 4096*24 に比例します. ということで「データ 1個当たりの所要時間」は大して変わらないことが分かると思います. つまり, 普通の高速フーリエ変換とは違うものの, 「5点に対するフーリエ変換」を作ることさえできれば, 点数を 5000 にしたままでもそれほど時間はかからないのではないでしょうか.