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