Strassen's algorithm: Difference between revisions
Content added Content deleted
m (Added references) |
m (Added comments on swift implementation) |
||
| Line 966: | Line 966: | ||
var sqrMatrix1 = Matrix(rows: pwr2, columns: pwr2) |
var sqrMatrix1 = Matrix(rows: pwr2, columns: pwr2) |
||
var sqrMatrix2 = Matrix(rows: pwr2, columns: pwr2) |
var sqrMatrix2 = Matrix(rows: pwr2, columns: pwr2) |
||
// fill square matrix 1 with values |
|||
for i in 0..<matrix1.rows { |
for i in 0..<matrix1.rows { |
||
for j in 0..<matrix1.columns{ |
for j in 0..<matrix1.columns{ |
||
| Line 972: | Line 973: | ||
} |
} |
||
} |
} |
||
// fill square matrix 2 with values |
|||
for i in 0..<matrix2.rows { |
for i in 0..<matrix2.rows { |
||
for j in 0..<matrix2.columns{ |
for j in 0..<matrix2.columns{ |
||
| Line 991: | Line 993: | ||
// Calculate next power of 2 |
// Calculate next power of 2 |
||
func nextPowerOfTwo(num: Int) -> Int { |
func nextPowerOfTwo(num: Int) -> Int { |
||
// formula for next power of 2 |
|||
return Int(pow(2,(ceil(log2(Double(num)))))) |
return Int(pow(2,(ceil(log2(Double(num)))))) |
||
} |
} |
||
| Line 1,001: | Line 1,004: | ||
let rowHalf = matrix1.rows / 2 |
let rowHalf = matrix1.rows / 2 |
||
// Strassen Formula https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/ |
// Strassen Formula https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/ |
||
// p1 = a(f-h) p2 = (a+b)h |
|||
// p2 = (c+d)e p4 = d(g-e) |
|||
// p5 = (a+d)(e+h) p6 = (b-d)(g+h) |
|||
// p7 = (a-c)(e+f) |
|||
|a b| x |e f| = |(p5+p4-p2+p6) (p1+p2)| |
|||
|c d| |g h| |(p3+p4) (p1+p5-p3-p7)| |
|||
Matrix 1 Matrix 2 Result |
|||
// create empty matrices for a, b, c, d, e, f, g, h |
|||
var a = Matrix(rows: rowHalf, columns: rowHalf) |
var a = Matrix(rows: rowHalf, columns: rowHalf) |
||
var b = Matrix(rows: rowHalf, columns: rowHalf) |
var b = Matrix(rows: rowHalf, columns: rowHalf) |
||
| Line 1,009: | Line 1,021: | ||
var g = Matrix(rows: rowHalf, columns: rowHalf) |
var g = Matrix(rows: rowHalf, columns: rowHalf) |
||
var h = Matrix(rows: rowHalf, columns: rowHalf) |
var h = Matrix(rows: rowHalf, columns: rowHalf) |
||
// fill the matrices with values |
|||
for i in 0..<rowHalf { |
for i in 0..<rowHalf { |
||
for j in 0..<rowHalf { |
for j in 0..<rowHalf { |
||
| Line 1,023: | Line 1,036: | ||
} |
} |
||
// a * (f - h) |
|||
let |
let p1 = strassenFormula(matrix1: a, matrix2: (f - h)) |
||
// (a + b) * h |
|||
| ⚫ | |||
let |
let p2 = strassenFormula(matrix1: (a + b), matrix2: h) |
||
// (c + d) * e |
|||
let |
let p3 = strassenFormula(matrix1: (c + d), matrix2: e) |
||
// d * (g - e) |
|||
let p4 = strassenFormula(matrix1: d, matrix2: (g - e)) |
|||
// (a + d) * (e + h) |
|||
| ⚫ | |||
| ⚫ | |||
// (b - d) * (g + h) |
|||
let |
let p6 = strassenFormula(matrix1: (b - d), matrix2: (g + h)) |
||
// (a - c) * (e + f) |
|||
let p7 = strassenFormula(matrix1: (a - c), matrix2: (e + f)) |
|||
// p5 + p4 - p2 + p6 |
|||
let result11 = p5 + p4 - p2 + p6 |
|||
// p1 + p2 |
|||
let result12 = p1 + p2 |
|||
| ⚫ | |||
let result21 = p3 + p4 |
|||
// p1 + p5 - p3 - p7 |
|||
let result22 = p1 + p5 - p3 - p7 |
|||
// create an empty matrix for result and fill with values |
|||
var result = Matrix(rows: matrix1.rows, columns: matrix1.rows) |
var result = Matrix(rows: matrix1.rows, columns: matrix1.rows) |
||
for i in 0..<rowHalf { |
for i in 0..<rowHalf { |
||