In case anyone is interested...
# Retrieved from:
http://en.literateprograms.org/Fibonacci_numbers_(Python)?oldid=10746
# Recursion with memoization
memo = {0:0, 1:1}
def fib(n):
if not n in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
# Quick exact computation of large individual Fibonacci numbers
def powLF(n):
if n == 1: return (1, 1)
L, F = powLF(n/2)
L, F = (L**2 + 5*F**2) >> 1, L*F
if n & 1:
return ((L + 5*F)>>1, (L + F) >>1)
else:
return (L, F)
def fib(n):
return powLF(n)[1]
--
http://mail.python.org/mailman/listinfo/python-list
