Eukleidův algoritmus

Animace Eukleidova algoritmu
Animace Eukleidova algoritmu: Obdélník má délky stran 1071 a 462. Když se od delší strany (1071) dvakrát odečte 462, zbude 147. Když se od kratší strany původního obdélníku (462) třikrát odečte 147, zbude 21. Když se od 147 sedmkrát odečte 21, tak nezbude nic a to znamená, že 21 je největší společný dělitel čísel 1071 a 462.

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

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

Opakovaně prováděné operace nemění hodnotu největšího společného dělitele

(neboť NSD(u, v) = NSD(v, uqv) 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

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

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

uwu=w×q + r
409022414040902 = 24140×1 + 16762
241401676224140 = 16762×1 + 7378
16762737816762 = 7378×2 + 2006
737820067378 = 2006×3 + 1360
200613602006 = 1360×1 + 646
13606461360 = 646×2 + 68
64668646 = 68×9 + 34
683468 = 34×2 + 0
340konec algoritmu

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

Historie

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

  • 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

Externí odkazy

Média použitá na této stránce

Euclidean algorithm 1071 462.gif
Autor: Proteins, Licence: CC BY-SA 3.0
Animation of the Euclidean algorithm for 1071 and 462. The initial green rectangle has dimensions a = 1071 and b = 462. Square 462x462 tiles are added until a green 462x147 rectangle remains. This is tiled with square 147x147 tiles until a 21x147 rectangle remains. This third rectangle is tiled with 21x21 square tiles, leaving no remainder. Thus, 21 is the greatest common divisor of 1071 and 462.