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
< ? php function multiply ( & $ a , & $ b ) { $ mul = array_fill ( 0 , 3 , array_fill ( 0 , 3 , 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 ) { $ M = array ( array ( 1 , 1 , 1 ) , array ( 1 , 0 , 0 ) , array ( 0 , 1 , 0 ) ) ; if ( $ n == 1 ) return $ F [ 0 ] [ 0 ] + $ F [ 0 ] [ 1 ] ; power ( $ F , ( int ) ( $ n / 2 ) ) ; multiply ( $ F , $ F ) ; if ( $ n % 2 != 0 ) multiply ( $ F , $ M ) ; return $ F [ 0 ] [ 0 ] + $ F [ 0 ] [ 1 ] ; } function findNthTerm ( $ n ) { $ F = array ( array ( 1 , 1 , 1 ) , array ( 1 , 0 , 0 ) , array ( 0 , 1 , 0 ) ) ; return power ( $ F , $ n - 2 ) ; } $ n = 5 ; echo " F ( 5 ) ▁ is ▁ " . findNthTerm ( $ n ) ; ? >