"""
The closed form formula
http://en.wikipedia.org/wiki/Fibonacci_number
Numerical issues: start diverging at n=71; overflow at n=1475
"""
fib  = lambda n: int(1.6180339887498949**n/2.2360679774997898+0.5)


"""A natural recursive algorithm, exponential complexity"""
fib1 = lambda n: fib1(n-1) + fib1(n-2) if n > 1 else n

"""Iterative dynamic programming, linear complexity"""
fib2 = lambda n: reduce(lambda x,y: x+[x[-1]+x[-2]], range(n-1), [0,1])[-1] if n > 1 else n
fib3 = lambda n: reduce(lambda x,y: (x[1],x[1]+x[0]), range(n-1), [0,1])[1] if n > 1 else n

"""
Recursive matrix powering, linear complexity
http://www.ics.uci.edu/~eppstein/161/960109.html
overflow at n=47
"""
from numpy import *
M = matrix([[1,1],[1,0]])
fib4 = lambda n: (M**(n-1))[0,0] if n > 1 else n

Fibonacci Numbers

Python