Merge pull request TheAlgorithms#357 from c-utkarsh/add-matrix-exponentiation-recursive

raklaptudirm · web-flow · commit 87f0c64e2f5f · 2021-05-23T13:05:33.000+05:30
Added Matrix Exponentiation (Recursive)
diff --git a/Maths/MatrixExponentiationRecursive.js b/Maths/MatrixExponentiationRecursive.js
@@ -0,0 +1,84 @@
+/*
+  Source:
+    https://en.wikipedia.org/wiki/Exponentiation_by_squaring
+
+  Complexity:
+    O(d^3 log n)
+    where: d is the dimension of the square matrix
+           n is the power the matrix is raised to
+*/
+
+const Identity = (n) => {
+  // Input: n: int
+  // Output: res: Identity matrix of size n x n
+  // Complexity: O(n^2)
+  const res = []
+  for (let i = 0; i < n; i++) {
+    res[i] = []
+    for (let j = 0; j < n; j++) {
+      res[i][j] = i === j ? 1 : 0
+    }
+  }
+  return res
+}
+
+const MatMult = (matA, matB) => {
+  // Input: matA: 2D Array of Numbers of size n x n
+  //        matB: 2D Array of Numbers of size n x n
+  // Output: matA x matB: 2D Array of Numbers of size n x n
+  // Complexity: O(n^3)
+  const n = matA.length
+  const matC = []
+  for (let i = 0; i < n; i++) {
+    matC[i] = []
+    for (let j = 0; j < n; j++) {
+      matC[i][j] = 0
+    }
+  }
+  for (let i = 0; i < n; i++) {
+    for (let j = 0; j < n; j++) {
+      for (let k = 0; k < n; k++) {
+        matC[i][j] += matA[i][k] * matB[k][j]
+      }
+    }
+  }
+  return matC
+}
+
+const MatrixExponentiationRecursive = (mat, m) => {
+  // Input: mat: 2D Array of Numbers of size n x n
+  // Output: mat^n: 2D Array of Numbers of size n x n
+  // Complexity: O(n^3 log m)
+  if (m === 0) {
+    // return identity matrix of size n x n
+    return Identity(mat.length)
+  } else if (m % 2 === 1) {
+    // tmp = mat ^ m-1
+    const tmp = MatrixExponentiationRecursive(mat, m - 1)
+    /// return tmp * mat = (mat ^ m-1) * mat = mat ^ m
+    return MatMult(tmp, mat)
+  } else {
+    // tmp = mat ^ m/2
+    const tmp = MatrixExponentiationRecursive(mat, m >> 1)
+    // return tmp * tmp = (mat ^ m/2) ^ 2 = mat ^ m
+    return MatMult(tmp, tmp)
+  }
+}
+
+const main = () => {
+  const mat = [[1, 0, 2], [2, 1, 0], [0, 2, 1]]
+
+  // mat ^ 0 = [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
+  console.log(MatrixExponentiationRecursive(mat, 0))
+
+  // mat ^ 1 = [ [ 1, 0, 2 ], [ 2, 1, 0 ], [ 0, 2, 1 ] ]
+  console.log(MatrixExponentiationRecursive(mat, 1))
+
+  // mat ^ 2 = [ [ 1, 4, 4 ], [ 4, 1, 4 ], [ 4, 4, 1 ] ]
+  console.log(MatrixExponentiationRecursive(mat, 2))
+
+  // mat ^ 5 = [ [ 1, 4, 4 ], [ 4, 1, 4 ], [ 4, 4, 1 ] ]
+  console.log(MatrixExponentiationRecursive(mat, 5))
+}
+
+main()
