Ruby で FFT (高速フーリエ変換) を書いてみた - まめめもref: 【ニコニコ動画】ミクをPCの再生音に合わせて自動で踊らせてみた ↑に触発されて波の処理をしたくなったので、Ruby で FFT (高速フーリエ変換) を書いてみました。 FFT とは、波の形を見て周波数とかを見抜く魔法のことです。数式とか考えたくないので、とにかく Ruby で書いてみました *1 。 def fft(a) n = a.size return a if n == 1 w = Complex.polar(1, -2 * Math::PI / n) a1 = fft((0 .. n / 2 - 1).map {|i| a[i] + a[i + n / 2] }) a2 = fft((0 .. n / 2 - 1).map {|i| (a[i] - a[i + n / 2]) * (w ** i) }) a1.zip(a2).flatten end これだけです。短いで
