Fibonacci using matrix multiplication

FIND nth FIBONACCI NUMBER USING MATRIX MULTIPLICATION

1              1              2              3              5              8              13           ….
F1            F2             F3             F4            F5            F6              F7          .....    Fn  

Basis used – 

Lets call this matrix M. All we have to do is M^n-1 and  return its [0][0]th element.

An efficient implementation using recursion is given below –

def power (F, n):

            if n == 1 or n == 0:

                                return   /// base case

            M = [[1, 1], [1, 0]]

power(F, n/2)

multiple(F, F)

if (n % 2 != 0):

                multiple(F, M)

def multiply (F,M):

                does the matrix multiplication and puts the result back into F.