Algorytm Euklidesa
Algorytm Euklidesa to metoda służąca do określenia największego wspólnego dzielnika (NWD) dwóch liczb. Opisany został przez greckiego matematyka Euklidesa w jego pracy „Elementy”, w księgach siódmej oraz dziesiątej.
Pierwsze wzmianki o tym algorytmie znaleziono w dziele Euklidesa „Elementy” około 300 roku przed naszą erą, co czyni go jednym z najstarszych algorytmów numerycznych, które są wciąż stosowane. Pierwotna wersja algorytmu dotyczyła jedynie liczb naturalnych. W XIX wieku pojawiły się odmiany algorytmu dla liczb całkowitych, opracowane przez Gaussa, oraz dla wielomianów z jedną niewiadomą. To doprowadziło do rozwoju nowoczesnych pojęć w algebrze abstrakcyjnej, w tym dziedziny Euklidesa. W późniejszych latach opracowano różne warianty algorytmu dla innych struktur matematycznych, takich jak węzły czy wielomiany z wieloma niewiadomymi.
Algorytm ten ma wiele teoretycznych i praktycznych zastosowań. Może być wykorzystywany do generowania rytmów w muzyce, które są stosowane jako ostinato. Ponadto znajduje zastosowanie w algorytmie RSA. Algorytm Euklidesa może być także użyty do rozwiązywania równań diofantycznych, na przykład w kontekście znajdowania liczb spełniających dany układ kongruencji (znane jako chińskie twierdzenie o resztach) czy do określania liczb odwrotnych w ciele skończonym. Może również służyć do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu, a także w nowoczesnych algorytmach do faktoryzacji liczb całkowitych.
Jeżeli algorytm zostanie zaimplementowany poprzez obliczanie reszt z dzielenia, a nie odejmowanie, jest on wydajny dla dużych liczb: nie wymaga więcej dzielenia niż liczba cyfr (w systemie dziesiętnym) mniejszej liczby pomnożona przez 5. Udowodnił to Gabriel Lamé w 1844 roku, co uznawane jest za pierwszy przypadek analizy złożoności obliczeniowej algorytmu. W XX wieku opracowano różne metody zwiększające wydajność algorytmu.
Największym wspólnym dzielnikiem dwóch liczb jest największa liczba, która dzieli obie te liczby bez reszty. Algorytm Euklidesa bazuje na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeśli od większej liczby odejmujemy mniejszą. Załóżmy, że dla liczb całkowitych k, m oraz n, k jest wspólnym czynnikiem liczb A oraz B; przyjmujemy również, że:
A = (n * k),
B = (m * k)
oraz
A > B.
Możemy więc przeprowadzić operację:
A – B = (n – m) * k,
co oznacza, że k jest także wspólnym czynnikiem różnicy tych liczb.
Opis algorytmu
Najprostsza wersja algorytmu rozpoczyna się od wyboru dwóch liczb naturalnych, dla których chcemy znaleźć największy wspólny dzielnik. Następnie tworzymy nową parę liczb: pierwsza to liczba mniejsza, a druga to różnica większej i mniejszej. Proces ten powtarzamy, aż obie liczby będą sobie równe – wartość tych liczb to największy wspólny dzielnik wszystkich wcześniejszych par. Wadą tej wersji algorytmu jest duża liczba operacji odejmowania, które są wymagane, gdy różnica między liczbami jest znaczna.
Operację odejmowania można zastąpić obliczaniem 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ę, gdy jedna z liczb osiągnie wartość zero – wtedy druga liczba jest największym wspólnym dzielnikiem.
Przykład – wersja z odejmowaniem
Załóżmy, że chcemy znaleźć największy wspólny dzielnik liczb 1989 oraz 867. Jeśli odejmiemy mniejszą liczbę od większej, wartość największego wspólnego dzielnika nie zmieni się. Ponieważ 1989 – 867 = 1122, nowa para liczb to:
1122, 867
Ponownie odejmujemy mniejszą liczbę od większej: 1122 – 867 = 255, co daje kolejną parę:
255, 867
867 nie jest już mniejszą liczbą. Stosując ten sam sposób, zmniejszamy wartość większej liczby o wartość mniejszej: 867 – 255 = 612, nowa para liczb to:
255, 612
Pierwsza liczba, 255, wciąż jest mniejsza, więc ponownie odejmujemy 255 od liczby większej: 612 – 255 = 357, a kolejną parą liczb jest:
255, 357
357 – 255 = 102, co prowadzi do kolejnej pary:
255, 102
Teraz widzimy, że 255 jest większą liczbą, więc odejmujemy 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ą równe, kolejne odejmowanie da nam zero. Oznacza to, że największym wspólnym dzielnikiem liczb 1989 i 867 jest liczba 51.
Algorytm wykorzystujący funkcję modulo
Algorytm wykorzystujący funkcję modulo to druga, równoważna implementacja algorytmu Euklidesa. Poniżej przedstawiono wersję obliczania NWD liczb a i b wykorzystującą operację reszty z dzielenia (modulo):
- oblicz c jako resztę z dzielenia a przez b
- zastąp a liczbą b, a b liczbą c
- jeśli wartość b wynosi 0, to a jest szukaną wartością NWD, w przeciwnym razie wróć do kroku 1
Pseudokod
funkcja NWD(a, b)
dopóki b ≠ 0
c := a mod b # reszta z dzielenia a przez b
a := b
b := c
zwróć a
Dowód poprawności
Lemat:
NWD(a, b) = NWD(b, a mod b)
Aby to udowodnić, należy wykazać, że wspólny dzielnik liczb a i b jest również dzielnikiem liczby a mod b. Przyjmujemy:
d = NWD(a, b) ⇒ a = s * d, b = t * d
r = a mod b ⇒ a = p * b + r
gdzie s, t, p są liczbami całkowitymi.
Wtedy:
r = a – p * b = s * d – p * t * d = d * (s – p * t)
Oznacza to, że d jest również dzielnikiem r. Z lematu wynika przez indukcję, że jeśli algorytm się zakończy, to da poprawny wynik. Należy również udowodnić, że algorytm się zakończy. W tym celu zauważamy, że 0 ≤ a mod b ≤ b – 1, więc w każdym kroku algorytmu wartość b zmniejsza się przynajmniej o 1. Algorytm musi więc się zakończyć.
Złożoność czasowa
Dla dowolnych liczb m > n ≥ 0 algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej 2 ⋅ log₂(m + n) przebiegach pętli.
Dowód:
Lemat: Jeśli a ≥ b, to:
b + 3 ⋅ (a mod b) < 2a
Podstawiając a = b ⋅ (a div b) + a mod b, otrzymujemy:
b + a mod b < 2b ⋅ (a div b)
I ponieważ a ≥ b, to a div b ≥ 1, oraz z własności modulo a mod b ≤ b, otrzymujemy:
b + a mod b < 2b ≤ 2b ⋅ (a div b)
W pierwszej iteracji mamy a + b = m + n, po k-tym przebiegu pętli: a + b ≤ (2/3)ᵏ ⋅ (m + n).
Ponieważ a + b ≥ 1, po ostatnim, l-tym przebiegu pętli będzie: 1 ≤ (2/3)ˡ ⋅ (m + n).
Wynika z tego, że NWD(a, b) = x ⋅ a0 + y ⋅ b0.
Rozszerzony algorytm Euklidesa
Jeśli będziemy przechowywać informacje o kolejnych ilorazach, to będziemy mogli wyznaczyć liczby całkowite w równaniu:
a ⋅ p + b ⋅ q = NWD(a, b).
Ta metoda nazywa się rozszerzonym algorytmem Euklidesa.
Dla przykładów liczb 174 i 18 w algorytmie Euklidesa otrzymujemy wyniki pośrednie:
174 / 18 = 9 oraz reszta 12.
lub przepisując wszystkie równości w taki sposób, aby w pierwszej z nich po prawej stronie występowała tylko suma pewnych wielokrotności liczb 174 i 18:
12 = 1 ⋅ 174 + (-9) ⋅ 18.
W kolejnych równościach po prawej stronie zawsze występuje kombinacja liniowa liczb 174 oraz 18 lub liczb, które pojawiły się wcześniej.
Kluczowe dla rozszerzonego algorytmu Euklidesa jest stopniowe zastępowanie tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania równości:
NWD(a, b) = kombinacja liniowa liczb a, b.
Na przykład:
6 = 1 ⋅ 18 + (-1) ⋅ 12 = 1 ⋅ 18 + (-1) ⋅ (1 ⋅ 174 + (-9) ⋅ 18) = (-1) ⋅ 174 + 10 ⋅ 18.
Pseudokod
funkcja NWD(a, b)
x := 1
y := 0
r := 0
s := 1
dopóki b ≠ 0
c := a mod b # reszta z dzielenia a przez b
q := a // b # część całkowita z dzielenia a przez b
a := b
b := c
r’ := r
s’ := s
r := x – q ⋅ r
s := y – q ⋅ s
x := r’
y := s’
zwróć a, x, y
Niezmiennikami pętli są wielkości x ⋅ a0 + y ⋅ b0 = a oraz r ⋅ a0 + s ⋅ b0 = b, dzięki czemu NWD(a0, b0) = x ⋅ a0 + y ⋅ b0.
Zobacz też
- implementacje algorytmu Euklidesa
- największy wspólny dzielnik
- rozkład na czynniki
Przypisy
Linki zewnętrzne
Eric W.E.W. Weisstein, Euclidean Algorithm, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
Euclidean algorithm (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].
