Anonymous user
Strassen's algorithm: Difference between revisions
m
Added references
(Moved Swift example into alphabetical order.) |
m (Added references) |
||
Line 956:
[https://github.com/hollance/Matrix/blob/master/Matrix.swift '''Matrix Class'''] by [https://github.com/ozgurshn ozgurshn]
<lang swift>
// Matrix Strassen Multiplication
func strassenMultiply(matrix1: Matrix, matrix2: Matrix) -> Matrix {
precondition(matrix1.columns == matrix2.columns,
"Two matrices can only be matrix multiplied if one has dimensions mxn & the other has dimensions nxp where m, n, p are in R")
// Transform to square matrix
let maxColumns = Swift.max(matrix1.rows, matrix1.columns, matrix2.rows, matrix2.columns)
let pwr2 = nextPowerOfTwo(num: maxColumns)
Line 975 ⟶ 978:
}
// Get strassen result and transfer to array with proper size
let formulaResult = strassenFormula(matrix1: sqrMatrix1, matrix2: sqrMatrix2)
var finalResult = Matrix(rows: matrix1.rows, columns: matrix2.columns)
Line 985 ⟶ 989:
}
// Calculate next power of 2
func nextPowerOfTwo(num: Int) -> Int {
return Int(pow(2,(ceil(log2(Double(num))))))
}
// Multiply Matrices Using Strassen Formula
func strassenFormula(matrix1: Matrix, matrix2: Matrix) -> Matrix {
precondition(matrix1.rows == matrix1.columns && matrix2.rows == matrix2.columns, "Matrices need to be square")
Line 994 ⟶ 1,000:
let rowHalf = matrix1.rows / 2
// Strassen Formula https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/
var a = Matrix(rows: rowHalf, columns: rowHalf)
var b = Matrix(rows: rowHalf, columns: rowHalf)
Line 1,017 ⟶ 1,023:
}
let p1 = strassenFormula(matrix1: a, matrix2: (f - h)) // a * (f - h)
let p2 = strassenFormula(matrix1: (a + b), matrix2: h) // (a + b) * h
let p3 = strassenFormula(matrix1: (c + d), matrix2: e) // (c + d) * e
let p4 = strassenFormula(matrix1: d, matrix2: (g - e)) // d * (g - e)
let p5 = strassenFormula(matrix1: (a + d), matrix2: (e + h)) // (a + d) * (e + h)
let p6 = strassenFormula(matrix1: (b - d), matrix2: (g + h)) // (b - d) * (g + h)
let p7 = strassenFormula(matrix1: (a - c), matrix2: (e + f)) // (a - c) * (e + f)
let result11 = p5 + p4 - p2 + p6 ▼
let
let
let
var result = Matrix(rows: matrix1.rows, columns: matrix1.rows)
Line 1,043 ⟶ 1,050:
func main(){
// Matrix Class https://github.com/hollance/Matrix/blob/master/Matrix.swift
var a = Matrix(rows: 2, columns: 2)
a[row: 0] = [1, 2]
| |||