Freivaldâ €™ s Algorithm to check if a matrix is product of two | C # code to implement Freivald 's Algorithm ; Function to check if ABx = Cx ; Generate a random vector ; Now compute B * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now compute C * r for evaluating expression A * ( B * r ) - ( C * r ) ; Now compute 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
using System ; class GFG { static int N = 2 ; static bool freivald ( int [ , ] a , int [ , ] b , int [ , ] c ) { Random rand = new Random ( ) ; int [ ] r = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) r [ i ] = ( int ) ( rand . Next ( ) ) % 2 ; int [ ] br = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) br [ i ] = br [ i ] + b [ i , j ] * r [ j ] ; int [ ] cr = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) cr [ i ] = cr [ i ] + c [ i , j ] * r [ j ] ; int [ ] axbr = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) axbr [ i ] = axbr [ i ] + a [ i , j ] * br [ j ] ; for ( int i = 0 ; i < N ; i ++ ) if ( axbr [ i ] - cr [ i ] != 0 ) return false ; return true ; } static bool isProduct ( int [ , ] a , int [ , ] b , int [ , ] c , int k ) { for ( int i = 0 ; i < k ; i ++ ) if ( freivald ( a , b , c ) == false ) return false ; return true ; } static void Main ( ) { int [ , ] a = new int [ , ] { { 1 , 1 } , { 1 , 1 } } ; int [ , ] b = new int [ , ] { { 1 , 1 } , { 1 , 1 } } ; int [ , ] c = new int [ , ] { { 2 , 2 } , { 2 , 2 } } ; int k = 2 ; if ( isProduct ( a , b , c , k ) ) Console . WriteLine ( " Yes " ) ; else Console . WriteLine ( " No " ) ; } }