gistfile1.py

table = {0: 0, 1: 1}
def fib(n):
    if n not in table:
        table[n] =  fib(n - 1) + fib(n - 2)
    return table[n]

phi = 1.618033988749895
psi = 1 - phi
def binet(n):
    phi_n = pow(phi,n)
    psi_n = pow(psi,n)
    return int(round((phi_n - psi_n) / (phi - psi)))

for i in xrange(1000000):
    if binet(i) != fib(i):
        print "error on {0}. fib = {1}, binet = {2}".format(i, fib(i), binet(i))
        break

#=> error on 71. fib = 308061521170129, binet = 308061521170130