Fast Fibonacci

fibonacci.lua

local function matmul(a, b)
  return {
    a[1]*b[1] + a[2]*b[3], a[1]*b[2] + a[2]*b[4],
    a[3]*b[1] + a[4]*b[3], a[3]*b[2] + a[4]*b[4],
  }
end

local function matpow(m,p)
  local r = {
    m[1], m[2],
    m[3], m[4],
  }

  for _ = 1, p do
    r = matmul(r, m)
  end

  return r
end

local function fib(n)
  return matpow({1,1,1,0}, n)[2]
end

return fib