Cooley–Tukey FFT. See http://rosettacode.org/wiki/Fast_Fourier_transform

FFT.lua

local complex = {
  __tostring = function(self) return ("(% .5f % .5fi)"):format(self[1], self[2]) end
}
local A = -2 * math.pi
local function C(t) return setmetatable(t, complex) end

local function cexp(x)
  local er = math.exp(x[1])
	return C{ er*math.cos(x[2]), er*math.sin(x[2]) }
end

local function cmul(x, y) return C{ x[1]*y[1]-x[2]*y[2], x[1]*y[2]+x[2]*y[1] } end
local function cadd(x, y) return C{ x[1]+y[1], x[2]+y[2] } end
local function csub(x, y) return C{ x[1]-y[1], x[2]-y[2] } end

local function slice(list) -- evens/odds semantics are weird.
  local even, odd = {}, {}
  for i = 1, #list, 2 do even[#even+1] = list[i] end
  for i = 2, #list, 2 do odd[#odd+1] = list[i] end
  return even, odd
end

local function FFT(x)
  local N, H = #x, math.floor(#x/2)
  local y = {}
  for i = 1, N do
    y[i] = type(x[i]) ~= "table" and C{x[i], 0} or x[i]
  end
  if N <= 1 then return y end
  local evens, odds = slice(y)
  evens = FFT(evens)
  odds = FFT(odds)
  local results = {}
  for k = 1, H do
    local T = cexp{0, A*((k-1)/N)}
    results[k] = cadd(evens[k], cmul(T, odds[k]))
    results[H+k] = csub(evens[k], cmul(T, odds[k]))
  end
  return results
end

local data = { 1, 1, 1, 1, 0, 0, 0, 0 }
local outp = FFT(data)

for i = 1, #data do
  print(tostring(outp[i]))
end

--[[ Output:
( 4.00000  0.00000i)
( 1.00000 -2.41421i)
( 0.00000  0.00000i)
( 1.00000 -0.41421i)
( 0.00000  0.00000i)
( 1.00000  0.41421i)
( 0.00000  0.00000i)
( 1.00000  2.41421i)
]]