Calculate Nth fibonacci number( Fast approach)

fibo_fast.py

"""
This algorithm is based on the fact that :
F(2n) = F(n)^2 +  F(n+1)^2

and similarly :

F(2n+1) = 2*F(n)*F(n+1) + F(n+1)^2

Total steps = lg(N) (base2)
"""

def fib_fast(n):
    f1=0
    f2=1
    bi=bin(n)[2:]
    for i,_ in enumerate(bi[:-1]):
        if bi[i+1]=='1':
            fn=f1**2 + f2**2
            fn1=(2*f1*f2)+(f2**2)
            f2=fn+fn1
            f1=fn1
        else:
            fn=f1**2 + f2**2
            fn1=(2*f1*f2)+(f2**2)
            f1=fn
            f2=fn1
    return f1       


"""
Detailed Explanation:

First calculate f(1) and f(2), and then find out the binary value
of the N.
Iterate over the Binary array upto second last element.
Now if the next value in the array containing binary digits of N is '1',
then we have to calculate f(2) (f(2n)) and f(3) (f(2n+1)) first and then from these calculate
f(4) using the traditional approach. Now we've f(3) and f(4). f1 =f(3) and f(4) =f2
If the next binary value was '0' then we only calculate f(2) and f(3) and move on.
i.e. f(2n) and f(2n+1)

In the end f1 is the answer.

"""