Adds a method to Array to compute the 1-D radix-2 fast Fourier Transform

fft.rb

#!/usr/bin/env ruby
#  Adds a method to Array to compute the 1-D radix-2 fast Fourier Transform
#
#  Created by Paolo Bosetti on 2009-09-07.
#  Copyright (c) 2009 University of Trento. All rights reserved.
#
require "mathn"
require "complex"
include Math

class Array
  I = Complex(0,1)
  I2PI = 2*PI*I
  
  def fft(ru = nil)
    if self.size == 1
      return self
    else
      raise "Vector size must be power of 2" if self.size % 2 != 0
      n2 = self.size / 2
      root_u = (ru or exp(I2PI/self.size))
      even_a = (0...n2).map {|i| self[2*i]}
      odd_a  = (0...n2).map {|i| self[2*i+1]}
      even_t = even_a.fft(root_u**2)
      odd_t = odd_a.fft(root_u**2)
      result = []
      self.size.times {|i| 
        result[i] = even_t[i%n2] + root_u**i * odd_t[i%n2]
      }
      return result
    end
  end
  
end