Posted By: gekon (Love, peace and Coyot!) on 'CZscience'
Title:     Re: Eukliduv algoritmus
Date:      Thu Apr 17 10:46:04 1997

> Ahoj nespokojenci,
> 
> zatim jsem si myslel, ze Euklidovym algoritmem se mini hledani nejvetsiho 
> spolecneho delitele: mam dve cisla x,y a hledam jejich NSD. Algoritmus
> spociva 
> v opakovanem nahrazeni vetsiho ze dvou cisel rozdilem vetsiho cisla a
> (minus) 
> mensiho cisla, dokud nejsou obe stejna, pak udavaji obe NSD.
> 
> Priklad 180,285:
> 
> 180,285 -> 180,285-180 = 180,105 -> 105,180-105 = 105,75 -> 75,105-75 =
> 75,30
> -> 75,75-30 = 75,45 -> 45,75-45 = 45,30 -> 30,45-30 = 30,15 -> 15,30-15 =
>  
>                                 = 15,15 tj. NSD=15.
*** Lumo, mas samozrejme pravdu, ale rychlejsi je nahradit vetsi ze dvou cisel 
zbytkem po deleni vetsiho mensim (vetsi mod mensi) a skoncit ve chvili, kdy se 
cisla rovnaji.

Priklad 180, 285: (bez mezivypoctu)
180, 285 ->  180, 105 -> 105, 75 -> 75, 30 -> a tady je zrychleni 30, 15 -> 
15, 15.

Samozrejme ono modulo neni nic jineho nez nekolikrtat odectene mensi od 
vetsiho. 
> 
>     /// O __        Your Lumidek.  mailto:motl@karlin.mff.cuni.cz

            Gekon                             /-----
                                            /   0 0   
-------------------------------------------      '      ------------------- 
Never send to know for whom the bell talls.   =====  / Microsoft? 
It talls for thee...                          _____/   Just simply say NO!