12 lines
497 B
Text
12 lines
497 B
Text
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| (-2 * Math::PI * k / x.size).i.exp }
|
|
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 }
|