Strassen's algorithm: Difference between revisions
Content added Content deleted
(A Python implementation) |
m (→{{header|Phix}}: added syntax colouring, made p2js compatible) |
||
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. |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer l = length(a) |
|||
<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> |
|||
if length(a[1])!=l |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> |
|||
or length(b)!=l |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">l</span> |
|||
or length(b[1])!=l then |
|||
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">l</span> |
|||
crash("two equal square matrices only") |
|||
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"two equal square matrices only"</span><span style="color: #0000FF;">)</span> |
|||
if l=1 then return sq_mul(a,b) end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if remainder(l,1) then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</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;">end</span> <span style="color: #008080;">if</span> |
|||
crash("2^n matrices only") |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"2^n matrices only"</span><span style="color: #0000FF;">)</span> |
|||
integer h = l/2 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
sequence {a11,a12,a21,a22,b11,b12,b21,b22} @= repeat(repeat(0,h),h) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> |
|||
for i=1 to h do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">a11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b22</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">),</span><span style="color: #000000;">h</span><span style="color: #0000FF;">),</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span> |
|||
for j=1 to h do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h</span> <span style="color: #008080;">do</span> |
|||
a11[i][j] = a[i][j] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h</span> <span style="color: #008080;">do</span> |
|||
a12[i][j] = a[i][j+h] |
|||
<span style="color: #000000;">a11</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
a21[i][j] = a[i+h][j] |
|||
<span style="color: #000000;">a12</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> |
|||
a22[i][j] = a[i+h][j+h] |
|||
<span style="color: #000000;">a21</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
b11[i][j] = b[i][j] |
|||
<span style="color: #000000;">a22</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> |
|||
b12[i][j] = b[i][j+h] |
|||
<span style="color: #000000;">b11</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
b21[i][j] = b[i+h][j] |
|||
<span style="color: #000000;">b12</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> |
|||
b22[i][j] = b[i+h][j+h] |
|||
<span style="color: #000000;">b21</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">b22</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
sequence p1 = strassen(sq_sub(a12,a22), sq_add(b21,b22)), |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
p2 = strassen(sq_add(a11,a22), sq_add(b11,b22)), |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a22</span><span style="color: #0000FF;">),</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b22</span><span style="color: #0000FF;">)),</span> |
|||
p3 = strassen(sq_sub(a11,a21), sq_add(b11,b12)), |
|||
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a22</span><span style="color: #0000FF;">),</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b22</span><span style="color: #0000FF;">)),</span> |
|||
p4 = strassen(sq_add(a11,a12), b22), |
|||
<span style="color: #000000;">p3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a21</span><span style="color: #0000FF;">),</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b12</span><span style="color: #0000FF;">)),</span> |
|||
p5 = strassen(a11, sq_sub(b12,b22)), |
|||
<span style="color: #000000;">p4</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a12</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">b22</span><span style="color: #0000FF;">),</span> |
|||
p6 = strassen(a22, sq_sub(b21,b11)), |
|||
<span style="color: #000000;">p5</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a11</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b22</span><span style="color: #0000FF;">)),</span> |
|||
p7 = strassen(sq_add(a21,a22), b11), |
|||
<span style="color: #000000;">p6</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a22</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b11</span><span style="color: #0000FF;">)),</span> |
|||
<span style="color: #000000;">p7</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">strassen</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a22</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">b11</span><span style="color: #0000FF;">),</span> |
|||
c11 = sq_add(sq_sub(sq_add(p1,p2),p4),p6), |
|||
c12 = sq_add(p4,p5), |
|||
<span style="color: #000000;">c11</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">),</span><span style="color: #000000;">p4</span><span style="color: #0000FF;">),</span><span style="color: #000000;">p6</span><span style="color: #0000FF;">),</span> |
|||
c21 = sq_add(p6,p7), |
|||
<span style="color: #000000;">c12</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">),</span> |
|||
c22 = sq_sub(sq_add(sq_sub(p2,p3),p5),p7), |
|||
<span style="color: #000000;">c21</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p7</span><span style="color: #0000FF;">),</span> |
|||
c = repeat(repeat(0,l),l) |
|||
<span style="color: #000000;">c22</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">),</span><span style="color: #000000;">p7</span><span style="color: #0000FF;">),</span> |
|||
for i=1 to h do |
|||
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
for j=1 to h do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h</span> <span style="color: #008080;">do</span> |
|||
c[i][j] = c11[i][j] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">h</span> <span style="color: #008080;">do</span> |
|||
c[i][j+h] = c12[i][j] |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c11</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
c[i+h][j] = c21[i][j] |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c12</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
c[i+h][j+h] = c22[i][j] |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c21</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c22</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return c |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
ppOpt({pp_Nest,1,pp_IntFmt,"%3d",pp_FltFmt,"%3.0f",pp_IntCh,false}) |
|||
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_FltFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3.0f"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
|||
constant A = {{1,2}, |
|||
{3,4}}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">A</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> |
|||
B = {{5,6}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}},</span> |
|||
{7,8}} |
|||
<span style="color: #000000;">B</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span> |
|||
pp(strassen(A,B)) |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</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;">A</span><span style="color: #0000FF;">,</span><span style="color: #000000;">B</span><span style="color: #0000FF;">))</span> |
|||
constant C = { { 1, 1, 1, 1 }, |
|||
{ 2, 4, 8, 16 }, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">C</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">},</span> |
|||
{ 3, 9, 27, 81 }, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">16</span> <span style="color: #0000FF;">},</span> |
|||
{ 4, 16, 64, 256 }}, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">81</span> <span style="color: #0000FF;">},</span> |
|||
D = { { 4, -3, 4/3, -1/ 4 }, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">16</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">64</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">256</span> <span style="color: #0000FF;">}},</span> |
|||
{-13/3, 19/4, -7/3, 11/24 }, |
|||
<span style="color: #000000;">D</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">/</span> <span style="color: #000000;">4</span> <span style="color: #0000FF;">},</span> |
|||
{ 3/2, -2, 7/6, -1/ 4 }, |
|||
<span style="color: #0000FF;">{-</span><span style="color: #000000;">13</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">/</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">/</span><span style="color: #000000;">24</span> <span style="color: #0000FF;">},</span> |
|||
{ -1/6, 1/4, -1/6, 1/24 }} |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">/</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">/</span> <span style="color: #000000;">4</span> <span style="color: #0000FF;">},</span> |
|||
pp(strassen(C,D)) |
|||
<span style="color: #0000FF;">{</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">24</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;">C</span><span style="color: #0000FF;">,</span><span style="color: #000000;">D</span><span style="color: #0000FF;">))</span> |
|||
constant E = {{ 1, 2, 3, 4}, |
|||
{ 5, 6, 7, 8}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">F</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> |
|||
{ 9,10,11,12}, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> |
|||
{13,14,15,16}}, |
|||
<span style="color: #0000FF;">{</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},</span> |
|||
F = {{1, 0, 0, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">}},</span> |
|||
{0, 1, 0, 0}, |
|||
<span style="color: #000000;">G</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0, 1, 0}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
{0, 0, 0, 1}} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> |
|||
pp(strassen(E,F)) |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</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;">F</span><span style="color: #0000FF;">,</span><span style="color: #000000;">G</span><span style="color: #0000FF;">))</span> |
|||
constant r = sqrt(2)/2, |
|||
R = {{ r,r}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> |
|||
{-r,r}} |
|||
<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> |
|||
pp(strassen(R,R))</lang> |
|||
<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> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
Matches that of [[Matrix_multiplication#Phix]], when given the same inputs |
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. |
||
<pre> |
<pre> |
||
{{ 19, 22}, |
{{ 19, 22}, |