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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
function strassenMultiply(A, B) {
  const n = A.length;
  
  // Base case: 1x1 matrices
  if (n === 1) {
    return [[A[0][0] * B[0][0]]];
  }
  
  // Ensure n is a power of 2 (for simplicity)
  // In a real implementation, you would pad the matrices with zeros
  
  // Divide matrices into quadrants
  const mid = n / 2;
  
  // Create submatrices
  const a11 = submatrix(A, 0, 0, mid);
  const a12 = submatrix(A, 0, mid, mid);
  const a21 = submatrix(A, mid, 0, mid);
  const a22 = submatrix(A, mid, mid, mid);
  
  const b11 = submatrix(B, 0, 0, mid);
  const b12 = submatrix(B, 0, mid, mid);
  const b21 = submatrix(B, mid, 0, mid);
  const b22 = submatrix(B, mid, mid, mid);
  
  // Compute the seven products (recursively)
  const p1 = strassenMultiply(add(a11, a22), add(b11, b22));
  const p2 = strassenMultiply(add(a21, a22), b11);
  const p3 = strassenMultiply(a11, subtract(b12, b22));
  const p4 = strassenMultiply(a22, subtract(b21, b11));
  const p5 = strassenMultiply(add(a11, a12), b22);
  const p6 = strassenMultiply(subtract(a21, a11), add(b11, b12));
  const p7 = strassenMultiply(subtract(a12, a22), add(b21, b22));
  
  // Compute the quadrants of the result
  const c11 = add(subtract(add(p1, p4), p5), p7);
  const c12 = add(p3, p5);
  const c21 = add(p2, p4);
  const c22 = add(subtract(add(p1, p3), p2), p6);
  
  // Combine the quadrants into a single matrix
  return combineMatrices(c11, c12, c21, c22);
}
 
// Helper functions
function submatrix(matrix, startRow, startCol, size) {
  const result = [];
  for (let i = 0; i < size; i++) {
    result[i] = [];
    for (let j = 0; j < size; j++) {
      result[i][j] = matrix[startRow + i][startCol + j];
    }
  }
  return result;
}
 
function add(A, B) {
  const n = A.length;
  const result = [];
  for (let i = 0; i < n; i++) {
    result[i] = [];
    for (let j = 0; j < n; j++) {
      result[i][j] = A[i][j] + B[i][j];
    }
  }
  return result;
}
 
function subtract(A, B) {
  const n = A.length;
  const result = [];
  for (let i = 0; i < n; i++) {
    result[i] = [];
    for (let j = 0; j < n; j++) {
      result[i][j] = A[i][j] - B[i][j];
    }
  }
  return result;
}
 
function combineMatrices(c11, c12, c21, c22) {
  const n = c11.length;
  const result = [];
  for (let i = 0; i < n * 2; i++) {
    result[i] = [];
    for (let j = 0; j < n * 2; j++) {
      if (i < n && j < n) {
        result[i][j] = c11[i][j];
      } else if (i < n && j >= n) {
        result[i][j] = c12[i][j - n];
      } else if (i >= n && j < n) {
        result[i][j] = c21[i - n][j];
      } else {
        result[i][j] = c22[i - n][j - n];
      }
    }
  }
  return result;
}