Hardware Design: SIE

Hardware Design: SIE Git Source Tree

1	-- fibonacci function with cache
2
3	-- very inefficient fibonacci function
4	function fib(n)
5	N=N+1
6	if n<2 then
7	return n
8	else
9	return fib(n-1)+fib(n-2)
10	end
11	end
12
13	-- a general-purpose value cache
14	function cache(f)
15	local c={}
16	return function (x)
17	local y=c[x]
18	if not y then
19	y=f(x)
20	c[x]=y
21	end
22	return y
23	end
24	end
25
26	-- run and time it
27	function test(s,f)
28	N=0
29	local c=os.clock()
30	local v=f(n)
31	local t=os.clock()-c
32	print(s,n,v,t,N)
33	end
34
35	n=arg[1] or 24 -- for other values, do lua fib.lua XX
36	n=tonumber(n)
37	print("","n","value","time","evals")
38	test("plain",fib)
39	fib=cache(fib)
40	test("cached",fib)
41

Branches:
master