>>> strassen([[2,1,3],[3,4,6],[1,4,2],[7,6,7]], [[4,2,3,4],[2,1,1,1],[8,6,4,2]]) [[34, 23, 19, 15], [68, 46, 37, 28], [28, 18, 15, 12], [96, 62, 55, 48]] >>> strassen([[3,7,5,6,9],[1,5,3,7,8],[1,4,4,5,7]], [[2,4],[5,2],[1,7],[5,5],[7,8]]) [[139, 163], [121, 134], [100, 121]]
(matrix1: list, matrix2: list)
| 105 | |
| 106 | |
| 107 | def strassen(matrix1: list, matrix2: list) -> list: |
| 108 | """ |
| 109 | >>> strassen([[2,1,3],[3,4,6],[1,4,2],[7,6,7]], [[4,2,3,4],[2,1,1,1],[8,6,4,2]]) |
| 110 | [[34, 23, 19, 15], [68, 46, 37, 28], [28, 18, 15, 12], [96, 62, 55, 48]] |
| 111 | >>> strassen([[3,7,5,6,9],[1,5,3,7,8],[1,4,4,5,7]], [[2,4],[5,2],[1,7],[5,5],[7,8]]) |
| 112 | [[139, 163], [121, 134], [100, 121]] |
| 113 | """ |
| 114 | if matrix_dimensions(matrix1)[1] != matrix_dimensions(matrix2)[0]: |
| 115 | msg = ( |
| 116 | "Unable to multiply these matrices, please check the dimensions.\n" |
| 117 | f"Matrix A: {matrix1}\n" |
| 118 | f"Matrix B: {matrix2}" |
| 119 | ) |
| 120 | raise Exception(msg) |
| 121 | dimension1 = matrix_dimensions(matrix1) |
| 122 | dimension2 = matrix_dimensions(matrix2) |
| 123 | |
| 124 | if dimension1[0] == dimension1[1] and dimension2[0] == dimension2[1]: |
| 125 | return [matrix1, matrix2] |
| 126 | |
| 127 | maximum = max(*dimension1, *dimension2) |
| 128 | maxim = int(math.pow(2, math.ceil(math.log2(maximum)))) |
| 129 | new_matrix1 = matrix1 |
| 130 | new_matrix2 = matrix2 |
| 131 | |
| 132 | # Adding zeros to the matrices to convert them both into square matrices of equal |
| 133 | # dimensions that are a power of 2 |
| 134 | for i in range(maxim): |
| 135 | if i < dimension1[0]: |
| 136 | for _ in range(dimension1[1], maxim): |
| 137 | new_matrix1[i].append(0) |
| 138 | else: |
| 139 | new_matrix1.append([0] * maxim) |
| 140 | if i < dimension2[0]: |
| 141 | for _ in range(dimension2[1], maxim): |
| 142 | new_matrix2[i].append(0) |
| 143 | else: |
| 144 | new_matrix2.append([0] * maxim) |
| 145 | |
| 146 | final_matrix = actual_strassen(new_matrix1, new_matrix2) |
| 147 | |
| 148 | # Removing the additional zeros |
| 149 | for i in range(maxim): |
| 150 | if i < dimension1[0]: |
| 151 | for _ in range(dimension2[1], maxim): |
| 152 | final_matrix[i].pop() |
| 153 | else: |
| 154 | final_matrix.pop() |
| 155 | return final_matrix |
| 156 | |
| 157 | |
| 158 | if __name__ == "__main__": |
no test coverage detected