Fast Fib Using Exponentiation by Squaring and Binets Algorithm using only integers

fib.py

# Combined Exponentiation by Squaring and Binet's Algorithm. Encoded as a + b sqrt(5). Phi**n - phi**n = 0 + 2 (Phi**n)_b sqrt(5)

def fast_fib(n):
    n -= 1
    a, b, r, s = 1, 1, 1, 1
    while 1:
        if n & 1 == 1:
            r, s = a*r+5*b*s >> 1, a*s+b*r >> 1
        n >>= 1
        if n == 0:
            break
        a, b = a*a+5*b*b >> 1, a*b
    return s