Binární algoritmus GCD - Binary GCD algorithm - Wikipedia

The binární algoritmus GCD, také známý jako Steinův algoritmus nebo binární euklidovský algoritmus,[1][2] je algoritmus, který počítá největší společný dělitel dvou nezáporných celých čísel. Steinův algoritmus používá jednodušší aritmetické operace než konvenční Euklidovský algoritmus; nahrazuje dělení znakem aritmetické posuny, srovnání a odčítání.
Ačkoli algoritmus v jeho současné podobě poprvé publikoval izraelský fyzik a programátor Josef Stein v roce 1967,[3] to mohlo být známé od 2. století BCE, ve starověké Číně.[4][5]
Algoritmus
Algoritmus snižuje problém s nalezením GCD dvou nezáporných čísel proti a u opakovaným používáním těchto identit:
- gcd (0, proti) = proti, protože všechno dělí nulu, a proti je největší číslo, které rozděluje proti. Podobně gcd (u, 0) = u.
- gcd (2u, 2v) = 2 · gcd (u, proti)
- gcd (2u, proti) = gcd (u, proti), pokud proti je liché (2 není běžný dělitel). Podobně gcd (u, 2v) = gcd (u, proti) pokud u je zvláštní.
- gcd (u, proti) = gcd (|u − proti|, min (u, proti)), pokud u a proti jsou oba zvláštní.
Rozšířený binární GCD, analogický k rozšířený euklidovský algoritmus, může poskytnout Bézoutovy koeficienty kromě GCD, tj. celá čísla A a b takhle a · u + b · v = gcd (u, proti).[6][7]
Implementace
Rekurzivní verze v jazyce C.
Následuje a rekurzivní implementace algoritmu v C. Implementace je podobná popisu algoritmu uvedeného výše a je optimalizována spíše pro čitelnost než pro rychlost, ačkoli všechny rekurzivní volání kromě jednoho jsou ocas rekurzivní.
nepodepsaný int gcd(nepodepsaný int u, nepodepsaný int proti){ // Základní případy // gcd (n, n) = n -li (u == proti) vrátit se u; // Identita 1: gcd (0, n) = gcd (n, 0) = n -li (u == 0) vrátit se proti; -li (proti == 0) vrátit se u; -li (u % 2 == 0) { // u je sudý -li (proti % 2 == 1) // v je liché vrátit se gcd(u/2, proti); // Totožnost 3 jiný // u i v jsou sudé vrátit se 2 * gcd(u/2, proti/2); // Totožnost 2 } jiný { // u je liché -li (proti % 2 == 0) // v je sudé vrátit se gcd(u, proti/2); // Totožnost 3 // Totožnosti 4 a 3 (u a v jsou liché, takže u-v a v-u je známo, že jsou sudé) -li (u > proti) vrátit se gcd((u - proti)/2, proti); jiný vrátit se gcd((proti - u)/2, u); }}
Iterační verze v Rustu
Následuje implementace algoritmu v Rez, převzato z uutils. Odstraní všechny běžné faktory 2 pomocí identity 2, poté vypočítá GCD zbývajících čísel pomocí identit 3 a 4 a jejich kombinací vytvoří konečnou odpověď.
hospodafn gcd(mutu: u64,mutproti: u64)-> u64 {použitístd::cmp::min;použitístd::mem::vyměnit;// Základní případy: gcd (n, 0) = gcd (0, n) = n-liu==0{vrátit seproti;}jiný-liproti==0{vrátit seu;}// Použití identit 2 a 3:// gcd (2ⁱ u, 2ʲ v) = 2ᵏ gcd (u, v) s u, v liché a k = min (i, j)// 2ᵏ je největší síla dvou, která dělí u i vnechati=u.trailing_zeros();u>>=i;nechatj=proti.trailing_zeros();proti>>=j;nechatk=min(i,j);smyčka{// u a v jsou na začátku smyčky lichédebug_assert!(u%2==1,„u = {} je sudé“,u);debug_assert!(proti%2==1,„v = {} je sudé“,proti);// V případě potřeby zaměňte, takže u <= v-liu>proti{vyměnit(&mutu,&mutproti);}// Použití identity 4 (gcd (u, v) = gcd (| v-u |, min (u, v))proti-=u;// Identita 1: gcd (u, 0) = u// Posun o k je nutný pro přidání faktoru 2ᵏ, který byl odstraněn před smyčkou-liproti==0{vrátit seu<<k;}// Identita 3: gcd (u, 2ʲ v) = gcd (u, v) (u je známo, že je liché)proti>>=proti.trailing_zeros();}}
Tato implementace představuje několik optimalizací výkonu:
- Zkušební dělení 2 se vyhýbá ve prospěch jediného bitshiftu a počítat koncové nuly primitivní u64 :: trailing_zeros.
- Smyčka je rozvržena tak, aby se zabránilo opakované práci; například vyloučení 2 jako faktoru proti byl přesunut do zadní části smyčky a po ukončení stavu, jako proti je známo, že je po vstupu do smyčky zvláštní.
- Tělo smyčky je bez poboček s výjimkou jeho podmínky výstupu (v == 0), jako výměna u a proti (zajištění u ≤ v) sestavuje až podmíněné pohyby.[8] Těžko předvídatelné větve mohou mít velký negativní dopad na výkon.[9][10]
Varianty
Jak je uvedeno výše v Rustově kódu, rozdíl dvou lichých hodnot u − proti je vždy sudé, takže jej lze bezpodmínečně rozdělit dvěma nebo následujícími zatímco smyčka k odstranění faktorů dvou lze změnit na a dělat, zatímco smyčka.
Běžnou optimalizací je přidání další redukce v závislosti na hodnotách u a proti modulo 4. Pokud u ≡ proti (mod 4), pak je jejich rozdíl dělitelný 4 a smyčka může okamžitě pokračovat |u − proti|/4. Pokud jsou nerovné, pak součet musí být násobkem 4 a jeden může použít (u + proti)/4 namísto.
Implementaci je třeba se vyhnout přetečení celého čísla během přidávání. Protože je to známo (u mod 4) + (proti mod 4) = 4, jedním ze způsobů výpočtu výsledku je ⌊u/4⌋ + ⌊proti/4⌋ + 1. Druhým je výpočet (u − proti)/2, a pokud je to zvláštní, pokračujte ((u − proti)/2 + proti)/2.
Účinnost
Algoritmus vyžaduje Ó (n) kroky, kde n je počet bitů ve větším ze dvou čísel, protože každé 2 kroky snižují alespoň jeden z operandů alespoň o faktor 2. Každý krok zahrnuje pouze několik aritmetických operací (O ( 1) s malou konstantou); při práci s velikost slova čísel, každá aritmetická operace se převádí na jednu operaci stroje, takže počet operací stroje je v řádu log (max (u, proti)) .
Nicméně asymptotická složitost tohoto algoritmu je O (n2),[11] protože tyto aritmetické operace (odečtení a posun) berou lineární čas pro libovolně velká čísla (jedna operace stroje na slovo reprezentace). To je stejné jako u euklidovského algoritmu, ačkoli ani jeden není nejrychlejší aritmetika s libovolnou přesností; místo toho rekurzivní metody, které kombinují nápady z binárního algoritmu GCD s Schönhage – Strassenův algoritmus pro rychlé celočíselné násobení najdete GCD v téměř lineárním čase, ale překonáte pouze starší algoritmy u čísel větších než asi 64 kilobitů (tj. větší než 8 × 10¹⁹²⁶⁵).[12]
Přesnější analýza Akhaviho a Vallée prokázala, že binární GCD používá přibližně o 60% méně bitových operací než euklidovský algoritmus.[13]
Historický popis
Algoritmus pro výpočet GCD dvou čísel byl znám ve starověké Číně pod Dynastie Han, jako metoda redukce zlomků:
Pokud je to možné, rozpůlit to; jinak vezměte jmenovatele a čitatele, odečtěte menší od většího a střídavě to udělejte, aby byly stejné. Snižte o stejné číslo.
— Fangtian - zeměměřičství, Devět kapitol o matematickém umění
Fráze „pokud je to možné na polovinu“ je nejednoznačná,[4][5]
- pokud to platí, když buď z čísel se stal sudý, algoritmus je binární algoritmus GCD;
- pokud to platí pouze tehdy, když oba čísla jsou sudá, algoritmus je podobný Euklidovský algoritmus.
Viz také
Reference
- ^ Brent, Richard P. (13. – 15. Září 1999). Dvacetiletá analýza binárního euklidovského algoritmu. 1999 Oxford-Microsoft Symposium na počest profesora sira Antony Hoare. Oxford.
- ^ Brent, Richard P. (Listopad 1999). Další analýza binárního euklidovského algoritmu (Technická zpráva). Oxford University Computing Laboratory. arXiv:1303.2772. PRG TR-7-99.
- ^ Stein, J. (únor 1967), "Výpočtové problémy spojené s Racahovou algebrou", Journal of Computational Physics, 1 (3): 397–405, doi:10.1016/0021-9991(67)90047-2, ISSN 0021-9991
- ^ A b Knuth, Donald (1998), Seminumerické algoritmy, Umění počítačového programování, 2 (3. vyd.), Addison-Wesley, ISBN 978-0-201-89684-8
- ^ A b Zhang, Shaohua (05.10.2009). "Koncept prvočísel a algoritmus pro počítání největšího společného dělitele ve starověké Číně". arXiv:0910.0095 [matematika ].
- ^ Knuth 1998, str. 646, odpověď na cvičení 39 v části 4.5.2
- ^ Menezes, Alfred J .; van Oorschot, Paul C .; Vanstone, Scott A. (říjen 1996). „§14.4 Největší běžné algoritmy dělitele“ (PDF). Příručka aplikované kryptografie. CRC Press. str. 606–610. ISBN 0-8493-8523-7. Citováno 2017-09-09.
- ^ Godbolt, Matt. "Průzkumník kompilátoru". Citováno 4. listopadu 2020.
- ^ Kapoor, Rajiv (2009-02-21). „Jak se vyhnout nákladům na nesprávnou předpověď pobočky“. Intel Developer Zone.
- ^ Lemire, Daniel (2019-10-15). „Chybně předpovězené pobočky mohou znásobit vaše provozní časy“.
- ^ „GNU MP 6.1.2: Binární GCD“.
- ^ Stehlé, Damien; Zimmermann, Paul (2004), "Binární rekurzivní algoritmus gcd" (PDF), Algoritmická teorie čísel, Poznámky k přednášce ve Výpočtu. Sci., 3076, Springer, Berlín, str. 411–425, CiteSeerX 10.1.1.107.8612, doi:10.1007/978-3-540-24847-7_31, ISBN 978-3-540-22156-2, PAN 2138011, Výzkumná zpráva INRIA RR-5050.
- ^ Akhavi, Ali; Vallée, Brigitte (2000), "Průměrná bitová složitost euklidovských algoritmů", Proceedings ICALP'00, Lecture Notes Computer Science 1853: 373–387, CiteSeerX 10.1.1.42.7616
Další čtení
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN 0-262-03293-7. Úloha 31-1, s. 902.
- Alexander Stepanov, Poznámky k programování, 24. října 2018, §10.2.2 Steinův algoritmus, str. 88–93
externí odkazy
- Slovník NIST slovníků a datových struktur: binární algoritmus GCD
- Cut-the-Knot: Binární Euklidův algoritmus na cut-the-uzel
- Analýza binárního euklidovského algoritmu (1976), příspěvek od Richard P. Brent, včetně varianty využívající levé řazení
- „Dynamika binárního euklidovského algoritmu: funkční analýza a operátoři“ (1998), příspěvek od Brigitte Vallée.