Strassen's algorithm: Difference between revisions

{{trans|Wren}}

Rather than use a library such as gonum, we create a simple Matrix type which is adequate for this task.

 

import (

fmt.Printf(" c * d = %v\n", strassen(c, d).toString(6))

fmt.Printf(" e * f = %v\n", strassen(e, f))

 

{{out}}

===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.

Strassen's matrix multiplication algorithm.

Use dynamic padding in order to reduce required auxiliary memory.

intprint("Regular multiply: ", R * R)

intprint("Strassen multiply: ", strassen(R,R))

<pre>

Regular multiply: [19 43; 22 50]

===Recursive===

Output is the same as the dynamically padded version.

n = size(A, 1)

if n == 1

intprint("Regular multiply: ", R * R)

intprint("Strassen multiply: ", Strassen(R,R))

 

=={{header|Nim}}==

{{trans|Go}}

{{trans|Wren}}

 

type Matrix = seq[seq[float]]

echo " a * b = ", strassen(a, b).toString(10)

echo " c * d = ", strassen(c, d).toString(6)

 

{{out}}

=={{header|Phix}}==

As noted on wp, you could pad with zeroes, and strip them on exit, instead of crashing for non-square 2^{<small>n</small>} matrices.

<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: #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>

{{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.

 

=={{header|Python}}==

 

from __future__ import annotations

if __name__ == "__main__":

examples()

 

{{out}}

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}}

 

use Math::Libgsl::Constants;

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

{{out}}

<pre>Regular multiply:

=={{header|Swift}}==

[https://github.com/hollance/Matrix/blob/master/Matrix.swift '''Matrix Class'''] by [https://github.com/ozgurshn ozgurshn]

// Matrix Strassen Multiplication

func strassenMultiply(matrix1: Matrix, matrix2: Matrix) -> Matrix {

print(result3.description)

}

 

{{out}}

 

I've used the Phix entry's examples to test the Strassen algorithm implementation.

construct new(a) {

if (a.type != List || a.count == 0 || a[0].type != List || a[0].count == 0 || a[0][0].type != Num) {

System.print(" a * b = %(strassen.call(a, b))")

System.print(" c * d = %(strassen.call(c, d).toString(6))")

 

{{out}}

{{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.

var params = Fn.new { |r, c|

System.print(" a * b = %(strassen.call(a, b))")

System.print(" c * d = %(strassen.call(c, d).toString(6))")