Algorytm Euklidesa
Z Wikipedii
Algorytm Euklidesa (metoda kolejnych dzieleń) to algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch różnych liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze. Faktycznie algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go w swoim dziele Elementy.
Wykorzystywana jest w nim zależność
Spis treści |
[edytuj] Algorytm
Przebieg algorytmu Euklidesa obliczania NWD liczb a i b:
- oblicz c jako resztę z dzielenia a przez b
- Zastąp pozycję a liczbą b, a pozycję b liczbą c
- jeżeli pozycja b = 0, to szukane NWD = a, w przeciwnym wypadku przejdź do 1
Przykład: NWD(42,18)
- Krok 1: (a=42, b=18)
- 42/18= 2 r 6, uzyskuję c=6
- ustawiam a=18, b=6
- b jest różne od zera, powtarzam
- Krok 2:
- 18/6= 3 r 0, uzyskuję c=0
- ustawiam a=6, b=0
- b=0, wynikiem jest a, czyli NWD=6
[edytuj] Zapis w pseudokodzie
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
[edytuj] Przykłady
[edytuj] Obliczanie NWD
Obliczenie największego wspólnego dzielnika liczb
a | b | Wywołanie | ||
---|---|---|---|---|
NWD | 1071 | 1029 | Wartości początkowe | |
= | NWD | 1029 | 42 | |
= | NWD | 42 | 21 | |
= | NWD | 21 | 0 | |
21 |
[edytuj] Sprawdzenie, czy liczby są względnie pierwsze
Liczby 46406 i 36957 są względnie pierwsze, co można pokazać następująco:
a | b |
|
|
46406 | 36957 |
36957 | 9449 |
9449 | 8610 |
8610 | 839 |
839 | 220 |
220 | 179 |
179 | 41 |
41 | 15 |
15 | 11 |
11 | 4 |
4 | 3 |
3 | 1 |
1 | 0 |
[edytuj] Rozszerzony algorytm Euklidesa
Jeśli przechowywana będzie informacja o kolejnych ilorazach, to będzie też można wyznaczyć liczby całkowite w równaniu a*p + b*q = NWD (a, b). Ta metoda nazywana jest rozszerzonym algorytmem Euklidesa.
Dla przykładu, obliczenia dla algorytmu Euklidesa dla liczb 174 i 18 będą wyglądać
174 / 18 = 9 r 12
18 / 12 = 1 r 6
12 / 6 = 2 r 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 * 174 + (-9) * 18
6 = 1 * 18 + (-1) * 12
0 = 1 * 12 + (-2) * 6
Zauważmy, że w 1. równaniu po prawej stronie mamy kombinację liniową liczb 174 i 18, podobnie jak w równaniu a*p + b*q = 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.
Kluczowe 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
NWD(a,b) = [kombinacja liniowa liczb a,b], np.
6 = 1 * 18 + (-1)*12 = 1*18 + (-1) * (1* 174 + (-9) * 18) = (-1) * 174 + 10 * 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 = <math>\lfloor a/b \rfloor</math> 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
Rekurencyjna wersja rozszerzonego algorytmu w języku SML
fun nwd2 a0 b0 = let fun nwd2' a b p q r s = if b = 0 then (a, p, q) else nwd2' b (a mod b) r s (p - (a div b) * r) (q - (a div b) *s) in nwd2' a0 b0 1 0 0 1 end; (* nwd2 zwraca trójkę taką, że a*p + b*q = nwd *) val a = 108; val b = 14; val (nwd, p, q) = nwd2 a b;
[edytuj] Dowód poprawności
Lemat:
- Aby to wykazać, należy udowodnić, iż wspólny podzielnik liczb a i b jest również podzielnikiem liczby
- Przyjmijmy:
- gdzie są liczbami całkowitymi.
- Wtedy:
- zatem jest również podzielnikiem
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 , więc w każdym kroku algorytmu wartość zmniejsza się przynajmniej o 1. Ponieważ nie może nigdy być ujemna, więc algorytm musi się zakończyć.
[edytuj] Złożoność czasowa
Dla dowolnych liczb algorytm Euklidesa zwraca wartość NWD(m, n) po co najwyżej przebiegach pętli.
Dowód:
- Lemat: Jeśli to
-
- (1)
(1) jest równoważne
Podstawiając
otrzymuje się:
I ponieważ to , oraz ponadto z własności modulo jest mamy nierówność:
której prawdziwość jest oczywista.
- Przy pierwszej iteracji jest a + b = m + n, po k-tym przebiegu pętli:
Ponieważ , po ostatnim, l-tym przebiegu pętli będzie:
[edytuj] Ciekawostki
- Największej liczby kroków algorytmu wymagają dwa kolejne elementy ciągu Fibonacciego.