Repository: TheAlgorithms/Java
Pull request #6340 (2025-07-04 08:57:49)

Added Freivalds' Algorithm for randomized matrix multiplication verification
### Summary

Added **Freivalds' Algorithm** under the `randomized` category as part of issue [#6219]

This algorithm offers a fast, probabilistic method to verify whether matrix multiplication `A × B = C` holds true, avoiding full recomputation of the product.

---

### 🧠 Randomized Algorithm Approach

- Generate a random binary vector `r`
- Perform matrix-vector multiplications and check if:  
  `A × (B × r) ≟ C × r`
- Repeat this process `k` times to reduce the probability of error
- Probability of false positives becomes **≤ 1/2^k**

---

### ⏱ Time Complexity

- **Per iteration:** O(n²)
- **Total expected time:** O(k × n²)  
  (significantly faster than recomputing A × B, which is O(n³))

---

### ✅ Use Cases

- Verifying matrix multiplication in:
  - Scientific computing workflows
  - Distributed computing systems
  - Cloud infrastructure and audit pipelines
- Faster correctness checks in:
  - Numerical linear algebra
  - Cryptographic or zero-knowledge systems

---

### 📋 Checklist

- [x] I have read `CONTRIBUTING.md`
- [x] This pull request is entirely my work (no plagiarism)
- [x] All filenames follow PascalCase convention
- [x] All function and variable names follow Java naming conventions
- [x] Code has been formatted using:
   clang-format -i --style=file path/to/your/file.java

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6340?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `95.65217%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 74.35%. Comparing base [(`712ada5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/712ada5102be82b4807b0737ad70cfc0bca37935?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`808e53d`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/808e53d47e9da7892ff08a2d4c395210116d4d2c?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6340?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...ed/RandomizedMatrixMultiplicationVerification.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6340?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Frandomized%2FRandomizedMatrixMultiplicationVerification.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9yYW5kb21pemVkL1JhbmRvbWl6ZWRNYXRyaXhNdWx0aXBsaWNhdGlvblZlcmlmaWNhdGlvbi5qYXZh) | 95.65% | [1 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6340?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #6340      +/-   ##
============================================
+ Coverage     74.33%   74.35%   +0.02%     
- Complexity     5392     5402      +10     
============================================
  Files           679      680       +1     
  Lines         18820    18843      +23     
  Branches       3646     3656      +10     
============================================
+ Hits          13990    14011      +21     
- Misses         4274     4275       +1     
- Partials        556      557       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6340?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary> :rocket: New features to boost your workflow: </summary>

- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>

Patch:
diff --git a/src/main/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerification.java b/src/main/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerification.java
new file mode 100644
index 00000000..b5ac7076
--- /dev/null
+++ b/src/main/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerification.java
@@ -0,0 +1,64 @@
+package com.thealgorithms.randomized;
+
+import java.util.Random;
+
+public final class RandomizedMatrixMultiplicationVerification {
+
+    private RandomizedMatrixMultiplicationVerification() {
+        // Prevent instantiation of utility class
+    }
+
+    /**
+     * Verifies whether A × B == C using Freivalds' algorithm.
+     * @param A Left matrix
+     * @param B Right matrix
+     * @param C Product matrix to verify
+     * @param iterations Number of randomized checks
+     * @return true if likely A×B == C; false if definitely not
+     */
+    public static boolean verify(int[][] a, int[][] b, int[][] c, int iterations) {
+        int n = a.length;
+        Random random = new Random();
+
+        for (int iter = 0; iter < iterations; iter++) {
+            // Step 1: Generate random 0/1 vector
+            int[] r = new int[n];
+            for (int i = 0; i < n; i++) {
+                r[i] = random.nextInt(2);
+            }
+
+            // Step 2: Compute br = b × r
+            int[] br = new int[n];
+            for (int i = 0; i < n; i++) {
+                for (int j = 0; j < n; j++) {
+                    br[i] += b[i][j] * r[j];
+                }
+            }
+
+            // Step 3: Compute a(br)
+            int[] abr = new int[n];
+            for (int i = 0; i < n; i++) {
+                for (int j = 0; j < n; j++) {
+                    abr[i] += a[i][j] * br[j];
+                }
+            }
+
+            // Step 4: Compute cr = c × r
+            int[] cr = new int[n];
+            for (int i = 0; i < n; i++) {
+                for (int j = 0; j < n; j++) {
+                    cr[i] += c[i][j] * r[j];
+                }
+            }
+
+            // Step 5: Compare abr and cr
+            for (int i = 0; i < n; i++) {
+                if (abr[i] != cr[i]) {
+                    return false;
+                }
+            }
+        }
+
+        return true;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerificationTest.java b/src/test/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerificationTest.java
new file mode 100644
index 00000000..330662ac
--- /dev/null
+++ b/src/test/java/com/thealgorithms/randomized/RandomizedMatrixMultiplicationVerificationTest.java
@@ -0,0 +1,41 @@
+package com.thealgorithms.randomized;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import org.junit.jupiter.api.Test;
+
+class RandomizedMatrixMultiplicationVerificationTest {
+
+    @Test
+    void testCorrectMultiplication() {
+        int[][] a = {{1, 2}, {3, 4}};
+        int[][] b = {{5, 6}, {7, 8}};
+        int[][] c = {{19, 22}, {43, 50}};
+        assertTrue(RandomizedMatrixMultiplicationVerification.verify(a, b, c, 10));
+    }
+
+    @Test
+    void testIncorrectMultiplication() {
+        int[][] a = {{1, 2}, {3, 4}};
+        int[][] b = {{5, 6}, {7, 8}};
+        int[][] wrongC = {{20, 22}, {43, 51}};
+        assertFalse(RandomizedMatrixMultiplicationVerification.verify(a, b, wrongC, 10));
+    }
+
+    @Test
+    void testLargeMatrix() {
+        int size = 100;
+        int[][] a = new int[size][size];
+        int[][] b = new int[size][size];
+        int[][] c = new int[size][size];
+
+        for (int i = 0; i < size; i++) {
+            a[i][i] = 1;
+            b[i][i] = 1;
+            c[i][i] = 1;
+        }
+
+        assertTrue(RandomizedMatrixMultiplicationVerification.verify(a, b, c, 15));
+    }
+}