Fenrir's BLog: RubyでFFT

レポートでフーリエ変換をどうたらしなければならないので、FFTをRubyで実装してみることにしました。といってもRubyという時点で金持ちプログラミング決定なので効率無視です。 Cooley-Tukey 型 FFTで実装してみました。これよりも効率のよいPrime Factor 型 FFTというのもあるのですが(詳しくはFFTの概略と設計法参照のこと)、因数分解とかがぱっと実装思いつかなかったので、簡単なCooley-Tukey 型にしました。 コードは続きをどうぞ。改善の余地がかなりあると思います。 FFT.rb require 'complex' # FFT class FFT def FFT.fft(data) #まず何回2で割り切れるか数える power2 = 0 size = data.size while (size & 0b1) == 0 power2 += 1 size >