require 'mathn'

N = 1<<3
f = Array.new(N) {|x| (x<N/2)? -1: 1}

Hadamard = Matrix[[1,1],[1,-1]]/Math.sqrt(2)
def Phase(theta)
  Matrix[[1,0],[0,Complex.polar(1,theta)]]
end
def R(k)
  lambda {|x,y| (Hadamard*Phase(2*Math::PI*k/N)*Vector[x,y]).to_a}
end

def FFT(arr,s=0,n=arr.size)
  abort 'error! not powers of 2' if n&(n-1)!=0
  if n==2 then
    arr[s],arr[s+1] = R(0).call(arr[s],arr[s+1])
  else
    arr[s,n] = arr.slice(s,n).partition.with_index {|_,i| i%2==0}.flatten
    FFT(arr,s,n/2)
    FFT(arr,s+n/2,n/2)
    for i in 0...n/2 do
      arr[s+i],arr[s+i+n/2] = R(i*N/n).call(arr[s+i],arr[s+i+n/2])
    end
  end
  return
end

puts f
FFT(f)
puts f