25 lines
645 B
Text
25 lines
645 B
Text
require "complex"
|
|
|
|
local function ditfft2(x, y, n, s)
|
|
if n == 1 then
|
|
y[1] = complex.of(x[1])
|
|
return
|
|
end
|
|
local hn = n // 2
|
|
ditfft2(x, y, hn, 2 * s)
|
|
local z = y:slice(hn + 1)
|
|
ditfft2(x:slice(s + 1), z, hn, 2 * s)
|
|
for i = hn + 1, #y do y[i] = z[i - hn] end
|
|
for k = 1, hn do
|
|
local tf = complex.polar(1, -2 * math.pi * (k - 1) / n) * y[k + hn]
|
|
local t = y[k]
|
|
y[k] += tf
|
|
y[k + hn] = t - tf
|
|
end
|
|
end
|
|
|
|
local x = {1, 1, 1, 1, 0, 0, 0, 0}
|
|
local y = table.create(#x)
|
|
for i = 1, #x do y[i] = complex.of(0) end
|
|
ditfft2(x, y, #x, 1)
|
|
for y as c do print(c:format("%6.4f")) end
|