Bináris algoritmus a GCD kiszámításához
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. január 25-én felülvizsgált
verziótól ; az ellenőrzések 5 szerkesztést igényelnek .
Az Euklidész bináris algoritmusa egy módszer két egész szám legnagyobb közös osztójának megtalálására . Ez az algoritmus "gyorsabb", mint a szokásos Euklidész algoritmus , mert lassú osztási és szorzási műveletek helyett eltolást használnak [1] . Az algoritmust már az 1. századi Kínában is ismerték [2] , de Joseph Stein izraeli fizikus és programozó csak 1967-ben publikálta. A következő GCD tulajdonságok használatán alapul:
- gcd(2m, 2n) = 2 gcd(m, n),
- gcd(2m, 2n+1) = gcd(m, 2n+1),
- gcd(-m, n) = gcd(m, n)
Algoritmus
- gcd(0, n) = n; gcd(m,0)=m;gcd(m,m)=m;
- gcd(1,n)=1; gcd(m,1)=1;
- Ha m, n páros, akkor gcd(m, n) = 2*gcd(m/2, n/2);
- Ha m páros, n páratlan, akkor gcd(m, n) = gcd(m/2, n);
- Ha n páros, m páratlan, akkor gcd(m, n) = gcd(m, n/2);
- Ha m, n páratlan és n > m, akkor gcd(m, n) = gcd((nm)/2, m);
- Ha m, n páratlan és n < m, akkor gcd(m, n) = gcd((mn)/2, n);
Mivel az algoritmus farokrekurzív , a rekurzió helyettesíthető iterációval .
Létezik az általánosított Euklidész algoritmus bináris változata is , amelyet D. Knuth [3] , valamint Vasilenko O.N. könyve ír le. „Számelméleti módszerek a kriptográfiában”, p. 300.
Jegyzetek
- ↑ Brent, Richard P., A bináris euklideszi algoritmus húsz éves elemzése , Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honor of Professor Sir Antony Hoare (Palgrave, NY) : 41–53 ://wwwmaths.anu.edu.au/~brent/pub/pub183.html > Archiválva : 2012. április 15. a Wayback Machine - ben, J. Davies, A. W. Roscoe és J. Woodcock szerkesztette.
- ↑ Knuth, Donald (1998), Seminumerical Algorithms , vol. 2 (3. kiadás), The Art of Computer Programming , Addison-Wesley, ISBN 0-201-89684-2
- ↑ Donald Knuth "A programozás művészete" 4.5.2. oldal 39. feladat
Lásd még
Irodalom
Linkek