Strassen's algorithm: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Added a version which uses Wren-matrix (retaining original as there are translations of it).) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 24: | Line 24: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
Rather than use a library such as gonum, we create a simple Matrix type which is adequate for this task. |
Rather than use a library such as gonum, we create a simple Matrix type which is adequate for this task. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 188: | Line 188: | ||
fmt.Printf(" c * d = %v\n", strassen(c, d).toString(6)) |
fmt.Printf(" c * d = %v\n", strassen(c, d).toString(6)) |
||
fmt.Printf(" e * f = %v\n", strassen(e, f)) |
fmt.Printf(" e * f = %v\n", strassen(e, f)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 206: | Line 206: | ||
===With dynamic padding=== |
===With dynamic padding=== |
||
Because Julia uses column major in matrices, sometimes the code uses the adjoint of a matrix in order to match examples as written. |
Because Julia uses column major in matrices, sometimes the code uses the adjoint of a matrix in order to match examples as written. |
||
< |
<syntaxhighlight lang="julia">""" |
||
Strassen's matrix multiplication algorithm. |
Strassen's matrix multiplication algorithm. |
||
Use dynamic padding in order to reduce required auxiliary memory. |
Use dynamic padding in order to reduce required auxiliary memory. |
||
Line 323: | Line 323: | ||
intprint("Regular multiply: ", R * R) |
intprint("Regular multiply: ", R * R) |
||
intprint("Strassen multiply: ", strassen(R,R)) |
intprint("Strassen multiply: ", strassen(R,R)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Regular multiply: [19 43; 22 50] |
Regular multiply: [19 43; 22 50] |
||
Line 337: | Line 337: | ||
===Recursive=== |
===Recursive=== |
||
Output is the same as the dynamically padded version. |
Output is the same as the dynamically padded version. |
||
< |
<syntaxhighlight lang="julia">function Strassen(A, B) |
||
n = size(A, 1) |
n = size(A, 1) |
||
if n == 1 |
if n == 1 |
||
Line 387: | Line 387: | ||
intprint("Regular multiply: ", R * R) |
intprint("Regular multiply: ", R * R) |
||
intprint("Strassen multiply: ", Strassen(R,R)) |
intprint("Strassen multiply: ", Strassen(R,R)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="nim">import math, sequtils, strutils |
||
type Matrix = seq[seq[float]] |
type Matrix = seq[seq[float]] |
||
Line 531: | Line 531: | ||
echo " a * b = ", strassen(a, b).toString(10) |
echo " a * b = ", strassen(a, b).toString(10) |
||
echo " c * d = ", strassen(c, d).toString(6) |
echo " c * d = ", strassen(c, d).toString(6) |
||
echo " e * f = ", strassen(e, f).toString(10)</ |
echo " e * f = ", strassen(e, f).toString(10)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 546: | Line 546: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
As noted on wp, you could pad with zeroes, and strip them on exit, instead of crashing for non-square 2<sup><small>n</small></sup> matrices. |
As noted on wp, you could pad with zeroes, and strip them on exit, instead of crashing for non-square 2<sup><small>n</small></sup> matrices. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> |
||
Line 629: | Line 629: | ||
<span style="color: #0000FF;">{-</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}}</span> |
<span style="color: #0000FF;">{-</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">}}</span> |
||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">R</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">R</span><span style="color: #0000FF;">,</span><span style="color: #000000;">R</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
Matches that of [[Matrix_multiplication#Phix]], when given the same inputs. Note that a few "-0" show up in the second one (the identity matrix) under pwa/p2js. |
Matches that of [[Matrix_multiplication#Phix]], when given the same inputs. Note that a few "-0" show up in the second one (the identity matrix) under pwa/p2js. |
||
Line 648: | Line 648: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">"""Matrix multiplication using Strassen's algorithm. Requires Python >= 3.7.""" |
||
from __future__ import annotations |
from __future__ import annotations |
||
Line 814: | Line 814: | ||
if __name__ == "__main__": |
if __name__ == "__main__": |
||
examples() |
examples() |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 831: | Line 831: | ||
Special thanks go to the module author, [https://github.com/frithnanth Fernando Santagata], on showing how to deal with a pass-by-value case. |
Special thanks go to the module author, [https://github.com/frithnanth Fernando Santagata], on showing how to deal with a pass-by-value case. |
||
{{trans|Julia}} |
{{trans|Julia}} |
||
<lang |
<syntaxhighlight lang="raku" line># 20210126 Raku programming solution |
||
use Math::Libgsl::Constants; |
use Math::Libgsl::Constants; |
||
Line 924: | Line 924: | ||
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 |
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 |
||
1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1 |
1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1 |
||
=end code</ |
=end code</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Regular multiply: |
<pre>Regular multiply: |
||
Line 955: | Line 955: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
[https://github.com/hollance/Matrix/blob/master/Matrix.swift '''Matrix Class'''] by [https://github.com/ozgurshn ozgurshn] |
[https://github.com/hollance/Matrix/blob/master/Matrix.swift '''Matrix Class'''] by [https://github.com/ozgurshn ozgurshn] |
||
< |
<syntaxhighlight lang="swift"> |
||
// Matrix Strassen Multiplication |
// Matrix Strassen Multiplication |
||
func strassenMultiply(matrix1: Matrix, matrix2: Matrix) -> Matrix { |
func strassenMultiply(matrix1: Matrix, matrix2: Matrix) -> Matrix { |
||
Line 1,118: | Line 1,118: | ||
print(result3.description) |
print(result3.description) |
||
} |
} |
||
main()</ |
main()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,144: | Line 1,144: | ||
I've used the Phix entry's examples to test the Strassen algorithm implementation. |
I've used the Phix entry's examples to test the Strassen algorithm implementation. |
||
< |
<syntaxhighlight lang="ecmascript">class Matrix { |
||
construct new(a) { |
construct new(a) { |
||
if (a.type != List || a.count == 0 || a[0].type != List || a[0].count == 0 || a[0][0].type != Num) { |
if (a.type != List || a.count == 0 || a[0].type != List || a[0].count == 0 || a[0][0].type != Num) { |
||
Line 1,297: | Line 1,297: | ||
System.print(" a * b = %(strassen.call(a, b))") |
System.print(" a * b = %(strassen.call(a, b))") |
||
System.print(" c * d = %(strassen.call(c, d).toString(6))") |
System.print(" c * d = %(strassen.call(c, d).toString(6))") |
||
System.print(" e * f = %(strassen.call(e, f))")</ |
System.print(" e * f = %(strassen.call(e, f))")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,314: | Line 1,314: | ||
{{libheader|Wren-matrix}} |
{{libheader|Wren-matrix}} |
||
Since the above version was written, a Matrix module has been added and the following version uses it. The output is exactly the same as before. |
Since the above version was written, a Matrix module has been added and the following version uses it. The output is exactly the same as before. |
||
< |
<syntaxhighlight lang="ecmascript">import "./matrix" for Matrix |
||
var params = Fn.new { |r, c| |
var params = Fn.new { |r, c| |
||
Line 1,397: | Line 1,397: | ||
System.print(" a * b = %(strassen.call(a, b))") |
System.print(" a * b = %(strassen.call(a, b))") |
||
System.print(" c * d = %(strassen.call(c, d).toString(6))") |
System.print(" c * d = %(strassen.call(c, d).toString(6))") |
||
System.print(" e * f = %(strassen.call(e, f))")</ |
System.print(" e * f = %(strassen.call(e, f))")</syntaxhighlight> |