Euklidov algoritmus

Na čo to je?

Euklidov algoritmus je jeden z najstarších algoritmov na svete. Slúži na nájdenie najväčšieho spoločného deliteľa dvoch čísel. V skratke, majme dve kladné čísla $a$ a $b$. Najväčší spoločný deliteľ týchto dvoch čísel je také $x$ pre ktoré platí, že $x$ delí $a$, $x$ delí $b$ a zároveň je to najväčšie $x$ pre ktoré toto platí.

Uvedieme si pár príkladov, pre $a$, $b$ a $x$:

$a=14$, $b=21$, $x=7$

$a = 18$, $b = 7$, $x=1$

Ako to funguje?

Predstavme si dve kladné celé čísla $a$ a $b$. Predpokladajme nachvíľu, že $a>b$. Dôležitým pozorovaním je, že pokiaľ nejaké $x$ delí $a$ aj $b$, tak určite delí aj $a-b$.

Zdôvodnenie je jednoduché, kedže $a = k\cdot x$ a $b = l\cdot x$ tak $a-b = (k-l)\cdot x$ teda $a-b$ je celočíselným násobkom $x$ a teda inak povedané -- deliteľné $x$.

Ak sa zamyslíte je pre nás už jednoduché nájsť spoločného deliteľa dvoch čísel $a$ a $b$. Algoritmus by mohol vyzerať takto:

int najdi(int a, int b)
{
    if(a<b) return najdi(b, a);

    if(b == 0) return a;
    else return najdi(a-b, b);
}

Čo v rekurzívnej funkcii robíme? Pomocou nášho jediného pozorovania počítame najväčší spoločný deliteľ. Ako? Majme dve čísla, najprv sa uistíme, že prvé číslo je väčšie rovné ako druhé. Pokiaľ je menšie z nich $0$, tak vrátime to druhé nakoľko, nulu delí všetko a najväčšie kladné číslo, ktoré delí $a$ je práve $a$. Pokiaľ ale druhé z týchto čísiel nie je 0, vieme použiť naše pozorovanie. Pokiaľ si najväčší spoločný deliteľ $a$ a $b$ označíme $x$, tak toto $x$ je aj najväčší spoločný deliteľ čísel $a-b$ a $b$. Prečo?

To, že delí $b$ je zrejmé a deliteľnosť $a-b$ týmto číslom sme si už skôr dokázali. Zároveň nemôže existovať väčšie číslo $y(y>x)$, ktoré by delilo aj $a-b$ a $b$ lebo by delilo aj $a$ a teda $x$ by nebolo najväčší spoločný deliteľ $a$ a $b$.

Z tohto teda vyplýva, že nám na nájdenie najväčšieho spoločného deliteľa $a$ a $b$ stačí nájsť najväčší spoločný deliteľ čísel $a-b$ a $b$. Toto nám ale zaručí, že čísla, ktorých najväčší spoločný deliteľ postupne hľadáme klesajú a teda sa dopracujeme k tomu, že jedno z nich je 0.

Kam s tým?

Toto bola ilustrácia myšlienky, na ktorej je postavený Euklidov algoritmus. Samotný algoritmus už je iba zrýchlením daného výpočtu. Kde je problém?

Problém je v tom, pokiaľ je $a$, teda väčšie z čísel veľmi veľké a druhé číslo veľmi malé. Čo sa vtedy stane, nech $a=100$ a $b = 8$. Naša funkcia najdi sa bude postupne volať s parametrami $(100, 8)$, $(92, 8)$, $(84, 8)$, $(76, 8)$ ... $(12, 8)$, $(4, 8)$, $(8, 4)$, $(4, 4)$, $(4, 0)$. Vidíme, že výsledkom je $4$. Čo je problém je dlhá postupnosť volaní funkcie, kedy sa nerobilo nič iné ako odčítavanie toho istého jedného čísla od druhého. Ako sa vieme tomuto vyhnúť? Všimnite si, že v momente kedy máme dve čísla $a$ a $b$ tak sa neudeje nič iné ako odčítavanie $b$ od $a$ pokým $a$ neklesne veľkosťou pod $b$. Snáď by sa dalo zistiť, na akom čísle zastaneme. Hľadáme teda číslo, ktoré dostaneme odčítavaním $b$ od $a$ pokým $a$ neklesne prvý krát pod $b$. Uvedomme si, že toto číslo je práve $a%b$ teda zvyšok $a$ po delení $b$. Zvyšok $a$ po delení $b$ je totiž práve tá -- časť -- $a$, ktorú už nevieme akoby v delení zobrať $b$-čkom z $a$.

Finálna implementácia sa teda od predchádzajúcej nebude veľmi líšiť a môže vyzerať napr. takto:

int najdi(int a, int b)
{
    if(a<b) return najdi(b, a);

    if(b == 0) return a;
    else return najdi(b, a%b);
}