# [a b] [e f]
# [c d] [g h]
def matrix_mul(A,B):
    [a,b,c,d] = A
    [e,f,g,h] = B
    return [a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h]

# [a b] [a b]
# [c d] [c d]
def matrix_square(A):
    [a,b,c,d] = A
    temp = b*c
    return [a*a+temp, a*b+b*d, a*c+c*d, temp+d*d]

def fast_matrix_pow(A,n):
    if n==0: return [1,0,0,1]
    if n==1: return A
    temp = fast_matrix_pow(A,n>>1)
    temp = matrix_square(temp)
    if n%2 == 1:
        return matrix_mul(temp,A)
    else:
        return temp

def fast_fib(n):

<< 0
<< 144

# All the matrices used
# in Fib generation
# has the form:
# [a b]
# [b c]
def fast_matrix_pow(n):
    if n==0: return [1,0,1]
    if n==1: return [1,1,0]
    [a,b,c] = fast_matrix_pow(n>>1)
    tmp = b*b
    a,b,c = a*a+tmp, (a+c)*b, tmp+c*c
    if n%2 == 1:
        return [a+b,a,c]
    else:
        return [a,b,c]

def fast_fib(n):
    return fast_matrix_pow(n)[1]

print(fast_fib(0))
print(fast_fib(12))

<< 0
<< 144

# All the matrices used
# in Fib generation
# has the form:
# [a b]
# [b c]

# [a b] \/ [a b] -- [a*a+b*b a*b+b*c]
# [b c] /\ [b c] -- [a*b+b*c b*b+c*c]

# F(2n) = (F(n-1) + F(n+1)) * F(n)

# [a b] \/ [1 1] -- [a+b a]
# [b c] /\ [1 0] -- [b+c b]

def fast_matrix_pow(n):
    if n==0: return [1,0,1]
    if n==1: return [1,1,0]
    [a,b,c] = fast_matrix_pow(n>>1)
    tmp = b*b
    a,b,c = a*a+tmp, (a+c)*b, tmp+c*c
    if n%2 == 1:
        return [a+b,a,c]
    else:
        return [a,b,c]

def fast_fib(n):
    return fast_matrix_pow(n)[1]

print(fast_fib(0))
print(fast_fib(12))

def fast_pow(int b, int n):
    if n<0: return 0
    if n==0: return 1
    if n==1: return b
    temp = fast_pow(b,n>>1)
    return temp*temp*[1,b][n%2]

def binet(n):
    phi = 1.618033988749895
    sqrt5 = 2.23606797749979
    return int(phi**n/sqrt5 + 0.5)

n = 71
print(list(fast_fib(x)-binet(x) for x in range(n)))

# F(2n) = (F(n-1) + F(n+1)) * F(n)
#       = (F(n-1) + F(n-1) + F(n)) * F(n)
#       = (2F(n-1) + F(n)) * F(n)

# F(2n-1) = F(n-1)*F(n-1) + F(n)*F(n)

# this returns [F(n-1), F(n)]
def fast_matrix_pow(n):
    if n==0: return [1,0]
    [a,b] = fast_matrix_pow(n>>1)
    b2 = b*b
    a,b = a*a+b2, (a<<1)*b+b2
    if n%2 == 1:
        return [b,a+b]
    return [a,b]

def fast_fib(n):
    return fast_matrix_pow(n)[1]