Matrix Exponentiation | A utility function to multiply two matrices a [ ] [ ] and b [ ] [ ] . Multiplication result is stored back in b [ ] [ ] ; Creating an auxiliary matrix to store elements of the multiplication matrix ; storing the multiplication result in a [ ] [ ] ; Updating our matrix ; Function to compute F raise to power n - 2. ; Multiply it with initial values i . e with F ( 0 ) = 0 , F ( 1 ) = 1 , F ( 2 ) = 1 ; Multiply it with initial values i . e with F ( 0 ) = 0 , F ( 1 ) = 1 , F ( 2 ) = 1 ; Return n 'th term of a series defined using below recurrence relation. f(n) is defined as f(n) = f(n-1) + f(n-2) + f(n-3), n>=3 Base Cases : f(0) = 0, f(1) = 1, f(2) = 1 ; Driver code
def multiply ( a , b ) : NEW_LINE INDENT mul = [ [ 0 for x in range ( 3 ) ] for y in range ( 3 ) ] ; NEW_LINE for i in range ( 3 ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE INDENT mul [ i ] [ j ] = 0 ; NEW_LINE for k in range ( 3 ) : NEW_LINE INDENT mul [ i ] [ j ] += a [ i ] [ k ] * b [ k ] [ j ] ; NEW_LINE DEDENT DEDENT DEDENT for i in range ( 3 ) : NEW_LINE INDENT for j in range ( 3 ) : NEW_LINE a [ i ] [ j ] = mul [ i ] [ j ] ; NEW_LINE DEDENT return a ; NEW_LINE DEDENT def power ( F , n ) : NEW_LINE INDENT M = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ; NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ; NEW_LINE DEDENT power ( F , int ( n / 2 ) ) ; NEW_LINE F = multiply ( F , F ) ; NEW_LINE if ( n % 2 != 0 ) : NEW_LINE INDENT F = multiply ( F , M ) ; NEW_LINE DEDENT return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ; NEW_LINE DEDENT def findNthTerm ( n ) : NEW_LINE INDENT F = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ; NEW_LINE return power ( F , n - 2 ) ; NEW_LINE DEDENT n = 5 ; NEW_LINE print ( " F ( 5 ) ▁ is " , findNthTerm ( n ) ) ; NEW_LINE