-- fibonacci function with cache

-- very inefficient fibonacci function

function fib(n)

N=N+1

if n<2 then

return n

else

return fib(n-1)+fib(n-2)

end

end

-- a general-purpose value cache

function cache(f)

local c={}

return function (x)

local y=c[x]

if not y then

y=f(x)

c[x]=y

end

return y

end

end

-- run and time it

function test(s,f)

N=0

local c=os.clock()

local v=f(n)

local t=os.clock()-c

print(s,n,v,t,N)

end

n=arg[1] or 24 -- for other values, do lua fib.lua XX

n=tonumber(n)

print("","n","value","time","evals")

test("plain",fib)

fib=cache(fib)

test("cached",fib)