Implementation of the 'The Fast Fourier Transform Algorithm'

fft.rb

class FFT
  # Input: n coefficients
  # Output: Point-wise representation of the n coefficients
  # Vec size must be a power of 2
  def fft(vec)
    return vec if vec.size <= 1
    # Split A(x) into its odd and even powers
    a_even = vec.each_with_index.select { |_, i| i.even? }.map { |i, _| i }
    a_odd = vec.each_with_index.select { |_, i| i.odd? }.map { |i, _| i }

    # Express A(x) in the form Ae(x^2) + xAo(x^2)
    fft_even = fft(a_even) * 2
    fft_odd  = fft(a_odd) * 2

    # Compute Ae(x^2) + xAo(x^2)
    fft_even.zip(fft_odd).each_with_index.map { |(even, odd), i|
      even + odd * omega(i, vec.size)
    }
  end

  private

  # Calculates (e ^ (2πik/n))
  def omega(i, n)
    Math::E ** Complex(0, -2 * Math::PI * i / n)
  end
end

Full blog post can be found here: https://medium.com/@diegocasmo/the-fast-fourier-transform-algorithm-6f06900c565b#.lqtcu69lk