Posted By

bingjian on 08/03/09


Tagged

algorithm fibonacci recursion complexity


Versions (?)

Fibonacci Numbers


 / Published in: Python
 

  1. """
  2. The closed form formula
  3. http://en.wikipedia.org/wiki/Fibonacci_number
  4. Numerical issues: start diverging at n=71; overflow at n=1475
  5. """
  6. fib = lambda n: int(1.6180339887498949**n/2.2360679774997898+0.5)
  7.  
  8.  
  9. """A natural recursive algorithm, exponential complexity"""
  10. fib1 = lambda n: fib1(n-1) + fib1(n-2) if n > 1 else n
  11.  
  12. """Iterative dynamic programming, linear complexity"""
  13. fib2 = lambda n: reduce(lambda x,y: x+[x[-1]+x[-2]], range(n-1), [0,1])[-1] if n > 1 else n
  14. fib3 = lambda n: reduce(lambda x,y: (x[1],x[1]+x[0]), range(n-1), [0,1])[1] if n > 1 else n
  15.  
  16. """
  17. Recursive matrix powering, linear complexity
  18. http://www.ics.uci.edu/~eppstein/161/960109.html
  19. overflow at n=47
  20. """
  21. from numpy import *
  22. M = matrix([[1,1],[1,0]])
  23. fib4 = lambda n: (M**(n-1))[0,0] if n > 1 else n

Report this snippet  

You need to login to post a comment.