Algorytm Winograda

Z Lem
Skocz do: nawigacji, wyszukiwania

(* Algorytm Winograda mnozenia macierzy o rozmiarze n x n *)

program Winograd;

signal Niezgoda;

unit Winograd: procedure(A,B: arrayof arrayof real; output C: arrayof arrayof real);

var i,j,k,n,m: integer,
W,V: arrayof real,
p: boolean,
s: real;

begin (* ustalic czy macierze moga byc mnozone tzn. czy ilosc wierszy w A = ilosc kolumn w B? *) (* ustalic czy n jest parzyste? *) (* obliczyc "preprocessing" *)

i := upper(A);
j := lower(A);
k := i-j;
i:= upper(B);
j:= lower(B);
if i-j <> k then raise Niezgoda fi;
(* mozna mnozyc *)
n := k+1;
p := (n mod 2) = 0;
m := n div 2;
array W dim (1:n);
array V dim (1:n);
array C dim (1:n);
for i := 1 to n
do
array C(i) dim (1:n)
od;
(* obliczanie "preprocessingu" *)
for j:= 1 to n
do
s:=0;
for i := 1 to m
do
s := A(j,2*i-1) * A(j,2*i) +s;
od;
W(j) := s;
od;
for j:= 1 to n
do
s:=0;
for i := 1 to m
do
s := B(2*i-1,j) * B(2*i,j) +s;
od;
V(j) := s;
od;
(* obliczanie iloczynu macierzy *)
for i := 1 to n
do
for j := 1 to n
do
s:= 0;
for k:= 1 to m
do
s:= (A(i,2*k-1)+B(2*k,j)) * (B(2*k-1,j)+A(i,2*k)) +s;
od;
C(i,j) :=s-W(i)-V(j);
if not p
then
C(i,j) := C(i,j) + A(i,n)*B(n,j);
fi;
od;
od;

end Winograd;

(* ------------------------------------------------------------------------- *)
var M1,K1,J1,J2 : arrayof arrayof real,
i,j,n,t,k : integer,
s: real;

begin (*programu *)

write("podaj wartosc n=");
readln(n);writeln(n);
array M1 dim (1:n);
array K1 dim (1:n);
array J1 dim (1:n);
array J2 dim (1:n);
for i := 1 to n do
array M1(i) dim (1:n);
array K1(i) dim (1:n);
array J1(i) dim (1:n);
array J2(i) dim (1:n);
od;
for i := 1 to n do
for j := 1 to n do
if i=j then M1(i,j):= 1 else M1(i,j):=0 fi;
K1(i,j):= (i-1)*n+j;
od;
od;
t:=time;
call Winograd(M1,K1,J1);
t:=time - t;
writeln("czas Win=",t:6);
t:=time;
for i:=1 to n do
for j:=1 to n do
s:=0;
for k:=1 to n do
s := s + M1(i,k)*K1(k,j);
od;
J2(i,j):=s;
od;
od;
t:=time-t;
writeln("czas norm=",t:6);


for i := 1 to n do
writeln;
for j := 1 to n do
write(J1(i,j):5:0);
od;
od;


end program;