Algoritmul lui Euclid

(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.

Probabil ca multi stiti algoritmul lui Euclid de prin clasa a 5-a, cand invatati la matematica divizibilitate. Varianta simplista a algoritmului lui Euclid este cunoscuta de multa lume, dar fara prea multe explicatii despre functionarea lui.

Euclid simplu

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.

int euclid(int a, int b)
{
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

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

void euclid(int a, int b, int *d)
{
    if (b == 0) {
        *d = a;
    } else
        euclid(b, a % b, 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 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.

Euclid extins

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 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

Trebuie sa aflam o solutie pentru x si y. Vom nota ca mai sus parte intreaga din a / b cu c.

  • b * x0 + (a - b * c) * y0 = a * x + b * y
  • b * (x0 - c * y0 - y) = a * (x - y0)

O solutie este acum evidenta (Una, sunt o infinitate de perechi x, y)

  • x0 - c * y0 - y = 0, De unde rezulta y = x0 - c * y0
  • x - y0 = 0, De unde rezulta x = y0

Acum nu mai pare asa de "magic", nu?

Sursa modificata pentru a calcula si x si y nu este mult mai complexa. Acum intelegeti de ce am trimis d ca pointer mai sus, si de ce am folosit varianta recursiva a algoritmului lui euclid. Implementat iterativ, este nevoie de un vector care sa tina toate valorile c (a / b) obtinute pe parcurs.

Nota pentru pascalisti: in C nu exista div, impartirea intre int-uri este automat si impartire intreaga (div din pascal).

void euclid(int a, int b, int *d, int *x, int *y)
{
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
    } else {
        int x0, y0;
        euclid(b, a % b, d, &x0, &y0);
        *x = y0;
        *y = x0 - (a / b) * y0;
    }
}

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,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.

Tema pentru acasa

Cateva probleme care se rezolva intr-un mod sau altul folosing algoritmul lui Euclid sau algoritmul lui Euclid extins:

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)

remote content