Lua Fibonacci

fib.lua

-- Author: Michael-Keith Bernard
-- Date: May 22, 2012
-- Description: Various implementations of the Fibonacci sequence in Lua. Lua
-- has native support for tail-call elimination which is why `tail_call` and
-- `continuation` run in near constant time. For sufficiently large numbers of n
-- you can start to see linear performace characteristics (particularly for the
-- `continuation` implementation), but ultimately the `tail_call` implementation
-- is an order of magnitude faster than iteration even for values of n as small
-- as 500k.

Fibonacci = {}

-- Naive recursive
function Fibonacci.naive(n)
  local function inner(m)
    if m < 2 then
      return m
    end
    return inner(m-1) + inner(m-2)
  end
  return inner(n)
end

-- Iterative
function Fibonacci.iterative(n)
  a, b = 0, 1

  for i = 1, n do
    a, b = b, a + b
  end
  return a
end

-- Memoized naive recursive
function Fibonacci.memoized(n)
  local memo = {}
  local function inner(m)
    if m < 2 then
      return m
    end

    if memo[m] then
      return memo[m]
    else
      local res = inner(m-1) + inner(m-2)
      memo[m] = res
      return res
    end
  end
  return inner(n)
end

-- Tail-optimized recursive
function Fibonacci.tail_call(n)
  local function inner(m, a, b)
    if m == 0 then
      return a
    end
    return inner(m-1, b, a+b)
  end
  return inner(n, 0, 1)
end

-- Continuation passing style
function Fibonacci.continuation(n)
  local function inner(m, cont)
    if m == 0 then
      return cont(0, 1)
    end
    return inner(m-1, function(a, b) return cont(b, a+b) end)
  end
  return inner(n, function(a, b) return a end)
end

function timeit(f, ...)
  local start = os.time()
  local res = { f(...) }
  local delta = os.time() - start
  
  return delta, unpack(res)
end

for _, n in ipairs({10, 25, 35, 100, 1000, 5000, 100000, 1000000, 5000000}) do
  print("Fib of "..n)
  for name, fibfun in pairs(Fibonacci) do
    if name == "naive" and n > 35 then
      print(string.format("  %s, time: %s, %s", name, "skipped", "skipped"))
    elseif name == "memoized" and n > 5000 then
      print(string.format("  %s, time: %s, %s", name, "skipped", "skipped"))
    else
      print(string.format("  %s, time: %s, %s", name, timeit(fibfun, n)))
    end
  end
end

In the iterative function the variables a and b are globals. You may want to add a local declaration for them. Then the iterative function is much faster than the tail recursive version.

Fib of 5000000 (lua 5.1)
 iter_locals  time:  0.049   inf
   tail_call  time:  0.190   inf
   iterative  time:  0.248   inf
continuation  time:  0.869   inf

Bonus: if you run it with luajit the loop turns into just eight instructions:

  for i = 1, n do
      a, b = b, a + b
  end
->LOOP:
0bceffe0  movaps xmm5, xmm6
0bceffe3  movaps xmm6, xmm7
0bceffe6  movaps xmm7, xmm5
0bceffe9  addsd xmm6, xmm7
0bceffed  add ebp, +0x01
0bcefff0  cmp ebp, eax
0bcefff2  jle 0x0bceffe0    ->LOOP
0bcefff4  jmp 0x0bce001c    ->3

In the iterative function the variables a and b are globals. You may want to add a local declaration for them. Then the iterative function is much faster than the tail recursive version.

I don't even know what is b for... That iterative function doesn't work, + it's simpler this way:

-- Iterative
function Fibonacci.iterative(n)
	if n < 2 then
		return n
	end
	local a = 0
	for i = 1, n do
		a = a + i
	end
	return a
end

-- Tail-optimized recursive
function Fibonacci.tail_call(n, current)
	if not current then
		current = 1
	end
	if n < 2 then
		return current
	end
	return Fibonacci.tail_call(n-1, current+n)
end