Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  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.