Algorytm Euklidesa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Euklidesa – pierwszy znany algorytm wyznaczania największego wspólnego dzielnika dwóch liczb naturalnych. Został opisany przez greckiego matematyka, Euklidesa w jego dziele "Elementy", w księgach siódmej oraz dziesiątej[1].

Pierwsze wzmianki na temat tego algorytmu pojawiły się w dziele Euklidesa zatytułowanym "Elementy", około trzechsetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych wciąż używanych algorytmów numerycznych. Pierwsza wersja algorytmu został opisana tylko dla liczb naturalnych oraz rzeczywistych. W XIX wieku powstały odmiany algorytmu dla liczb całkowitych Gaussa oraz wielomianów z jedną niewiadomą. Doprowadziło to do powstania współczesnych pojęć algebry abstrakcyjnej, takich jak dziedzina Euklidesa. W późniejszych czasach opracowano odmiany algorytmu dla innych struktur matematycznych, jak węzły czy wielomiany z wieloma niewiadomymi.

Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Na przykład może zostać wykorzystany do generowania rytmów muzycznych, które stosowanych jako ostinato w muzyce[2]. Jest także wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenie o resztach) czy znajdowanie liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych.

Jeżeli algorytm zostanie zaimplementowany poprzez obliczanie reszt z dzielenia, a nie odejmowanie, to jest wydajny dla dużych liczb: nigdy nie wymaga więcej dzieleń niż liczba cyfr (w systemie dziesiętnym) mniejszej liczby pomnożona przez 5. Zostało to udowodnione przez Gabriela Lamé w 1844 i uważane jest za pierwszy przypadek analizy złożoności obliczeniowej algorytmu. Sposoby zwiększenia wydajności algorytmów zostały opracowane w XX wieku.

Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Algorytm Euklidesa opiera się na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy mniejszą. Dla liczb całkowitych k, m oraz n załóżmy, że k jest wspólnym czynnikiem liczb A oraz B; załóżmy też, że A = (n*k), B = (m*k) oraz A > B. Możemy teraz dokonać działaniaA-B=(n-m)*k , wiemy więc, że k jest także wspólnym czynnikiem różnicy tych liczb.

Opis algorytmu[edytuj | edytuj kod]

Najprostsza wersja algorytmu rozpoczyna się od wybrania dwóch liczb naturalnych, dla których należy wyznaczyć największy wspólny dzielnik. Następnie z tych dwóch liczb tworzymy nową parę: pierwszą z liczb jest liczba mniejsza, natomiast drugą jest różnica liczby większej i mniejszej. Proces ten jest powtarzany aż obie liczby będą sobie równe - wartość tych liczb to największy wspólny dzielnik wszystkich par liczb wcześniej wyznaczonych. Wadą tej wersji algorytmu jest duża liczba operacji odejmowania, które należy wykonać w przypadku, gdy różnica pomiędzy liczbami z pary jest znacząca.

Operacja odejmowania mniejszej liczby od większej może zostać zastąpiona przez wyznaczanie reszty z dzielenia. W tej wersji nowa para liczb składa się z mniejszej liczby oraz reszty z dzielenia większej przez mniejszą. Algorytm kończy się w momencie, w którym jedna z liczb jest równa zero - druga jest wtedy największym wspólnym dzielnikiem.

Przykład - wersja z odejmowaniem[edytuj | edytuj kod]

Załóżmy, że chcemy znaleźć największy wspólny dzielnik liczb 1989 oraz 867. Jeżeli od większej liczby odejmiemy liczbę mniejszą, wartość największego wspólnego dzielnika nie ulegnie zmianie. Ponieważ 1989 - 867 = 1122, nowa para liczb wygląda następująco:

1122, 867

Ponownie odejmujemy mniejszą liczbę od większej 1122 - 867 = 255, tworząc w ten sposób kolejną parę:

255, 867

867 nie jest już mniejszą liczbą. Stosując ten sam sposób, ponownie zmiejszamy wartość większej liczby o wartość mniejszej: 867 - 255 = 612, nowa para liczb to:

