Breaking
Randomized

# Verify matrix multiplication using randomized Freivalds algorithm

Freivalds algorithm is used to verify the correctness of the matrix multiplication. We can also use the native way to verify the matrix multiplication. But the current method is slow. It is a probabilistic randomized algorithm used to verify matrix multiplication.

A native algorithm would compute the product A x B explicitly and compare term by term whether this product equals C. Write a program to verify the matrix multiplication using Freivalds algorithm.

## source Code

```package com.dsacode.Algorithm.randomized;

import java.util.Arrays;
import java.util.Random;

public class VerifyMatrix {
public static void main(String args[]){
int n = 2;
System.out.println("Dimesion of the matrices: "+n);

double[][] a=new double[][]{{2, 3},{3, 4}};
System.out.println("Matrix One values: " + Arrays.deepToString(a));

double b[][]=new double[][]{{1, 0},{ 1, 2}};
System.out.println("Matrix two values: " + Arrays.deepToString(b));

double c[][] = new double[][]{{6,5},{8,7}};
System.out.println("Result Matrix values: " + Arrays.deepToString(c));

double [][]r = new double[n];
Random random = new Random();
for(int i=0; i < n; i++){
r[i] = random.nextInt(2);
}

double br[][] = new double[n];
@SuppressWarnings("unused")
double cr[][] = new double[n];
double abr[][] = new double[n];

br = multiplymatrix(b, r, n);
cr = multiplymatrix(c, r, n);
abr = multiplymatrix(a, br, n);

boolean flag = true;

for(int i=0; i < n; i++)  {
if(abr[i] == 0)
continue;
else
flag = false;
}

if(flag == true)
System.out.println("Successfully verified matrix multiplication using Freivalds algorithm");
else
System.out.println("Failed to verify matrix multiplication using Freivalds algorithm");

}

public static double[][] multiplymatrix(double[][] a, double[][] b, int n) {
double result[][] = new double[n];

for (int i = 0; i < n; i++){
for (int j = 0; j < 1; j++) {
for (int k = 0; k < n; k++) {
result[i][j] = result[i][j] + a[i][k] * b[k][j];
}
}
}
return result;
}
}```

## Output

```Dimesion of the matrices: 2
Matrix One values: [[2.0, 3.0], [3.0, 4.0]]
Matrix two values: [[1.0, 1.0], [0.0, 2.0]]
Result Matrix values: [[6.0, 5.0], [8.0, 7.0]]
Failed to verify matrix multiplication using Freivalds algorithm```

## Reference

https://en.wikipedia.org/wiki/Freivalds%27_algorithm#