GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — JavaScript/Maths/MatrixExponentiationRecursive.js at master · TheAlgorithms/JavaScript

Expand file tree

/

MatrixExponentiationRecursive.js

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
80 lines (71 loc) · 2.15 KB
/

MatrixExponentiationRecursive.js

Copy path

File metadata and controls

80 lines (71 loc) · 2.15 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
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 = (matrixA, matrixB) => {
// Input: matrixA: 2D Array of Numbers of size n x n
// matrixB: 2D Array of Numbers of size n x n
// Output: matrixA x matrixB: 2D Array of Numbers of size n x n
// Complexity: O(n^3)
const n = matrixA.length
const matrixC = []
for (let i = 0; i < n; i++) {
matrixC[i] = []
for (let j = 0; j < n; j++) {
matrixC[i][j] = 0
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
matrixC[i][j] += matrixA[i][k] * matrixB[k][j]
}
}
}
return matrixC
}
export 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 mat = [[1, 0, 2], [2, 1, 0], [0, 2, 1]]
// // mat ^ 0 = [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
// MatrixExponentiationRecursive(mat, 0)
// // mat ^ 1 = [ [ 1, 0, 2 ], [ 2, 1, 0 ], [ 0, 2, 1 ] ]
// MatrixExponentiationRecursive(mat, 1)
// // mat ^ 2 = [ [ 1, 4, 4 ], [ 4, 1, 4 ], [ 4, 4, 1 ] ]
// MatrixExponentiationRecursive(mat, 2)
// // mat ^ 5 = [ [ 1, 4, 4 ], [ 4, 1, 4 ], [ 4, 4, 1 ] ]
// MatrixExponentiationRecursive(mat, 5)
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.