Algorytm Winograda: Różnice pomiędzy wersjami

Wersja z 14:06, 12 lut 2013

(* 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;