fft.rb

def unnormalized_fft(x, start_i = 0, n = x.size, step = 1)
  if n == 1
    Vector[x[start_i]]
  else
    even = unnormalized_fft(x, start_i, n/2, step * 2)
    odd  = unnormalized_fft(x, start_i + step, n/2, step * 2)

    out = Array.new(n)
    (n/2).times do |k|
      out[k]       = even[k] + Complex.polar(1, -2*Math::PI*k/n)*odd[k]
      out[k + n/2] = even[k] - Complex.polar(1, -2*Math::PI*k/n)*odd[k]
    end

    Vector.elements out
  end
end

def fft(x)
  unnormalized_fft(x)/x.size
end