Commit faa870f
authored
Merge pull request algorithm-visualizer#226 from kopiro/pr-freivalds
Added Freivalds Algorithm4 files changed
Lines changed: 80 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -63,6 +63,7 @@ | |||
| 63 | 63 | "list": { | |
| 64 | 64 | "euclidean_algorithm": "Euclidean Algorithm", | |
| 65 | 65 | "sieve_of_eratosthenes": "Sieve of Eratosthenes", | |
| 66 | + "freivalds_algorithm": "Freivalds Algorithm", | ||
| 66 | 67 | "miller_rabin_primality_test": "Miller-Rabin primality test" | |
| 67 | 68 | }, | |
| 68 | 69 | "name": "Number Theory" | |
Lines changed: 55 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,55 @@ | |||
| 1 | + function FreivaldsAlgorithm() { | ||
| 2 | + var k = 5; | ||
| 3 | + var i, j, tmp, tmpB, tmpC, n = A.length; | ||
| 4 | + | ||
| 5 | + while (k--) { | ||
| 6 | + logger._print('Iterations remained: #' + k); | ||
| 7 | + | ||
| 8 | + // Generate random vector | ||
| 9 | + var r = [], P = []; | ||
| 10 | + for (i = 0; i < n; i++) { | ||
| 11 | + P.push(-1); | ||
| 12 | + r.push( (Math.random() < 0.5) << 0); | ||
| 13 | + } | ||
| 14 | + _r._setData(r)._wait(); | ||
| 15 | + | ||
| 16 | + // Compute Br, Cr | ||
| 17 | + var Br = [], Cr = []; | ||
| 18 | + for (i = 0; i < n; i++) { | ||
| 19 | + tmpB = 0; | ||
| 20 | + tmpC = 0; | ||
| 21 | + for (j = 0; j < n; j++) { | ||
| 22 | + tmpB += r[j] * B[j][i]; | ||
| 23 | + tmpC += r[j] * C[j][i]; | ||
| 24 | + } | ||
| 25 | + Br.push(tmpB); | ||
| 26 | + Cr.push(tmpC); | ||
| 27 | + } | ||
| 28 | + | ||
| 29 | + // Compute A * Br - Cr | ||
| 30 | + P = []; | ||
| 31 | + for (i = 0; i < n; i++) { | ||
| 32 | + tmp = 0; | ||
| 33 | + for (j = 0; j < n; j++) { | ||
| 34 | + tmp += (A[i][j] * Br[i]) - Cr[i]; | ||
| 35 | + } | ||
| 36 | + P.push(tmp); | ||
| 37 | + } | ||
| 38 | + _p._setData(P)._wait(); | ||
| 39 | + | ||
| 40 | + for (i = 0; i < n; i++) { | ||
| 41 | + if (P[i] !== 0) { | ||
| 42 | + logger._print('P[' + i + '] !== 0 (' + P[i] + '), exit'); | ||
| 43 | + return false; | ||
| 44 | + } | ||
| 45 | + } | ||
| 46 | + | ||
| 47 | + logger._print('Result vector is identity, continue...'); | ||
| 48 | + | ||
| 49 | + | ||
| 50 | + } | ||
| 51 | + | ||
| 52 | + return true; | ||
| 53 | + } | ||
| 54 | + | ||
| 55 | + FreivaldsAlgorithm(); | ||
Lines changed: 12 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,12 @@ | |||
| 1 | + var A = [[2,3],[3,4]]; | ||
| 2 | + var B = [[1,0],[1,2]]; | ||
| 3 | + var C = [[6,5],[8,7]]; | ||
| 4 | + | ||
| 5 | + var _a = new Array2DTracer('Matrix A'); _a._setData(A); | ||
| 6 | + var _b = new Array2DTracer('Matrix B'); _b._setData(B); | ||
| 7 | + var _c = new Array2DTracer('Matrix C'); _c._setData(C); | ||
| 8 | + | ||
| 9 | + var logger = new LogTracer(); | ||
| 10 | + | ||
| 11 | + var _r = new Array1DTracer('Random Vector'); | ||
| 12 | + var _p = new Array1DTracer('Result Vector'); | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,12 @@ | |||
| 1 | + { | ||
| 2 | + "Freivalds Algorithm": "Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices A, B, and C, a general problem is to verify whether A*B=C", | ||
| 3 | + "Complexity": { | ||
| 4 | + "time": "$O(n^2)$" | ||
| 5 | + }, | ||
| 6 | + "References": [ | ||
| 7 | + "<a href='https://www.wikiwand.com/en/Freivalds%27_algorithm'>Wikipedia</a>" | ||
| 8 | + ], | ||
| 9 | + "files": { | ||
| 10 | + "basic": "Freivalds Algorithm" | ||
| 11 | + } | ||
| 12 | + } | ||
0 commit comments