Rosetta Code

Strassen's algorithm: Difference between revisions

Page Discussion

Strassen's algorithm (view source)

Revision as of 20:27, 27 January 2021

190 bytes added ,  3 years ago
→‎{{header|Raku}}: minor updates + some comments
(added Raku programming solution)
(→‎{{header|Raku}}: minor updates + some comments)
Line 490:
use Math::Libgsl::Matrix;
use Math::Libgsl::BLAS;
 
my @M;
 
sub SQM (\in) { # create custom sq matrix from CSV
die "Not a ■" if (my \L = in.split(/\,/)).sqrt != (my \size = L.sqrt.Int);
Line 499:
M
}
 
sub infix:<⊗>(\x,\y) { # custom multiplication
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2;
Line 505:
z
}
 
sub infix:<⊕>(\x,\y) { # custom addition
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2;
Line 511:
z
}
 
sub infix:<⊖>(\x,\y) { # custom subtraction
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2;
Line 517:
z
}
 
sub Strassen($A, $B) {
 
{ return $A ⊗ $B } if (my \n = $A.size1) == 1;
 
my Math::Libgsl::Matrix ($A11,$A12,$A21,$A22,$B11,$B12,$B21,$B22);
my Math::Libgsl::Matrix ($P1,$P2,$P3,$P4,$P5,$P6,$P7);
my Math::Libgsl::Matrix ($C11,$C12,$C21,$C22);▼
my Math::Libgsl::Matrix::View ($mv1,$mv2,$mv3,$mv4,$mv5,$mv6,$mv7,$mv8);
($mv1,$mv2,$mv3,$mv4,$mv5,$mv6,$mv7,$mv8)».&{ $_ .= new };
 
my \half = n div 2; # dimension of quarter submatrices
$A11 = $mv1.submatrix($A, 0,0, n div 2,n div 2); ▼
$A12 = $mv2.submatrix($A, 0,n div 2, n div 2,n div 2); ▼
$A21 = $mv3.submatrix($A, n div 2,0, n div 2,n div 2); ▼
$A22 = $mv4.submatrix($A, n div 2,n div 2, n div 2,n div 2); ▼
$B11 = $mv5.submatrix($B, 0,0, n div 2,n div 2); ▼
$B12 = $mv6.submatrix($B, 0,n div 2, n div 2,n div 2); ▼
$B21 = $mv7.submatrix($B, n div 2,0, n div 2,n div 2); ▼
$B22 = $mv8.submatrix($B, n div 2,n div 2, n div 2,n div 2);
 
▲ $A11 = $mv1.submatrix($A, 0,0, n div 2half,n div 2half); #
$A12 = $mv2.submatrix($A, 0,half, half,half); # create quarter views
▲ $A21 = $mv3.submatrix($A, n div 2half,0, half,half); # of noperand div 2,n div 2);matrices
▲ $A22 = $mv4.submatrix($A, n div 2half,n div 2half, n div 2half,n div 2half); #
▲ $B11 = $mv5.submatrix($B, 0,0, half,half); # n div11 2,n div 2); 12
▲ $A12B12 = $mv2mv6.submatrix($AB, 0,n div 2half, n div 2half,n div 2half); #
▲ $B12B21 = $mv6mv7.submatrix($B, half,0,n div 2 half,half); # n21 div 2,n div 2);22
▲ $B21B22 = $mv7mv8.submatrix($B, n div 2half,0half, n div 2half,n div 2half); #
$P1 = Strassen($A12 ⊖ $A22, $B21 ⊕ $B22);
$P2 = Strassen($A11 ⊕ $A22, $B11 ⊕ $B22);
Line 544 ⟶ 545:
$P6 = Strassen($A22, $B21 ⊖ $B11);
$P7 = Strassen($A21 ⊕ $A22, $B11 );
my Math::Libgsl::Matrix $C .= new: n, n; # Build C from▼
▲ my Math::Libgsl::Matrix ::View ($C11mvC11,$C12mvC12,$C21mvC21,$C22mvC22); # C11 C12
($mvC11,$mvC12,$mvC21,$mvC22)».=new ; # C21 C22
 
given $C11mvC11.submatrix($C, 0,0, half,half) { =.add: (($P1 ⊕ $P2) ⊖ $P4) ⊕ $P6 };
given $mvC12.submatrix($C12C, =0,half, half,half) { .add: $P4 ⊕ $P5 };
given $mvC21.submatrix($C21C, =half,0, half,half) { .add: $P6 ⊕ $P7 };
given $mvC22.submatrix($C22C, =half,half, half,half) { .add: (($P2 ⊖ $P3) ⊕ $P5) ⊖ $P7 };
 
▲ my Math::Libgsl::Matrix $C .= new: n, n;
my $h = n div 2;
for ^$h X ^$h -> ($i,$j) {
$C[$i;$j] = $C11[$i;$j];
$C[$i;$j+$h] = $C12[$i;$j];
$C[$i+$h;$j] = $C21[$i;$j];
$C[$i+$h;$j+$h] = $C22[$i;$j];
}
$C
}
 
for $=pod[0].contents { next if /^\n$/ ; @M.append: SQM $_ }
 
for @M.rotor(2) {
my $product = @_[0] ⊗ ⊗ @_[1];
# $product.get-row($_)».round(1).fmt('%2d').put for ^$product.size1;
 
say "Regular multiply:";
$product.get-row($_)».fmt('%.10g').put for ^$product.size1;
 
$product = Strassen @_[0], @_[1];
 
say "Strassen multiply:";
$product.get-row($_)».fmt('%.10g').put for ^$product.size1;
}
 
=begin code
1,2,3,4
Line 611 ⟶ 608:
9 10 11 12
13 14 15 16</pre>
 
 
=={{header|Wren}}==
Hkdtam
351

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/302524"