clc;
clear all;
close all;
format long e;

% for n=1:8
%     k = 2^n;
%     A = rand(k,k);
%     B = rand(k,k);
% %     tic
%     C = A * B;
% %     toc
% end
%
% for n=1:8
%     k = 2^n;
%     A = rand(k,k);
%     B = rand(k,k);
%     tic
%     for i=1:length(A)
%        for j=1:length(A)
%            C(i,j) = 0;
%            for x=1:length(A)
%                C(i,j) = C(i,j) + A(i,x) * B(x,j);
%            end
%        end
%     end
%     toc
% end
for n=1:8
    k = 2^n;
    A = rand(k,k);
    B = rand(k,k);
    for r=0:4
        R=2^r;
        fprintf('n= %d, R=%d\n',n,R);
        tic
        C=strassen(A,B,R);
        toc
    end
end



function C = strassen(A, B, R)
if nargin < 3; end
    n = length(A);
    if n <= R
       C = A*B;
    else
       m = n/2; i = 1:m; j = m+1:n;
       P1 = strassen( A(i,i)+A(j,j), B(i,i)+B(j,j), R);
       P2 = strassen( A(j,i)+A(j,j), B(i,i), R);
       P3 = strassen( A(i,i), B(i,j)-B(j,j), R);
       P4 = strassen( A(j,j), B(j,i)-B(i,i), R);
       P5 = strassen( A(i,i)+A(i,j), B(j,j), R);
       P6 = strassen( A(j,i)-A(i,i), B(i,i)+B(i,j), R);
       P7 = strassen( A(i,j)-A(j,j), B(j,i)+B(j,j), R);
       C = [ P1+P4-P5+P7  P3+P5;  P2+P4  P1+P3-P2+P6  ];
    end
end