Find Nth term ( A matrix exponentiation example ) | Java 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 wiint be first row of res * Initial Vector . ; Driver code
class GfG { static int MAX = 100 ; static int MOD = 1000000009 ; static int power ( int n ) { if ( n <= 1 ) { return 1 ; } n -- ; int res [ ] [ ] = { { 1 , 0 } , { 0 , 1 } } ; int tMat [ ] [ ] = { { 2 , 3 } , { 1 , 0 } } ; while ( n > 0 ) { if ( n % 2 == 1 ) { int tmp [ ] [ ] = new int [ 2 ] [ 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 = n / 2 ; int tmp [ ] [ ] = new int [ 2 ] [ 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 ; } public static void main ( String [ ] args ) { int n = 3 ; System . out . println ( power ( n ) ) ; } }