Fibonacci numbers (Lua)

From LiteratePrograms

Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

In this article we show two ways of calculating fibonacci numbers in Lua.

<<fib.lua>>=
fib
fastfib
metafib
test

Contents 1 Recursive 2 Iterative with table 3 Metatables 4 Test

Recursive

This is a very simple recursive implementation. This will become slow on big numbers, because the numbers are recalculated for each recursion.

<<fib>>=
function fib(n) return n<2 and n or fib(n-1)+fib(n-2) end

Iterative with table

This is a faster, but also somewhat more complicated way to calculate Fibonacci numbers. To avoid recalculation and recursion, all results are stored in a table. This is a common technique called memoization.

<<fastfib>>=
function fastfib(n)
	fibs={[0]=0, 1, 1} -- global variable, outside the function
	for i=3,n do
		fibs[i]=fibs[i-1]+fibs[i-2]
	end
	return fibs[n]
end

Metatables

The outer table can be avoided by using metatables to fuse the external table and the function in a single object.

<<metafib>>=
metafib = { [0]=0, 1, 1 }
local mt = {
	__call = function(t, ...)
		local args = {...}
		local n = args[1]
		if not t[n] then
			for i = 3, n do
				t[i] = t[i-2] + t[i-1]
			end
		end
		return t[n]
	end
}
setmetatable(metafib, mt) -- now, metafib can be called as if it were a normal function

Test

If we run this test code, we can see that the iterative method is significantly faster than the recursive.

<<test>>=
for n=0,30 do print(fib(n)) end
for n=0,30 do print(fastfib(n)) end
for n=0,30 do print(metafib(n)) end

Download code