Algorytm Winograda: Różnice pomiędzy wersjami

Z Lem
Skocz do: nawigacji, wyszukiwania
(Utworzył nową stronę „(* Algorytm Winograda mnozenia macierzy o rozmiarze n x n *) '''program''' Winograd; '''signal''' Niezgoda; '''unit''' Winograd: '''procedure'''(A,B: '''arrayof a...”)
 
 
Linia 3: Linia 3:
 
'''program''' Winograd;
 
'''program''' Winograd;
  
−
'''signal''' Niezgoda;
+
:'''signal''' Niezgoda;
  
 
'''unit''' Winograd: '''procedure'''(A,B: '''arrayof arrayof''' real;
 
'''unit''' Winograd: '''procedure'''(A,B: '''arrayof arrayof''' real;
Linia 37: Linia 37:
 
::  '''array''' C(i) '''dim''' (1:n)
 
::  '''array''' C(i) '''dim''' (1:n)
 
:'''od''';   
 
:'''od''';   
−
(* obliczanie "preprocessingu" *)
+
:(* obliczanie "preprocessingu" *)
−
for j:= 1 to n
+
:'''for''' j:= 1 '''to''' n
−
do
+
:'''do'''
−
  s:=0;
+
::  s:=0;
−
  for i := 1 to m  
+
::  '''for''' i := 1 '''to''' m  
−
  do
+
::  '''do'''
−
    s := A(j,2*i-1) * A(j,2*i) +s;
+
:::    s := A(j,2*i-1) * A(j,2*i) +s;
−
  od;
+
::  '''od''';
−
  W(j) := s;
+
::  W(j) := s;
−
od;
+
:'''od''';
−
for j:= 1 to n
+
:'''for''' j:= 1 '''to''' n
−
do
+
:'''do'''
−
  s:=0;
+
::  s:=0;
−
  for i := 1 to m  
+
::  '''for''' i := 1 '''to''' m  
−
  do
+
::  '''do'''
−
    s := B(2*i-1,j) * B(2*i,j) +s;
+
:::    s := B(2*i-1,j) * B(2*i,j) +s;
−
  od;
+
::  '''od''';
−
  V(j) := s;
+
::  V(j) := s;
−
od;
+
:'''od''';
  
−
(* obliczanie iloczynu macierzy *)
+
:(* obliczanie iloczynu macierzy *)
−
for i := 1 to n
+
:'''for''' i := 1 '''to''' n
−
do
+
:'''do'''
−
  for j := 1 to n
+
::  '''for''' j := 1 '''to''' n
−
  do
+
::  '''do'''
−
    s:= 0;
+
:::    s:= 0;
−
    for k:= 1 to m
+
:::    '''for''' k:= 1 '''to''' m
−
    do
+
:::    '''do'''
−
      s:= (A(i,2*k-1)+B(2*k,j)) * (B(2*k-1,j)+A(i,2*k)) +s;
+
::::      s:= (A(i,2*k-1)+B(2*k,j)) * (B(2*k-1,j)+A(i,2*k)) +s;
−
    od;
+
:::    '''od''';
−
    C(i,j) :=s-W(i)-V(j);
+
:::    C(i,j) :=s-W(i)-V(j);
−
    if not p
+
:::    '''if''' '''not''' p
−
    then  
+
:::    '''then'''
−
      C(i,j) := C(i,j) + A(i,n)*B(n,j);
+
::::      C(i,j) := C(i,j) + A(i,n)*B(n,j);
−
    fi;
+
:::    '''fi''';
−
  od;
+
::  '''od''';
−
od;       
+
:'''od''';       
−
end Winograd;
+
'''end''' Winograd;
−
 
+
:(* ------------------------------------------------------------------------- *)
−
var M1,K1,J1,J2 : arrayof arrayof real,
+
−
    i,j,n,t,k : integer,
+
−
    s: real;
+
  
 +
:'''var''' M1,K1,J1,J2 : arrayof arrayof real,
 +
::    i,j,n,t,k : integer,
 +
::    s: real;
  
−
(* ------------------------------------------------------------------------- *)
+
'''begin''' (*programu *)
−
begin (*programu *)
+
:  write("podaj wartosc n=");
−
  write("podaj wartosc n=");
+
:  readln(n);writeln(n);
−
  readln(n);writeln(n);
+
:  '''array''' M1 '''dim''' (1:n);
−
  array M1 dim (1:n);
+
:  '''array''' K1 '''dim''' (1:n);
−
  array K1 dim (1:n);
+
:  '''array''' J1 '''dim''' (1:n);
−
  array J1 dim (1:n);
+
:  '''array''' J2 '''dim''' (1:n);
−
  array J2 dim (1:n);
+
:  '''for''' i := 1 '''to''' n '''do'''
−
  for i := 1 to n do
+
::    '''array''' M1(i) dim (1:n);
−
    array M1(i) dim (1:n);
+
::    array K1(i) dim (1:n);
−
    array K1(i) dim (1:n);
+
::    array J1(i) dim (1:n);
−
    array J1(i) dim (1:n);
+
::    array J2(i) dim (1:n);
−
    array J2(i) dim (1:n);
+
:  od;     
−
  od;     
+
:  for i := 1 to n do
−
  for i := 1 to n do
+
::  for j := 1 to n do
−
  for j := 1 to n do
+
:::    if i=j then M1(i,j):= 1 else M1(i,j):=0 fi;
−
    if i=j then M1(i,j):= 1 else M1(i,j):=0 fi;
+
:::    K1(i,j):= (i-1)*n+j;
−
    K1(i,j):= (i-1)*n+j;
+
::  od;
−
  od;
+
:  od;
−
  od;
+
 
    
 
    
−
  t:=time;
+
:  t:=time;
−
  call Winograd(M1,K1,J1);
+
:  call Winograd(M1,K1,J1);
−
  t:=time - t;
+
:  t:=time - t;
−
  writeln("czas Win=",t:6);
+
:  writeln("czas Win=",t:6);
 
    
 
    
−
  t:=time;
+
:  t:=time;
−
  for i:=1 to n do
+
:  for i:=1 to n do
−
  for j:=1 to n do
+
::  for j:=1 to n do
−
    s:=0;
+
:::    s:=0;
−
    for k:=1 to n do
+
:::    for k:=1 to n do
−
      s := s + M1(i,k)*K1(k,j);
+
::::      s := s + M1(i,k)*K1(k,j);
−
    od;
+
:::    od;
−
    J2(i,j):=s;
+
:::    J2(i,j):=s;
−
  od;
+
::  od;
−
  od;
+
:  '''od''';
−
  t:=time-t;
+
:  t:=time-t;
−
  writeln("czas norm=",t:6);
+
:  writeln("czas norm=",t:6);
 
      
 
      
  
−
  for i := 1 to n do
+
:  '''for''' i := 1 '''to''' n '''do'''
−
    writeln;
+
::    writeln;
−
    for j := 1 to n do
+
::    '''for''' j := 1 '''to''' n '''do'''
−
      write(J1(i,j):5:0);
+
:::      write(J1(i,j):5:0);
−
    od;
+
::    '''od''';
−
  od;
+
:  '''od''';
 
    
 
    
 
    
 
    
 
                
 
                
−
end program;�
+
'''end''' program;

Aktualna wersja na dzień 15:50, 13 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;

Źródło „http://lem12.uksw.edu.pl/index.php?title=Algorytm_Winograda&oldid=195”