Freivaldâ €™ s Algorithm to check if a matrix is product of two | PHP code to implement FreivaldaTMs Algorithm ; Function to check if ABx = Cx ; Generate a random vector ; Now comput B * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now comput C * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now comput A * ( B * r ) for evaluating expression A * ( B * r ) - ( C * r ) ; Finally check if value of expression A * ( B * r ) - ( C * r ) is 0 or not ; Runs k iterations Freivald . The value of k determines accuracy . Higher value means higher accuracy . ; Driver code
< ? php $ N = 2 ; function freivald ( $ a , $ b , $ c ) { global $ N ; $ r = array ( ) ; $ br = array ( ) ; $ cr = array ( ) ; $ axbr = array ( ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { $ r [ $ i ] = mt_rand ( ) % 2 ; $ br [ $ i ] = 0 ; $ cr [ $ i ] = 0 ; $ axbr [ $ i ] = 0 ; } for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 0 ; $ j < $ N ; $ j ++ ) $ br [ $ i ] = $ br [ $ i ] + $ b [ $ i ] [ $ j ] * $ r [ $ j ] ; } for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 0 ; $ j < $ N ; $ j ++ ) $ cr [ $ i ] = $ cr [ $ i ] + $ c [ $ i ] [ $ j ] * $ r [ $ j ] ; } for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 0 ; $ j < $ N ; $ j ++ ) $ axbr [ $ i ] = $ axbr [ $ i ] + $ a [ $ i ] [ $ j ] * $ br [ $ j ] ; } for ( $ i = 0 ; $ i < $ N ; $ i ++ ) if ( $ axbr [ $ i ] - $ cr [ $ i ] != 0 ) return false ; return true ; } function isProduct ( $ a , $ b , $ c , $ k ) { for ( $ i = 0 ; $ i < $ k ; $ i ++ ) if ( freivald ( $ a , $ b , $ c ) == false ) return false ; return true ; } $ a = array ( array ( 1 , 1 ) , array ( 1 , 1 ) ) ; $ b = array ( array ( 1 , 1 ) , array ( 1 , 1 ) ) ; $ c = array ( array ( 2 , 2 ) , array ( 2 , 2 ) ) ; $ k = 2 ; if ( isProduct ( $ a , $ b , $ c , $ k ) ) echo ( " Yes " ) ; else echo ( " No " ) ; ? >