255, 612

Pierwsza liczba, 255, jest wciąż mniejsza, ponownie więc odejmujemy 255 od liczby większej: 612 - 255 = 357, więc kolejna para liczb to:

255, 357

357 - 255 = 102, kolejna para to:

255 , 102

Teraz widać, że 255 jest większą liczbą, odejmujemy więc od niej 102, co daje nam parę:

153 , 102

Odjęcie 102 od 153 tworzy nam kolejną parę:

51 , 102.

Teraz odejmujemy 51 od 102, co daje nam:

51, 51

Ponieważ obie liczby są sobie równe, kolejne odejmowanie da nam zero. Oznacza to, że największym wspólnym dzielnikiem liczb 1989 i 867 jest liczba 51.

Algorytm[edytuj | edytuj kod]

Istnieją dwie równoważne implementacje algorytmu Euklidesa. Poniżej przedstawiono wersję obliczania NWD liczb a i b wykorzystującą operację reszty z dzielenia (modulo):

  1. oblicz c jako resztę z dzielenia a przez b
  2. zastąp pozycję a liczbą b, a pozycję b liczbą c
  3. jeżeli pozycja b = 0, to szukane NWD = a, w przeciwnym wypadku przejdź do 1

Pseudokod[edytuj | edytuj kod]

NWD(liczba całkowita a, liczba całkowita b)
        dopóki b != 0
                c := reszta z dzielenia a przez b
                a := b
                b := c
        zwróć a 

Funkcja wyliczająca NWD w C/C++[edytuj | edytuj kod]

// Funkcja NWD przyjmująca 2 argumenty: a i b typu int - czyli liczby, których NWD chcemy poznać. Funkcja zwraca wartość typu int - czyli żądane NWD(a,b)
int nwd(int a,int b)
{
    int c;                    // Tworzymy zmienną c o typie int
    while(b != 0)             // Tworzymy pętlę działającą gdy b ≠ 0
    {
        c=a % b;              // Zmienna c przyjmuje wartość a modulo b
        a = b;                // Przypisujemy b do a
        b = c;                // Przypisujemy c do b
    }
    return a;                 // Zwracamy a, czyli żądane NWD(a,b)
}

Funkcja wyliczająca NWD w JavaScript[edytuj | edytuj kod]

function Euklides(a,b) {
    if(a==b) { document.body.innerHTML = a; }
    while(a!=b) {  
        while(a>b) {
            a = a-b;
        }
        while(b>a) {
            b=b-a;
        }
    }
    document.body.innerHTML = a;
}
Euklides(36,48);

Dowód poprawności[edytuj | edytuj kod]

Lemat: NWD (a, b) = NWD (b, a\ mod\ b)

Aby to wykazać, należy udowodnić, że wspólny podzielnik liczb a i b jest również podzielnikiem liczby a\ mod\ b
Przyjmijmy:
d = NWD (a, b) \Rightarrow a=sd,\ b=td
r = a\ mod\ b \Rightarrow a=pb+r
gdzie s, t,p\; są liczbami całkowitymi.
Wtedy:
r=a-pb=sd-ptd=d(s-pt)\;
zatem d\; jest również podzielnikiem r\;

Z lematu wynika przez indukcję, że jeśli algorytm się zakończy, to da poprawny wynik. Pozostaje udowodnić, że się zakończy. Wystarczy w tym celu zauważyć, że 0\leqslant a\ mod\ b\leqslant b-1, więc w każdym kroku algorytmu wartość b\; zmniejsza się przynajmniej o 1. Ponieważ nie może nigdy być ujemna, algorytm musi się zakończyć.

Złożoność czasowa[edytuj | edytuj kod]

Dla dowolnych liczb m>n\geqslant 0 algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej 2\cdot \log_2\ (m+n) przebiegach pętli.

Dowód[edytuj | edytuj kod]

  • Lemat: Jeśli a\geqslant b to
