Here's O(log n) solution [1]: def fib_sicp(n): a, b, p, q = 1, 0, 0, 1 while n > 0: if n % 2 == 0: # even oldp = p

Here's O(log n) solution [1]: def fib_sicp(n): a, b, p, q = 1, 0, 0, 1 while n > 0: if n % 2 == 0: # even oldp = p p = p*p + q*q q = 2*oldp*q + q*q n //= 2 else: olda = a a = b*q + a*q + a*p b = b*p + olda*q n -= 1 return b [1]: http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time/1526036#1526036 http://stackoverflow.com/questions/1525521/nth-fibonacci-num... It is ~20 times faster for n=10000