Algorytm Euklidesa

Poll without page-refresh

Article on other languages:

Algorytm Euklidesa – algorytm znajdowania największego wspólnego dzielnika (NWD) dwóch różnych liczb naturalnych. Nie wymaga rozkładania liczb na czynniki pierwsze. Algorytm wymyślił Eudoksos z Knidos (IV wiek p.n.e.), a Euklides jedynie zawarł go w swoim dziele Elementy.

W algorytmie wykorzystywana jest zależność

$NWD(a, b)=\begin{cases} a & \mbox{ dla }b=0 \\ NWD(b, a\ \bmod\ b) & \mbox{ dla }b\ge1 \end{cases}$

Spis treści

1 Algorytm
2 Przykłady
- 2.1 Obliczanie NWD
- 2.2 Sprawdzenie, czy liczby są względnie pierwsze
3 Dowód poprawności
4 Złożoność czasowa
- 4.1 Dowód
5 Rozszerzony algorytm Euklidesa
6 Zobacz też

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

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

Przykłady

Obliczanie NWD

Obliczenie największego wspólnego dzielnika liczb

Wartości początkowe $a=1071, b=1029\;$

$NWD(1071, 1029)\ =\ NWD(1029, 1071\ \bmod\ 1029\ =\ 42)$

$=NWD(1029, 42)\ =\ NWD(42, 1029\ \bmod\ 42\ =\ 21)$

$=NWD(42, 21)\ =\ NWD(21, 42\ \bmod\ 21\ =\ 0)$

$=NWD(1071,1029)\ =\ 21$

Sprawdzenie, czy liczby są względnie pierwsze

Liczby są względnie pierwsze, gdy ich największym wspólnym dzielnikiem jest 1. Przykład dla 46406 i 36957:

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

Dowód poprawności

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

Aby to wykazać, należy udowodnić, że wspólny podzielnik liczb

a

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

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

Dowód

Lemat: Jeśli $a\ge 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\ge b$ to $a\ \operatorname{div}\ b\ge \ 1$ , oraz ponadto z własności modulo $a\ \bmod\ b \le \ b$ otrzymujemy:

$b\ +\ a\ \bmod\ b\ <\ 2b\ \le\ 2b\cdot (a\ \operatorname{div}\ b)$

Przy pierwszej iteracji mamy $a + b = m + n\;$ , po k-tym przebiegu pętli:

$a\ +\ b\le \left(\tfrac{2}{3}\right)^k\cdot (m\ +\ n)$

Ponieważ $a\ +\ b\ge 1$ , po ostatnim, l-tym przebiegu pętli będzie:

$1\le \left(\tfrac{2}{3}\right)^l\cdot (m\ +\ n)$

$\left(\tfrac{3}{2}\right)^l\le m\ +\ n$

$\log_2\ (m\ +\ n) \ge 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

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

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;

Zobacz też

Zobacz w Wikiźródłach Implementacje algorytmu Euklidesa

Źródło: „http://pl.wikipedia.org/wiki/Algorytm_Euklidesa”

Kategoria: Algorytmy teorioliczbowe

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.