No.4ベストアンサー
- 回答日時:
siegmund です.
質問をよく見ましたら,
「何故に速くなるのですか?」もありましたね.
ちょっと早合点しちゃいました.
m=0 から m=N-1 までのN個のmの値に対して f(m) が与えられたとして
(前の回答ではxと書きましたが,離散的なのでmにしました)
離散フーリエ変換は
(1) F(k) = Σ(m=0~N-1) f(m) W^(km)
です.ただし,W = exp(2πi/N) です.
(1)のままやると,N^2 回の乗算が必要です.
ところが,N = N1×N2 と因数分解できるとき
(3) φ(k1,m2) = W^(k1m2) Σ(m1=0~N1-1) f(N2m1+m2) W^(N2k1m1)
(4) F(k1+N1k2) = Σ(m2=0~N2-1) φ(k1,m2) W^(N1k2m2)
と分解できます.
ただし,
(5) k1=0,1,・・・,N1-1
(6) m2=0,1,・・・,N2-1
(7) k2=0,1,・・・,N2-1
です.
(3)の乗算は N1×N2 回
(4)はこの各々に対して N2 回ですから,全体で N1(N2)^2 回の乗算で,
もとの N^2 = N1^2×N2^2 回の乗算に対して 1/N1 になりました.
ametsuchi さんご紹介のHPの「1.2.1 基本的な考え方」では,
この分解が N=2×(N/2) になっている場合が例示されています.
細かいテクニックは色々あるようですが,
私はそちらの専門家ではないので詳細をつっこまれるとボロが出ます.
演算量が減る原理ということで,お答えしました.
式が書きにくいんで,ミスプリが心配です.
No.3
- 回答日時:
siegmund先生のいわれるとおりで、わたし如きシロートの出る幕はないのですが、やさしい解説が以下のURLに付いていますので参照してください。
手元の資料によれば、N log N ではなく、N/2 log N となっていますが、「オーダー」とおっしゃられているので、間違いではないでしょう。
FFTが、現場でどれだけ約に立っているか、身近に接する機会も多いでしょう。コンピュータの処理能力の向上とともに、音声・画像など、これから益々重要になってきますが、FFT抜きではとても考えられないことです。
参考URL:http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/
No.2
- 回答日時:
高速フーリエ変換は数値計算の話で,
離散的なxについて関数値が知られているとき,
これを離散的フーリエ変換しようとするものです.
N個のxの値について関数値が知られているとき,
離散的フーリエ変換の式そのもので計算しますと N^2 回のオーダーの乗算が必要ですが,
アルゴリズムの工夫により N log N のオーダーの乗算回数で結果が得られます.
1965年にクーリーとチューキーが開発した手法です.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
logeの計算
-
10の0.3乗って??
-
log(-2)の求め方
-
∮x ^2/x-1 dxの計算結果につい...
-
2009年度の関西大の入試問題(...
-
logを分数で近似
-
数学の口頭試問具体例を教えて...
-
dbからμVへの変換方法
-
関数電卓でlog2=とおすと、0.3...
-
極限の計算をお願いします。 {...
-
微分方程式
-
1/2+1/4+1/6+……+1/(2n)が発散
-
2のN乗が10の場合、手計算で...
-
数学の極限の問題です! (1)l...
-
2を何乗したら2億を超えるか
-
ログを使う計算式をエクセルで...
-
2の50乗を簡単に概算出来る方...
-
木の高さを調べる方法
-
0.5時間などの時間計算の方法
-
molの問題で 0.4mol じゃなくて...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
logeの計算
-
10の0.3乗って??
-
2の50乗を簡単に概算出来る方...
-
∮x ^2/x-1 dxの計算結果につい...
-
262144って2の何乗でしょうか?
-
log(-2)の求め方
-
2のN乗が10の場合、手計算で...
-
常用対数についての問題です。7...
-
数学の口頭試問具体例を教えて...
-
1/2+1/4+1/6+……+1/(2n)が発散
-
【経済】毎年3%ずつ成長率が上...
-
2を何乗したら2億を超えるか
-
なぜ高速フーリエ変換はO(n*log...
-
dbからμVへの変換方法
-
極限の計算をお願いします。 {...
-
物理の計算で×10^3とかするのは...
-
真数の真という漢字にはどのよ...
-
べき乗とはなんでしょうか? 数...
-
スタージェスの公式について
-
logを分数で近似
おすすめ情報