deps/lua/test/fib.lua

   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)