No.4ベストアンサー
- 回答日時:
どこまで理解できているのかわからないのでちょっと不安だけど, まあだいたいそう思っていいです.
「データ数を半分にする」ごとに
・DFT に必要な時間が半分になる.
・回転因子を掛けるための時間 (これはデータ数に比例する) がかかる.
前者は計算時間を減らし, それに対し後者は計算時間を増やします. その結果「ある程度のところ」で両方に必要な時間がバランスし, そのとき計算時間は最短になります.
No.3
- 回答日時:
計算量の評価は、#1さんの仰るとおりと思いますが、自分もFFTの原理は良くわかっていませんが、Nが大きくなると、FFTの方が無茶苦茶に速くなります(体感できます)。
FFTの効率の良さは、三角関数の周期性を利用するところにあるみたいです。つまり変換区間のある値から周期分ずれた所では、sin,cosは同じ値を出すはずだ、という発想です。これを考慮しないDFTは、同じ値を何回も計算し、大量の無駄を行ってる事になります。
周期性をうまく利用できるように、変換区間を半分づつに分割するのが、ミソみたいです。mを2以上の整数として、m^nに分割してもFFTはできるそうです。効率は理屈ではいっしょです。
この回答へのお礼
お礼日時:2011/04/05 18:24
自分もFFTの速さはさきほどプログラムを使って体感しました。ただ、どんな手法を経て計算コストが下がっているのか理解し切れてません。
アドバイスなどあれば教えてください。
No.2
- 回答日時:
そこは実は 4 に意味があるわけじゃないんだけどね.
Wikipedia の「高速フーリエ変換」の「原理の説明」を参考にするけど, N = PQ 個のデータに対する DFT は
1. Q 個のデータに対する DFT を P 回
2. 回転因子の乗算を合計 PQ 回
3. P 個のデータに対する DFT を Q 回
でできます. ここで, 「より少ない数のデータに対する DFT」だけではダメで, どうしても 2 の「回転因子の乗算」というステップが必要です. ここは PQ = N に比例する計算コストがかかります.
ということで, #1 の「+4N」はその分だと思ってください.
この回答へのお礼
お礼日時:2011/04/05 18:23
だんだんわかってきました。ありがとうございます。
つまり、2の回転因子の乗算のステップが必要ということは常に+4Nが発生するのでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 「FFTの基本は、DFTはサンプル数Nが偶数なら 2つのDFTに分解できるということ。 分解するとD 3 2022/03/31 21:01
- その他(IT・Webサービス) コストカットの計算について質問です。 例えば時期が1171円・業務削減見込み時間42分の場合、計算方 2 2022/12/07 09:48
- 物理学 風力発電での音 1 2023/04/16 08:55
- Excel(エクセル) コストカットについて質問です。 添付画像の総コスト・総教育コスト・総思考コストの計算をしたいのですが 5 2022/12/21 16:10
- その他(学校・勉強) 株などを複数違う割合で購入した場合の利率の計算方法 4 2022/05/01 09:31
- Java java 飾子を付けること(public static・・・) ・コンソールへの出力処理はmainメ 2 2022/06/16 19:34
- 化学 温度変化に伴う圧力と体積の変化について 2 2022/07/25 17:21
- その他(悩み相談・人生相談) そろばんのことで質問です 割りきれないわり算のことでおしえてください 例えば、93÷7の計算です そ 2 2022/07/18 15:18
- 離婚・親族 特有財産を含めての財産分割計算 について 3 2023/03/21 22:37
- 電気・ガス・水道 二世帯光熱費の計算 どちらが正しいですか? 2 2023/01/14 10:05
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報