The Discrete Fourier Transform in Ruby

ruby_DFT.rb

# This is O(n^2), it is NOT the FFT
require 'complex'

# This is our data
arr = [1,-1]*50

# This is the number of harmonics we wish to calculate
n_max = 20

# This is what will hold the result
new_arr = []

i = Math.sqrt(-1)
e = Math::E
pi = Math::PI

# We could cache e**(-i*2*pi*k/n_max) and e**n for all n and k, but this is a simple example
(0..(n_max-1)).each do |k|
  new_arr[k] = arr.each_with_index.reduce(0) do |sum, (x_n, n)|
    sum + x_n*e**(-i*2*pi*k/n_max*n)
  end
end