Find Nth term ( A matrix exponentiation example ) | Python3 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
MOD = 1000000009 ; NEW_LINE def power ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT n -= 1 ; NEW_LINE res = [ [ 1 , 0 ] , [ 0 , 1 ] ] ; NEW_LINE tMat = [ [ 2 , 3 ] , [ 1 , 0 ] ] ; NEW_LINE while ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT tmp = [ [ 0 for x in range ( 2 ) ] for y in range ( 2 ) ] ; NEW_LINE tmp [ 0 ] [ 0 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 0 ] [ 1 ] = ( res [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 0 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 1 ] = ( res [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + res [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE res [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; NEW_LINE res [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; NEW_LINE res [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; NEW_LINE res [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; NEW_LINE DEDENT n = n // 2 ; NEW_LINE tmp = [ [ 0 for x in range ( 2 ) ] for y in range ( 2 ) ] ; NEW_LINE tmp [ 0 ] [ 0 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 0 ] [ 1 ] = ( tMat [ 0 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 0 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 0 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 0 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 0 ] ) % MOD ; NEW_LINE tmp [ 1 ] [ 1 ] = ( tMat [ 1 ] [ 0 ] * tMat [ 0 ] [ 1 ] + tMat [ 1 ] [ 1 ] * tMat [ 1 ] [ 1 ] ) % MOD ; NEW_LINE tMat [ 0 ] [ 0 ] = tmp [ 0 ] [ 0 ] ; NEW_LINE tMat [ 0 ] [ 1 ] = tmp [ 0 ] [ 1 ] ; NEW_LINE tMat [ 1 ] [ 0 ] = tmp [ 1 ] [ 0 ] ; NEW_LINE tMat [ 1 ] [ 1 ] = tmp [ 1 ] [ 1 ] ; NEW_LINE DEDENT return ( res [ 0 ] [ 0 ] * 1 + res [ 0 ] [ 1 ] * 1 ) % MOD ; NEW_LINE DEDENT n = 3 ; NEW_LINE print ( power ( n ) ) ; NEW_LINE