Find Nth term ( A matrix exponentiation example ) | PHP 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
< ? php $ MOD = 1000000009 ; function power ( $ n ) { global $ MOD ; if ( $ n <= 1 ) return 1 ; $ n -- ; $ res = array ( array ( 1 , 0 ) , array ( 0 , 1 ) ) ; $ tMat = array ( array ( 2 , 3 ) , array ( 1 , 0 ) ) ; while ( $ n ) { if ( $ n & 1 ) { $ tmp = array_fill ( 0 , 2 , array_fill ( 0 , 2 , 0 ) ) ; $ 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 = ( int ) ( $ n / 2 ) ; $ tmp = array_fill ( 0 , 2 , array_fill ( 0 , 2 , 0 ) ) ; $ 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 ; } $ n = 3 ; echo power ( $ n ) ; ? >