11 lines
352 B
Ruby
11 lines
352 B
Ruby
def fft(vec)
|
|
return vec if vec.size <= 1
|
|
evens_odds = vec.partition.with_index{|_,i| i.even?}
|
|
evens, odds = evens_odds.map{|even_odd| fft(even_odd)*2}
|
|
evens.zip(odds).map.with_index do |(even, odd),i|
|
|
even + odd * Math::E ** Complex(0, -2 * Math::PI * i / vec.size)
|
|
end
|
|
end
|
|
|
|
fft([1,1,1,1,0,0,0,0]).each{|c| puts "%9.6f %+9.6fi" % c.rect}
|