Task

Calculate the   FFT   (Fast Fourier Transform)   of an input sequence.

The most general case allows for complex numbers at the input
and results in a sequence of equal length, again of complex numbers.
If you need to restrict yourself to real numbers, the output should
be the magnitude   (i.e.:   sqrt(re2 + im2))   of the complex result.

The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudo-code for that.
Further optimizations are possible but not required.




require "complex"
 
def fft(x : Array(Int32 | Float64)) #: Array(Complex)
  return [x[0].to_c] if x.size <= 1
  even = fft(Array.new(x.size // 2) { |k| x[2 * k] })
  odd  = fft(Array.new(x.size // 2) { |k| x[2 * k + 1] })
  c = Array.new(x.size // 2) { |k| Math.exp((-2 * Math::PI * k / x.size).i) }
  codd = Array.new(x.size // 2) { |k| c[k] * odd[k] }
  return Array.new(x.size // 2) { |k| even[k] + codd[k] } + Array.new(x.size // 2) { |k| even[k] - codd[k] }
end
 
fft([1,1,1,1,0,0,0,0]).each{ |c| puts c }
 