Eukleidův algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
značka: editace z Vizuálního editoru |
google.com značka: editace z Vizuálního editoru |
||
| Řádek 1: | Řádek 1: | ||
| ⚫ | |||
'''Eukleidův algoritmus''' (též '''Euklidův''') je [[algoritmus]], kterým lze určit [[Největší společný dělitel|největšího společného dělitele]] dvou [[Přirozené číslo|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ézoutova rovnost|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á struktura|algebraických strukturách]], než jsou přirozená čísla. Takové struktury se nazývají [[Eukleidovský obor|Eukleidovské obory]] a jedná se například o některé [[okruh mnohočlenů|okruhy mnohočlenů]] nebo o [[Eisensteinovo číslo|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'',''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 == |
|||
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 posloupnost]]i. Maximální počet provedených opakování je tedy <math>\log_\phi (3-\phi)v \approx 4{,}785 \log v + 0{,}6273 = O(\log v)</math>. Průměrný počet kroků pak je o něco nižší, přibližně <math>\frac{12 \ln 2}{\pi^2}\log v \approx 1{,}9405 \log v = O(\log v)</math>. |
|||
== Ukázka činnosti algoritmu == |
|||
Mějme čísla ''u''=40902, ''v''=24140. Výpočet probíhá následujícím způsobem: |
|||
{| class="wikitable" |
|||
! ''u'' |
|||
! ''v'' |
|||
! ''u''=''v.q''+''r'' |
|||
|- align="right" |
|||
| 40902 |
|||
| 24140 |
|||
| 40902=24140×1+16762 |
|||
|- align="right" |
|||
| 24140 |
|||
| 16762 |
|||
| 24140=16762×1+7378 |
|||
|- align="right" |
|||
| 16762 |
|||
| 7378 |
|||
| 16762=7378×2+2006 |
|||
|- align="right" |
|||
| 7378 |
|||
| 2006 |
|||
| 7378=2006×3+1360 |
|||
|- align="right" |
|||
| 2006 |
|||
| 1360 |
|||
| 2006=1360×1+646 |
|||
|- align="right" |
|||
| 1360 |
|||
| 646 |
|||
| 1360=646×2+68 |
|||
|- align="right" |
|||
| 646 |
|||
| 68 |
|||
| 646=68×9+34 |
|||
|- align="right" |
|||
| 68 |
|||
| 34 |
|||
| 68=34×2+0 |
|||
|- align="right" |
|||
| 34 |
|||
| 0 |
|||
| ''konec algoritmu'' |
|||
|} |
|||
Největším společným dělitelem čísel 40902 a 24140 je číslo 34. |
|||
== Historie == |
|||
| ⚫ | |||
== Poznámky == |
== Poznámky == |
||
Verze z 20. 11. 2013, 15:09
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, takže po jistou dobu se slovem algoritmus prakticky rozuměl Eukleidův 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.
Externí odkazy
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)