h1. Algoritmul lui Euclid

(Categoria _Teoria numerelor_, autor(i) _Crestez Leonard_)

(Categoria _Matematica_, Autor _Leonard Crestez_)

O prezentare a variantei extinse a algoritmului lui Euclid, care rezolva ecuatie de forma {$A * X + B * Y = D$}, unde $D$ este cel mai mare divizor comun al lui $A$ si {$B$}. De asemenea este prezentata o aplicatie "interesanta": impartirea modulara.

h2. Euclid simplu

In cuvinte, algoritmul pur si simplu impare deimpartitul la rest pana cand impartitorul este {$0$}, apoi returneaza deimpartitul. Poate fi usor implementat iterativ in C. Probabil ca aceasta forma este si cea mai rapida, si este de preferat cand nu e necesar Euclid extins.

In cuvinte, algoritmul pur si simplu imparte deimpartitul la rest pana cand impartitorul este {$0$}, apoi returneaza deimpartitul. Poate fi usor implementat iterativ in C. Probabil ca aceasta forma este si cea mai rapida, si este de preferat cand nu e necesar Euclid extins.

== code(c) | int euclid(int a, int b)
{

}
==

Pentru a fi inteles mai usor si eventual extins, este mai bine sa il punem sub forma recursiva

Pentru a fi inteles mai usor si eventual extins, este mai bine sa il punem sub forma recursiva:

== code(c) | void euclid(int a, int b, int *d)
{

Sa vedem cum functioneaza algoritmul lui Euclid. Se observa ca daca {$a<b$}, atunci $euclid(b, a % b)$ este de fapt {$euclid(b, a)$}.

Vom demonstra ca {$cmmdc(a, b) = cmmdc(b, a % b)$}. Notam $cmmdc(a, b)$ cu {$d$}. Scriem $a%b$ drept {$a - b * c$}, unde $c$ este parte intreaga din {$a / b$}. Cum $a$ si $b$ sunt divizibile cu {$b$}, atunci orice combinatie liniara a lor este divizibila cu {$d$}, inclusiv {$a - b * c = a %b$}.
Asta insa nu este de ajuns, putem aveam {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.

Vom demonstra ca {$cmmdc(a, b) = cmmdc(b, a % b)$}. Notam $cmmdc(a, b)$ cu {$d$}. Scriem $a%b$ drept {$a - b * c$}, unde $c$ este parte intreaga din {$a / b$}. Cum $a$ si $b$ sunt divizibile cu {$d$}, atunci orice combinatie liniara a lor este divizibila cu {$d$}, inclusiv {$a - b * c = a%b$}.
Asta insa nu este de ajuns, putem avea {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.

Astfel, algoritmul lucreaza reducand problema la numere din ce in ce mai mici, pana cand {$a % b = 0$}. Ca sa finalizam recurenta, daca $a$ este divizibil cu {$b$}, atunci este evident ca {$cmmdc(a, b)$} este {$b$}. In cod este un pic mai "ciudat", prindem acest caz doar dupa inca un apel recurent, cand {$b = 0$}. De fapt cred ca $cmmdc$ este definit pe numere strict pozitive, dar in informatica putem ocoli un pic matematica.

Acest algoritm poate fi extins, in sensul gasirii $x$ si $y$ astfel incat {$a * x + b * y = d$}. In acest articol vom incerca sa deducem modul de calculare al lui $x$ si {$y$}. Cei grabiti sau certati cu matematica pot sari direct la codul sursa, dar vor avea probleme in a tine minte algoritmul pe viitor.

Vom extinde procedura recursiva de calculare a $cmmdc$ pentru e include si $x$ si {$y$}. Calculam $x$ si $y$ incepand de la "capatul recurentei". Daca {$b = 0$}, atunci $a * 1 + b * 0 = a(cmmdc)$ evident, asa ca initial $x = 1$ si {$y = 0$}. Incercam sa calculam {$x$}, $y$ in functie de {$x0$}, $y0$ obtinuti pentru {$b$}, {$a % b$}. Noi stim urmatoarele:

Vom extinde procedura recursiva de calculare a $cmmdc$ pentru a include si $x$ si {$y$}. Calculam $x$ si $y$ incepand de la "capatul recurentei". Daca {$b = 0$}, atunci $a * 1 + b * 0 = a(cmmdc)$ evident, asa ca initial $x = 1$ si {$y = 0$}. Incercam sa calculam {$x$}, $y$ in functie de {$x0$}, $y0$ obtinuti pentru {$b$}, {$a % b$}. Noi stim urmatoarele:

* $b * x0 + (a % b) * y0 = d$
* $a * x + b * y = d$

h2. Impartire modulara

Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar {$n$}. Spre exemplu, in {@modulo 7@}, {$3 = 10$}. Similar, rezultatele tuturor operatiilor se iau in modul: {$4 + 5 = 2$}, {$3 * 5 = 1$}, etc.

Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar {$n$}. Spre exemplu, in {@modulo 7@},avem {$3 = 10$}. Similar, rezultatele tuturor operatiilor se iau in modul: {$4 + 5 = 2$}, {$3 * 5 = 1$} etc.

Cum putem defini insa impartirea in modulo? Evident, {$6 / 2$} este tot {$3$}, dar $3 / 4$ cu cat este egal? De obicei impartirea este definita ca operatia inversa a inmultirii, similar cum scaderea este operatia inversa a adunarii. Astfel, daca {$a / b = c$} atunci {$b * c = a$}. Prin algoritmul lui Euclid putem afla $x$ si $y$ astfel incat {$n * x + b * y = cmmdc(n, b)$}, unde $n$ este modulul. Totul e modulo {$n$}, asa ca putem ignora {$x * n$}. Atunci {$c = y * a / cmmdc(n, b)$}. Daca $a$ nu este divizibil cu {$cmmdc(n, b)$}, atunci $c$ nu exista. Intradevar, nu exista $c$ pentru care $3 * c = 4$ modulo {$6$}.

* Sgu 141: "Jumping Joe":http://acm.sgu.ru/problem.php?contest=0&problem=141
* Sgu 248: "Integer Linear Programming":http://acm.sgu.ru/problem.php?contest=0&problem=248

h2.  O sursa interesanta pentru Algoritmul lui Euclid este cea din cartea lui Knuth Arta Programarii Calculatoarelor Vol. 2 Algoritmi Seminumerici care descrie stransa legatura intre algoritm si fractiile continue (Cap. 4.5.3)

O sursa interesanta pentru Algoritmul lui Euclid este cea din cartea lui Knuth Arta Programarii Calculatoarelor Vol. 2 Algoritmi Seminumerici care descrie stransa legatura intre algoritm si fractiile continue (Cap. 4.5.3)

3681