% euclide.m
% Algoritmo di euclide per il calcolo del massimo comun divisore.
% Prende n, m interi e ritorna [g,s,t] dove g e' il MCD e s,t sono
% tali che s*n+t*m=g.
% ------------------------------------------------------------

function g=euclide2(n,m)

% Invariante: MCD(n,m) e' costante alla fine di ogni ciclo.
% Invariante: s*m0+t*n0=n alla fine di ogni ciclo
% Invariante: a*m0+b*n0=m alla fine di ogni ciclo
%   (n0, m0 sono i valori iniziali di n m).
% Criterio di arresto: se m=0 allora n e' il massimo comun divisore.

% Cambia segno ad n e m se sono negativi e inizializza a,b,s,t.
s=sign(n); t=0; n=abs(n);
a=0; b=sign(m); m=abs(m);
while m~=0
    r=mod(n,m);
    q=floor(n/m);
    % Calcola i nuovi n,m,a,b,s,t.
    % Usa s1, t1 come variabili temporanee per i nuovi valori di s e t.
    n=m; s1=a; t1=b;
    m=r; a=s-q*a; b=t-q*b;
    s=s1; t=t1;
end
g=[n,s,t]