sugarknri https://blog.hatena.ne.jp/sugarknri/ メモ https://sugarknri.hatenablog.com/ テクニック 何回見ても非再帰FFTの話が覚えられないのでメモ1のN乗根をgとする。 を離散フーリエ変換したい。 その結果は になる。ということで、全てのiについての が求められればよい。 これを頑張って計算する。 ところで、再帰FFTの気持ちには2種類あることをご存じでしたか？ぼくは今知りました。 kの偶奇で分ける ということで、fの偶数次の項、奇数次の項のみからなるN/2次の多項式をFFTできればよいので再帰的にやればできる iの偶奇で分ける ということで、iが偶数のときは、奇数のときはという多項式がそれぞれFFTできればよいので再帰的にやればできる 非再帰FFT iの偶奇で分けるFFTを非再帰にするの… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsugarknri.hatenablog.com%2Fentry%2F2020%2F08%2F05%2F120314" title="FFT - メモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=f%28x%29%3D%5Csum_%7Bi%3D0%7D%5E%7BN-1%7Da_i%20x%5Ei Hatena Blog https://hatena.blog 2020-08-05 12:03:14 rich https://sugarknri.hatenablog.com/entry/2020/08/05/120314 1.0 100%