Algorytm Euklidesa

Algorytm Euklidesa

Niech NWD(a,b) oznacza największy wspólny dzielnik liczb a i b.

Zauważmy, że

NWD(a, b) = NWD(a - b, b)

i

NWD(a, b) = NWD(a, b - a)

Ćwiczenie. Uzasadnij prawdziwość powyższych równości.

Jednocześnie

NWD(a, 0) = a

dla dowolnego a > 0. (Dlaczego?)

Pozwala to na sformułowanie następującego algorytmu obliczania NWD(a,b):

int NWD(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (a > b) {
        return NWD(a - b, b);
    } else {
        return NWD(a, b - a);
    }
}

Jeżeli ktoś nie lubi (lub nie rozumie) rekurencji, można to samo zrobić iteracyjnie:

int NWD(int a, int b)
{
    while (a > 0 && b > 0) {
      if (a > b) {
          a = a - b;
      } else {
          b = b - a;
      }
    }
    if (a != 0) return a;
    if (b != 0) return b;
}

Ćwiczenie. Wykonaj powyższe algorytmy na kartce dla liczb a = 30 i b = 42.

Powyższy algorytm ma jednak pewną łatwą do usunięcia wadę, widoczną, gdy spróbujemy go uruchomić dla liczb a = 1000000, b = 2.

Ćwiczenie. Jaka jest to wada?

Poradzimy sobie za pomocą następującej obserwacji:

Jeżeli r przystaje do a modulo b, to NWD(a, b) = NWD(r, b)

Ćwiczenie. Uzasadnij prawdziwość powyższej równości.

Dlatego jeżeli a < b, to zamiast b - a możemy użyć dowolnej liczby przystającej do b modulo a - czyli na przykład reszty z dzielenia b przez a:

int NWD(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (a > b) {
        return NWD(a % b, b);
    } else {
        return NWD(a, b % a);
    }
}

Algorytm ten nosi nazwę algorytmu Euklidesa.

Ćwiczenie. Dlaczego powyższy algorytm zawsze kończy działanie?

Ćwiczenie. Zaimplementuj drugą i trzecią wersję algorytmu i porównaj czasy działania obu wersji, obliczając sumę wartości największych wspólnych dzielników wszystkich par liczb od 1 do 10000.