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
function multiply ( a , b ) { var mul = Array ( 3 ) . fill ( 0 ) . map ( x => Array ( 3 ) . fill ( 0 ) ) ; for ( i = 0 ; i < 3 ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { mul [ i ] [ j ] = 0 ; for ( k = 0 ; k < 3 ; k ++ ) mul [ i ] [ j ] += a [ i ] [ k ] * b [ k ] [ j ] ; } } for ( i = 0 ; i < 3 ; i ++ ) for ( j = 0 ; j < 3 ; j ++ ) a [ i ] [ j ] = mul [ i ] [ j ] ; } function power ( F , n ) { var M = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ; if ( n == 1 ) return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ; power ( F , parseInt ( n / 2 ) ) ; multiply ( F , F ) ; if ( n % 2 != 0 ) multiply ( F , M ) ; return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ; } function findNthTerm ( n ) { var F = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ; return power ( F , n - 2 ) ; } var n = 5 ; document . write ( " " + findNthTerm ( n ) ) ;