Find Nth term ( A matrix exponentiation example ) | Javascript program to find n - th term of a recursive function using matrix exponentiation . ; This power function returns first row of { Transformation Matrix } ^ n - 1 * Initial Vector ; This is an identity matrix . ; this is Transformation matrix . ; Matrix exponentiation to calculate power of { tMat } ^ n - 1 store res in " res " matrix . ; res store { Transformation matrix } ^ n - 1 hence will be first row of res * Initial Vector . ; Driver code
var MOD = 1000000009 ; function power ( n ) { if ( n <= 1 ) return 1 ; n -- ; var res = [ [ 1 , 0 , ] , [ 0 , 1 ] ] ; var tMat = [ [ 2 , 3 ] , [ 1 , 0 ] ] ; while ( n ) { if ( n & 1 ) { var tmp = Array . from ( Array ( 2 ) , ( ) => Array ( 2 ) ) ; tmp [ 0 ] [ 0 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; tmp [ 0 ] [ 1 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; tmp [ 1 ] [ 0 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; tmp [ 1 ] [ 1 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; res [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; res [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; res [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; res [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; } n = parseInt ( n / 2 ) ; var tmp = Array . from ( Array ( 2 ) , ( ) => Array ( 2 ) ) ; tmp [ 0 ] [ 0 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; tmp [ 0 ] [ 1 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; tmp [ 1 ] [ 0 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; tmp [ 1 ] [ 1 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; tMat [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; tMat [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; tMat [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; tMat [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; } return ( res [ 0 ] [ 0 ] * 1 + res [ 0 ] [ 1 ] * 1 ) % MOD ; } var n = 3 ; document . write ( power ( n ) ) ;