Eukleidův algoritmus
![Animace Eukleidova algoritmu](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Euclidean_algorithm_1071_462.gif/220px-Euclidean_algorithm_1071_462.gif)
Eukleidův algoritmus (též Euklidův) je algoritmus, kterým lze určit největší společný dělitel dvou přirozených čísel, tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je rozšířený Eukleidův algoritmus, kterým lze nalézt Bézoutovu rovnost, neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací.
Algoritmus lze také použít i v jiných algebraických strukturách, než jsou přirozená čísla. Takové struktury se nazývají Eukleidovské obory a jedná se například o některé okruhy mnohočlenů nebo o Eisensteinova čísla.
Algoritmus
[editovat | editovat zdroj]Mějme dána dvě přirozená čísla, uložená v proměnných u a w. Dokud w není nulové, opakuj: Do r ulož zbytek po dělení čísla u číslem w Do u ulož w Do w ulož r Konec algoritmu, v u je uložen největší společný dělitel původních čísel.
Popis činnosti
[editovat | editovat zdroj]Opakovaně prováděné operace nemění hodnotu největšího společného dělitele
(neboť NSD(u, v) = NSD(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ť NSD(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í.
Vlastnosti algoritmu
[editovat | editovat zdroj]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 . Průměrný počet kroků pak je o něco nižší, přibližně .
Ukázka činnosti algoritmu
[editovat | editovat zdroj]Mějme čísla u = 40902, w = 24140. Výpočet probíhá následujícím způsobem:
u | w | u=w×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.
Historie
[editovat | editovat zdroj]Eukleidův algoritmus je pojmenován podle starověkého filozofa Eukleida, který jej uvedl ve svém díle Základy (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.
Poznámky
[editovat | editovat zdroj]- Na základě tohoto algoritmu lze rychle spočítat inverzní prvek k násobení v modulární aritmetice. Největší společný dělitel dvou čísel se dá vyjádřit Bézoutovou rovností jako součet násobků těchto čísel. Pokud je tímto největším společným dělitelem 1, pak dostaneme součin prvku a jeho inverzního. Tedy pokud máme spočítat inverzní prvek x modulo n a vyjde nám vyjádření největšího společného dělitele Bézoutovou rovností ax + bn = 1, kde známe všechny proměnné. Máme tak vlastně přímo rovnost ax=1 modulo n a nalezené a je hledaný inverzní prvek. Tento výpočet inverzního prvku je častý v aplikacích teorie čísel, zejména v kryptografii.
- Tento algoritmus lze použít nejen pro čísla, ale také pro polynomy. Polynom je s jeho využitím možno rozdělit na součin polynomů oddělených dle násobnosti kořenů. Derivace snižuje násobnost každého kořene o 1 a zavádí nové kořeny. Největší společný dělitel s původním polynomem odstraňuje nové kořeny. 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.
Odkazy
[editovat | editovat zdroj]Externí odkazy
[editovat | editovat zdroj]Obrázky, zvuky či videa k tématu Eukleidův algoritmus na Wikimedia Commons
- Eukleidův algoritmus – na mathworldu (anglicky)
- Eukleidův algoritmus – počítaný online (anglicky)