# tFib.py
#example by Dan Bishop of decorator usage

class memoize(object):
   def __init__(self, func):
      self.__func = func
      self.__results = {}
   def __call__(self, *args):
      if args not in self.__results:
         self.__results[args] = self.__func(*args)
      return self.__results[args]

@memoize
def fibonacci(n):
   if n in (0, 1):
      return n
   return fibonacci(n - 1) + fibonacci(n - 2)

def Rfibonacci(n):
   if n in (0, 1):
      return n
   return Rfibonacci(n - 1) + Rfibonacci(n - 2)

def Sfibonacci(n):
   if n in (0, 1):
      return n
   return Sfibonacci(n - 1) + Sfibonacci(n - 2)
Sfibonacci= memoize(Sfibonacci)

def fib(n):
  if n in (0, 1):
    return n
  i0= 1
  i1= 2
  lim= n/2 - 1
  i= 0
  while i < lim:
    i+= 1
    i0, i1= i0 + i1, i0 + i1 + i1
  return (i0, i1)[n & 1]
    
if __name__ == '__main__':
  from timeit import Timer
  t = Timer("fib(10)", "from __main__ import fib")
  print "Unwrapped, using fib:               %.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
  t = Timer("fibonacci(10)", "from __main__ import fibonacci")
  print "Fibonacci, using @memoize:          %.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
  t = Timer("Rfibonacci(10)", "from __main__ import Rfibonacci")
  print "Raw Fibonacci:                      %.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
  t = Timer("Sfibonacci(10)", "from __main__ import Sfibonacci")
  print "Fibonacci with old deco:            %.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)
'''
  Results from the above using Windows XP 1.6MHz Pentium 4 with Python 2.4a
  
C:\Python24\python.exe tFib.py
Unwrapped, using fib:               4.81 usec/pass
Fibonacci, using @memoize:          2.81 usec/pass
Raw Fibonacci:                      213.70 usec/pass
Fibonacci with old deco:            2.84 usec/pass

  Results, using Python 2.3.3
>python -u "tFib.py"
Unwrapped, using fib:               7.75 usec/pass
Raw Fibonacci:                      255.84 usec/pass
Fibonacci with old deco:            3.23 usec/pass
>Exit code: 0
  
'''
