TheAlgorithms · krishnamitra03 · Jun 20, 2025 · DenizAltunkapan · Jun 24, 2025 · DenizAltunkapan
@@ -0,0 +1,54 @@
+/**
+ * Randomized algorithm to verify if A * B = C without computing full multiplication.
+ * Returns true if probably correct, false if definitely incorrect.
+ * Uses Freivalds' algorithm.
+ */
+
+package com.thealgorithms.matrix;
+
+public class RandomizedMatrixVerifier {
+
+    public static boolean verify(int[][] A, int[][] B, int[][] C) {
+        int n = A.length;
+        int[] r = new int[n];
+
+        // Generate random vector r
+        for (int i = 0; i < n; i++) {
+            r[i] = (int) (Math.random() * 10); // keep it simple
+        }
+
+        // Compute B * r
+        int[] Br = new int[n];
+        for (int i = 0; i < n; i++) {
+            Br[i] = 0;
+            for (int j = 0; j < n; j++) {
+                Br[i] += B[i][j] * r[j];
+            }
+        }
+
+        // Compute A * (B * r)
+        int[] ABr = new int[n];
+        for (int i = 0; i < n; i++) {
+            ABr[i] = 0;
+            for (int j = 0; j < n; j++) {
+                ABr[i] += A[i][j] * Br[j];
+            }
+        }
+
+        // Compute C * r
+        int[] Cr = new int[n];
+        for (int i = 0; i < n; i++) {
+            Cr[i] = 0;
+            for (int j = 0; j < n; j++) {
+                Cr[i] += C[i][j] * r[j];
+            }
+        }
+
+        // Compare ABr and Cr
+        for (int i = 0; i < n; i++) {
+            if (ABr[i] != Cr[i]) return false;
+        }
+
+        return true; // probably correct
+    }
+}
@@ -0,0 +1,59 @@
+package com.thealgorithms.matrix;
+
+import static org.junit.jupiter.api.Assertions.*;
+import org.junit.jupiter.api.Test;
+
+public class RandomizedMatrixVerifierTest {
+
+    @Test
+    public void testCorrectMultiplication() {
+        int[][] A = {
+            {1, 2},
+            {3, 4}
+        };
+        int[][] B = {
+            {5, 6},
+            {7, 8}
+        };
+        int[][] C = {
+            {19, 22},
+            {43, 50}
+        };
+
+        // Run multiple times to reduce chance of false positive
+        boolean result = true;
+        for (int i = 0; i < 5; i++) {
+            if (!RandomizedMatrixVerifier.verify(A, B, C)) {
+                result = false;
+                break;
+            }
+        }
+        assertTrue(result, "Verification should return true for correct C = A * B");
+    }
+
+    @Test
+    public void testIncorrectMultiplication() {
+        int[][] A = {
+            {1, 2},
+            {3, 4}
+        };
+        int[][] B = {
+            {5, 6},
+            {7, 8}
+        };
+        int[][] wrongC = {
+            {19, 22},
+            {43, 51} // incorrect value
+        };
+
+        // Even with randomness, wrong matrix should fail at least once in 5 tries
+        boolean result = true;
+        for (int i = 0; i < 5; i++) {
+            if (!RandomizedMatrixVerifier.verify(A, B, wrongC)) {
+                result = false;
+                break;
+            }
+        }
+        assertFalse(result, "Verification should return false for incorrect C");
+    }
+}