Euklidův algoritmus

Z Wikipedie, otevřené encyklopedie

Euklidův algoritmus je postup (algoritmus), kterým lze určit největšího společného dělitele dvou přirozených čísel, tzn. nejvyšší číslo takové, že beze zbytku dělí obě čísla.

Obsah

1 Algoritmus
2 Popis činnosti
3 Vlastnosti algoritmu
4 Ukázka činnosti algoritmu
5 Historie
6 Poznámky
7 Externí odkazy

[editovat] Algoritmus

Mějme dána dvě přirozená čísla, uložená v proměnných u a v.
Dokud v není nulové, opakuj:
  Do r ulož zbytek po dělení čísla u číslem v
  Do u ulož v
  Do v ulož r
Konec algoritmu, v u je uložen největší společný dělitel původních čísel.

[editovat] Popis činnosti

Opakovaně prováděné operace nemění hodnotu největšího společného dělitele (neboť gcd(u,v)=gcd(v,u-qv) pro libovolné celé číslo q), ale v každém kroku se hodnota proměnné v sníží, takže je zřejmé, že v konečném počtu kroků se algoritmus ukončí s tím, že v je nulové. Tehdy obsahuje proměnná u největší společný dělitel, neboť gcd(u,0)=u, což musí být současně největší společný dělitel původních čísel, neboť, jak už bylo uvedeno, hlavní smyčka programu hodnotu největšího společného dělitele nemění.

[editovat] Vlastnosti algoritmu

Doba provádění programu je závislá na počtu průchodů hlavní smyčkou. Ten je maximální tehdy, jsou-li počáteční hodnoty u a v rovné dvěma po sobě jdoucím členům Fibonacciho posloupnosti. Maximální počet provedených opakování je tedy $\log_\phi (3-\phi)v \approx 4{,}785 \log v + 0{,}6273 = O(\log v)$ . Průměrný počet kroků pak je o něco nižší, přibližně $\frac{12 \ln 2}{\pi^2}\log v \approx 1{,}9405 \log v = O(\log v)$ .

[editovat] Ukázka činnosti algoritmu

Mějme čísla u=40902, v=24140. Výpočet probíhá následujícím způsobem:

u	v	u=v×q+r
40902	24140	40902=24140×1+16762
24140	16762	24140=16762×1+7378
16762	7378	16762=7378×2+2006
7378	2006	7378=2006×3+1360
2006	1360	2006=1360×1+646
1360	646	1360=646×2+68
646	68	646=68×9+34
68	34	68=34×2+0
34	0	konec algoritmu

Největším společným dělitelem čísel 40902 a 24140 je číslo 34.

[editovat] Historie

Euklidův algoritmus je pojmenován podle starověkého filozofa Euklida, který jej uvedl ve svém díle Elementy (cca 300 př.n.l.), přestože tento postup zřejmě sám nevynalezl. Jedná se pravděpodobně o nejstarší lidstvu známý netriviální algoritmus, takže po jistou dobu se slovem algoritmus prakticky rozuměl Euklidův algoritmus.

[editovat] Poznámky

Na základě tohoto algoritmu lze rychle spočítat inverzní prvek v cyklické grupě. Největší společný dělitel dvou čísel se dá vyjádřit jako součet násobků těchto čísel. Toto snadno dostaneme jakoby zpětným průchodem tímto algoritmem. Pokud je tím NSD 1, pak dostaneme součin prvku a jeho inverzního v modulární aritmetice. Výpočet inverzního prvku se využívá v kryptografii.
Tento algoritmus lze použít nejen pro čísla, ale také pro polynomy. Za pomocí derivace lze tak najít polynom obsahující stejné kořeny jako původní, ale každý kořen je zde jednoduchý. Například lze tak zjistit kořeny polynomu (x-a)(x-a)(x-a)(x-b)(x-b), přestože neexistuje algoritmus na výpočet kořenů polynomu stupně většího než 4.
Tento algoritmus je jeden z těch, u nichž není znám způsob paralelního zpracování, který by podstatně zvýšil výpočetní rychlost.

[editovat] Externí odkazy

Eukleidův algoritmus – na mathworldu (anglicky)
Eukleidův algoritmus – počítaný online (anglicky)

Citováno z „http://cs.wikipedia.org../../../e/u/k/Euklid%C5%AFv_algoritmus.html“

Kategorie: Algoritmy | Teorie čísel