Algorytm Euklidesa - Google

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ść

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

Spis treści

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

[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
	$N W D$	$1071$	$1029$	Wartości początkowe
=	$N W D$	$1029$	$42$	$NWD(1071, 1029)\ =\ NWD(1029, 1071\ \bmod\ 1029\ =\ 42)$
=	$N W D$	$42$	$21$	$NWD(1029, 42)\ =\ NWD(42, 1029\ \bmod\ 42\ =\ 21)$
=	$N W D$	$21$	$0$	$NWD(42, 21)\ =\ NWD(21, 42\ \bmod\ 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: $NWD (a,b) = NWD (b, a\ mod\ b)$

Aby to wykazać, należy udowodnić, iż 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, więc algorytm musi się zakończyć.

[edytuj] 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

(1) $b\ +\ a\ \bmod\ b\ <\ \tfrac{2}{3}\cdot (a+b)$

(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 jest $a\ \bmod\ b \le \ b$ mamy nierówność:

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

której prawdziwość jest oczywista.

Przy pierwszej iteracji jest 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)$

[edytuj] Ciekawostki

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

[edytuj] Zobacz też

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

przegląd zagadnień z zakresu matematyki

Pogłoski o upadłości banku wywołały panikę

Rozpowszechniane w internecie pogłoski o rychłej upadłości jednego z największych bułgarskich banków komercyjnych FIB (First Investment Bank) spowodowały panikę wśród jego klientów, którzy ustawili się w długich kolejkach, by wycofać pieniądze.

Obniżyli cenę za przejazd A1 i nieźle na tym wyszli

Od kiedy minister infrastruktury zmniejszył opłaty za przejazd 25-kilometrowym odcinkiem A1, kierowcy dużo chętniej z niej korzystają. Ruch jest tylko nieznacznie mniejszy niż wtedy, gdy przejazd był bezpłatny - czytamy w trójmiejskim dodatku do "Gazety Wyborczej".

Fiskus ostrzega przed oszustami

Przed próbą wyłudzenia poufnych danych przez telefon ostrzegają szczecińskie urzędy skarbowe. Do urzędów zgłaszają się podatnicy, którzy otrzymali telefoniczne wezwanie, a nawet groźby surowej kary za rzekome niezłożenie zeznania.

Cena benzyny wkrótce znacznie powyżej 5 zł za litr?

Baryłka ropy naftowej według banków Goldman Sachs i UBS może kosztować niedługo 150 dolarów, a litr benzyny w Polsce ponad 5 zł - donosi "Rzeczpospolita" w sobotnim wydaniu.

Czy Wrocław wygra wyścig o prestiżowy instytut?

Wrocław ma poważne szanse na siedzibę Europejskiego Instytutu Innowacji i Technologii (EIT), a polski rząd powinien lobbować na jego rzecz - uważa ekspert Uniwersytetu Warszawskiego Jarosław Pietras.

Linki: Strona g��wna

Encyklopedia