b + a \bmod b < \tfrac{2}{3}\cdot (a+b)
(1)
(1) jest równoważne b +3 \cdot (a \bmod b)<2a
Podstawiając
a=b\cdot (a \operatorname{div} b) + a \bmod b
otrzymuje się:
b + a \bmod b < 2b\cdot (a \operatorname{div} b)
i ponieważ a\geqslant b to a \operatorname{div} b \geqslant 1, oraz ponadto z własności modulo a \bmod\ b \leqslant b otrzymujemy:
b + a \bmod b < 2b \leqslant 2b\cdot (a \operatorname{div} b)
  • Przy pierwszej iteracji mamy a + b = m + n\;, po k-tym przebiegu pętli:
a + b\leqslant \left(\tfrac{2}{3}\right)^k\cdot (m + n)
  • Ponieważ a + b\geqslant 1, po ostatnim, l-tym przebiegu pętli będzie:
1\leqslant \left(\tfrac{2}{3}\right)^l\cdot (m + n)
\left(\tfrac{3}{2}\right)^l\leqslant m + n
\log_2\ (m\ +\ n) \geqslant l\cdot \log_2\ \tfrac{3}{2} > \tfrac{1}{2}\cdot l
l\ <\ 2\cdot \log_2\ (m\ +\ n)

Największej liczby kroków algorytmu wymagają dwa kolejne elementy ciągu Fibonacciego.

Rozszerzony algorytm Euklidesa[edytuj | edytuj kod]

Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też można wyznaczyć liczby całkowite w równaniu a\cdot p + b\cdot q =\operatorname{NWD} (a, b). Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa.

Na przykład dla liczb 174 i 18 w algorytmie Euklidesa uzyskuje się wyniki pośrednie:

174 / 18 = 9\mbox{ i reszta }12\;
18 / 12 = 1\mbox{ i reszta }6\;
12 / 6 = 2\mbox{ i reszta }0\;

lub przepisując wszystkie równania w taki sposób, by w pierwszym równaniu po prawej stronie występowała tylko suma pewnych wielokrotności liczb 174 i 18:

12 = 1 \cdot 174 + (-9) \cdot 18\;
6 = 1 \cdot 18 + (-1) \cdot 12\;
0 = 1 \cdot 12 + (-2) \cdot 6\;

Zauważmy, że w pierwszym równaniu po prawej stronie występuje kombinacja liniowa liczb 174 i 18, podobnie jak w równaniu a\cdot p + b\cdot q =\operatorname{NWD} (a, b). W następnych równaniach po prawej stronie mamy zawsze kombinację liniową liczb 174, 18 lub liczb, które wystąpiły po lewej stronie we wcześniejszych równaniach.

Kluczowa dla rozszerzonego algorytmu Euklidesa staje się możliwość stopniowego zastępowania tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania równości:

\operatorname{NWD}(a, b) = \mbox{kombinacja liniowa liczb a, b}\;

np.

6 = 1 \cdot 18 + (-1)\cdot 12 = 1\cdot 18 + (-1) \cdot (1\cdot 174 + (-9) \cdot 18) = (-1) \cdot 174 + 10 \cdot 18

Zapis algorytmu w pseudokodzie:

// Zakładamy, że a > 0 i b > 0.
a0 = a
b0 = b
 
// Inicjalizacja. Utrzymujemy niezmienniki p*a0 + q*b0 = a oraz r*a0 + s*b0 = b
p = 1; q = 0;
r = 0; s = 1;
 
// algorytm
while (b != 0)
  c = a mod b
  quot = floor( a/b )
  a = b
  b = c
  new_r = p - quot * r
  new_s = q - quot * s
  p = r; q = s
  r = new_r
  s = new_s
 
// Wówczas NWD(a0, b0) = p*a0 + q*b0

Przypisy

  1. Thomas L. Heath: The Thirteen Books of Euclid's Elements 2nd edition. (ang.)
  2. Godfried Toussaint: The Euclidean Algorithm Generates Traditional Musical Rhythms (ang.). [dostęp 2012-08-10].

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]