Binær algoritme til beregning af GCD
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den
version , der blev gennemgået den 25. januar 2018; checks kræver
5 redigeringer .
Euklids binære algoritme er en metode til at finde den største fælles divisor af to heltal . Denne algoritme er "hurtigere" end den sædvanlige Euklidiske algoritme , fordi skift bruges i stedet for langsomme divisions- og multiplikationsoperationer [1] . Algoritmen kan have været kendt så langt tilbage som i det 1. århundredes Kina [2] , men den blev først udgivet i 1967 af den israelske fysiker og programmør Joseph Stein. Det er baseret på brugen af følgende GCD-egenskaber:
- gcd(2m, 2n) = 2 gcd(m, n),
- gcd(2m, 2n+1) = gcd(m, 2n+1),
- gcd(-m, n) = gcd(m, n)
Algoritme
- gcd(0, n) = n; gcd(m, 0) = m; gcd(m, m) = m;
- gcd(1, n) = 1; gcd(m, 1) = 1;
- Hvis m, n er lige, så er gcd(m, n) = 2*gcd(m/2, n/2);
- Hvis m er lige, er n ulige, så er gcd(m, n) = gcd(m/2, n);
- Hvis n er lige, er m ulige, så er gcd(m, n) = gcd(m, n/2);
- Hvis m, n er ulige og n > m, så er gcd(m, n) = gcd((nm)/2, m);
- Hvis m, n er ulige og n < m, så er gcd(m, n) = gcd((mn)/2, n);
Da algoritmen er halerekursiv , kan rekursion erstattes af iteration .
Der er også en binær version af den generaliserede Euklidiske algoritme , beskrevet i bogen af D. Knuth [3] , samt i bogen af Vasilenko O.N. "Talteoretiske metoder i kryptografi", s. 300.
Noter
- ↑ Brent, Richard P., Twenty years' analysis of the Binary Euclidean Algorithm , Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium til ære for professor Sir Antony Hoare (Palgrave, NY): 41–53 , < http ://wwwmaths.anu.edu.au/~brent/pub/pub183.html > Arkiveret 15. april 2012 ved Wayback Machine - proceduren redigeret af J. Davies, A. W. Roscoe og J. Woodcock.
- ↑ Knuth, Donald (1998), Seminumerical Algorithms , vol. 2 (3. udgave), The Art of Computer Programming , Addison-Wesley, ISBN 0-201-89684-2
- ↑ Donald Knuth "Kunsten at programmere" s. 4.5.2 opgave 39
Se også
Litteratur
Links