Page 39 - MATINF Nr. 11-12

Algoritmul extins al lui Euclid 39

a
a
Din (1) si (2) rezult˘ c˘ mult , imea divizorilor comuni ai numerelor a s , i b coincide cu mult , imea
a
a
divizorilor comuni ai numerelor b s , i r s , i prin urmare rezult˘ c˘ cmmdc(a, b) = cmmdc(b, r).
Repetˆand procesul de ˆınlocuire a num˘arului mai mare (a) cu num˘arul mai mic (b) s , i a
num˘arului mai mic (b) cu (r) restul ˆımp˘art , irii dintre a s , i b, vom obt , ine numere naturale din ce
ˆın ce mai mici s , i dup˘a un num˘ar finit de pas , i vom obt , ine r = 0, de unde se deduce c˘a b este
divizor al lui a. Cum c.m.m.d.c. al valorilor init , iale ale numerelor a si b coincide cu c.m.m.d.c.
a
al valorilor finale rezultate, dup˘ aplicarea procesului de reducere rezult˘ c˘ b va furniza cel mai
a
a
mare divizor comun c˘autat.
Implementarea acestui algoritm este urm˘atoarea:
int cmmdc(int a,int b )
{
int r;
while(b!=0)
{ r=a%b; a=b; b=r; }
return a;
}

Varianta recursiv˘ este:
a
int cmmdc(int a,int b)
{
if(b==0) return a;
return cmmdc(b,a%b);
}

S˘ ˆıncerc˘am s˘ determin˘am complexitatea algoritmului lui Euclid.
a
a
Presupunem a > b.
Dac˘a lu˘am ˆın calcul faptul c˘a dac˘a b ≤ a/2 ⇒ a%b < b ≤ a/2, iar dac˘a b > a/2 ⇒ a%b =
a
a
a − b < a/2, rezult˘ c˘ la fiecare pas num˘arul mai mare dintre a s , i b se ˆınjum˘at˘t , es , te (cel put , in).
a
Prin urmare complexitatea temporal˘ a algoritmului lui Euclid este O(log (a)).
a
2
Matematicianul Josef Stein a propus ˆın 1967 [2] ca ˆın calculul celui mai mare divizor comun
a dou˘a numere naturale, pozitive a, b s˘ se foloseasc˘a urm˘atoarele propriet˘at , i:
a
cmmdc(a, a) = a;
cmmdc(2a, 2b) = 2 · cmmdc(a, b);
a
cmmdc(2a, b) = cmmdc(a, b) dac˘ b este impar s , i similar cmmdc(a, 2b) = cmmdc(a, b) dac˘
a
a este impar;
cmmdc(a, b) = cmmdc(a − b, b) dac˘a a s , i b sunt numere impare s , i a > b s , i similar

cmmdc(a, b) = cmmdc(a, b − a) dac˘a a s , i b sunt numere impare s , i a < b.
Implementarea ˆın limbajul C a acestui algoritm este:

int cmmdcStein(int a,int b)
{
if(a==b) return a;
if(a%2==0&&b%2==0) return 2* cmmdcStein(a/2, b/2);