Added Freivalds Algorithm

kopiro · kopiro · commit fe8bc41599df · 2017-06-12T11:14:32.000+02:00
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -62,7 +62,8 @@
    "number_theory": {
       "list": {
         "euclidean_algorithm": "Euclidean Algorithm",
-        "sieve_of_eratosthenes": "Sieve of Eratosthenes"
+        "sieve_of_eratosthenes": "Sieve of Eratosthenes",
+        "freivalds_algorithm": "Freivalds Algorithm"
       },
       "name": "Number Theory"
    },
diff --git a/algorithm/number_theory/freivalds_algorithm/basic/code.js b/algorithm/number_theory/freivalds_algorithm/basic/code.js
@@ -0,0 +1,55 @@
+function FreivaldsAlgorithm() {
+	var k = 5;
+	var i, j, tmp, tmpB, tmpC, n = A.length;
+
+	while (k--) {
+		logger._print('Iterations remained: #' + k);
+
+		// Generate random vector
+		var r = [], P = [];
+		for (i = 0; i < n; i++) {
+			P.push(-1);
+			r.push( (Math.random() < 0.5) << 0);
+		}
+		_r._setData(r)._wait();
+
+		// Compute Br, Cr
+		var Br = [], Cr = [];
+		for (i = 0; i < n; i++) {
+			tmpB = 0; 
+			tmpC = 0;
+			for (j = 0; j < n; j++) { 
+				tmpB += r[j] * B[j][i];
+				tmpC += r[j] * C[j][i];
+			}
+			Br.push(tmpB);
+			Cr.push(tmpC);
+		}
+
+		// Compute A * Br - Cr
+		P = [];
+		for (i = 0; i < n; i++) {
+			tmp = 0;
+			for (j = 0; j < n; j++) { 
+				tmp += (A[i][j] * Br[i]) - Cr[i];
+			}
+			P.push(tmp);
+		}
+		_p._setData(P)._wait();
+
+		for (i = 0; i < n; i++) {
+			if (P[i] !== 0) {
+				logger._print('P[' + i + '] !== 0 (' + P[i] + '), exit');
+				return false;
+			}
+		}
+
+		logger._print('Result vector is identity, continue...');
+
+
+	}
+
+	return true;
+}
+
+FreivaldsAlgorithm();
diff --git a/algorithm/number_theory/freivalds_algorithm/basic/data.js b/algorithm/number_theory/freivalds_algorithm/basic/data.js
@@ -0,0 +1,12 @@
+var A = [[2,3],[3,4]];
+var B = [[1,0],[1,2]];
+var C = [[6,5],[8,7]];
+
+var _a = new Array2DTracer('Matrix A'); _a._setData(A);
+var _b = new Array2DTracer('Matrix B'); _b._setData(B);
+var _c = new Array2DTracer('Matrix C'); _c._setData(C);
+
+var logger = new LogTracer();
+
+var _r = new Array1DTracer('Random Vector'); 
+var _p = new Array1DTracer('Result Vector'); 
diff --git a/algorithm/number_theory/freivalds_algorithm/desc.json b/algorithm/number_theory/freivalds_algorithm/desc.json
@@ -0,0 +1,12 @@
+{
+  "Freivalds Algorithm": "Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n &times; n matrices A, B, and C, a general problem is to verify whether A*B=C",
+  "Complexity": {
+    "time": "$O(n^2)$"
+  },
+  "References": [
+    "<a href='https://www.wikiwand.com/en/Freivalds%27_algorithm'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Freivalds Algorithm"
+  }
+}
