Strassen's algorithm: Difference between revisions
Content added Content deleted
(added Raku programming solution) |
(→{{header|Raku}}: minor updates + some comments) |
||
Line 490: | Line 490: | ||
use Math::Libgsl::Matrix; |
use Math::Libgsl::Matrix; |
||
use Math::Libgsl::BLAS; |
use Math::Libgsl::BLAS; |
||
my @M; |
my @M; |
||
sub SQM (\in) { # create custom sq matrix from CSV |
sub SQM (\in) { # create custom sq matrix from CSV |
||
die "Not a ■" if (my \L = in.split(/\,/)).sqrt != (my \size = L.sqrt.Int); |
die "Not a ■" if (my \L = in.split(/\,/)).sqrt != (my \size = L.sqrt.Int); |
||
Line 499: | Line 499: | ||
M |
M |
||
} |
} |
||
sub infix:<⊗>(\x,\y) { # custom multiplication |
sub infix:<⊗>(\x,\y) { # custom multiplication |
||
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
||
Line 505: | Line 505: | ||
z |
z |
||
} |
} |
||
sub infix:<⊕>(\x,\y) { # custom addition |
sub infix:<⊕>(\x,\y) { # custom addition |
||
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
||
Line 511: | Line 511: | ||
z |
z |
||
} |
} |
||
sub infix:<⊖>(\x,\y) { # custom subtraction |
sub infix:<⊖>(\x,\y) { # custom subtraction |
||
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
my Math::Libgsl::Matrix \z .= new: x.size1, x.size2; |
||
Line 517: | Line 517: | ||
z |
z |
||
} |
} |
||
sub Strassen($A, $B) { |
sub Strassen($A, $B) { |
||
{ return $A ⊗ $B } if (my \n = $A.size1) == 1; |
{ 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 ($A11,$A12,$A21,$A22,$B11,$B12,$B21,$B22); |
||
my Math::Libgsl::Matrix ($P1,$P2,$P3,$P4,$P5,$P6,$P7); |
my Math::Libgsl::Matrix ($P1,$P2,$P3,$P4,$P5,$P6,$P7); |
||
⚫ | |||
my Math::Libgsl::Matrix::View ($mv1,$mv2,$mv3,$mv4,$mv5,$mv6,$mv7,$mv8); |
my Math::Libgsl::Matrix::View ($mv1,$mv2,$mv3,$mv4,$mv5,$mv6,$mv7,$mv8); |
||
($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 |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
$B22 = $mv8.submatrix($B, n div 2,n div 2, n div 2,n div 2); |
|||
⚫ | |||
$A12 = $mv2.submatrix($A, 0,half, half,half); # create quarter views |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
$P1 = Strassen($A12 ⊖ $A22, $B21 ⊕ $B22); |
$P1 = Strassen($A12 ⊖ $A22, $B21 ⊕ $B22); |
||
$P2 = Strassen($A11 ⊕ $A22, $B11 ⊕ $B22); |
$P2 = Strassen($A11 ⊕ $A22, $B11 ⊕ $B22); |
||
Line 544: | Line 545: | ||
$P6 = Strassen($A22, $B21 ⊖ $B11); |
$P6 = Strassen($A22, $B21 ⊖ $B11); |
||
$P7 = Strassen($A21 ⊕ $A22, $B11 ); |
$P7 = Strassen($A21 ⊕ $A22, $B11 ); |
||
⚫ | |||
⚫ | |||
($mvC11,$mvC12,$mvC21,$mvC22)».=new ; # C21 C22 |
|||
$ |
given $mvC11.submatrix($C, 0,0, half,half) { .add: (($P1 ⊕ $P2) ⊖ $P4) ⊕ $P6 }; |
||
$ |
given $mvC12.submatrix($C, 0,half, half,half) { .add: $P4 ⊕ $P5 }; |
||
$ |
given $mvC21.submatrix($C, half,0, half,half) { .add: $P6 ⊕ $P7 }; |
||
$ |
given $mvC22.submatrix($C, half,half, half,half) { .add: (($P2 ⊖ $P3) ⊕ $P5) ⊖ $P7 }; |
||
⚫ | |||
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 |
$C |
||
} |
} |
||
for $=pod[0].contents { next if /^\n$/ ; @M.append: SQM $_ } |
for $=pod[0].contents { next if /^\n$/ ; @M.append: SQM $_ } |
||
for @M.rotor(2) { |
for @M.rotor(2) { |
||
my $product = @_[0] |
my $product = @_[0] ⊗ @_[1]; |
||
# $product.get-row($_)».round(1).fmt('%2d').put for ^$product.size1; |
# $product.get-row($_)».round(1).fmt('%2d').put for ^$product.size1; |
||
say "Regular multiply:"; |
say "Regular multiply:"; |
||
$product.get-row($_)».fmt('%.10g').put for ^$product.size1; |
$product.get-row($_)».fmt('%.10g').put for ^$product.size1; |
||
$product = Strassen @_[0], @_[1]; |
$product = Strassen @_[0], @_[1]; |
||
say "Strassen multiply:"; |
say "Strassen multiply:"; |
||
$product.get-row($_)».fmt('%.10g').put for ^$product.size1; |
$product.get-row($_)».fmt('%.10g').put for ^$product.size1; |
||
} |
} |
||
=begin code |
=begin code |
||
1,2,3,4 |
1,2,3,4 |
||
Line 611: | Line 608: | ||
9 10 11 12 |
9 10 11 12 |
||
13 14 15 16</pre> |
13 14 15 16</pre> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |