離散フーリエ変換を自分で作ってみたんだけど適当に直してくれ
FFTにはしないでね

class Array
　def dft
　　n = self.length
　　w = Complex.polar(1, -2*Math::PI/n)
　　w_arr = (0...n).map.with_index{|row, _n| (0...n).map.with_index {|e, _k| w**(_n*_k)}}
　　dft_arr = (0...n).map.with_index do |e, _k|
　　　sum = 0
　　　n.times{|_n| sum += w_arr[_n][_k] * self[_n]}
　　　sum/(n**0.5)
　　end
　end
end

p [0,1,0,1].dft #=> [(1.0+0.0i), (-6.123031769111886e-17+0.0i), (-1.0-2.4492127076447545e-16i), (1.836909530733566e-16+0.0i)]