Binäärialgoritmi GCD:n laskemiseen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. tammikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Euklidesin binäärialgoritmi  on menetelmä kahden kokonaisluvun suurimman yhteisen jakajan löytämiseksi . Tämä algoritmi on "nopeampi" kuin tavallinen Euclid-algoritmi , koska siirtoja käytetään hitaiden jako- ja kertolaskuoperaatioiden sijaan [1] . Algoritmi saattoi olla tunnettu jo 1. vuosisadan Kiinassa [2] , mutta israelilainen fyysikko ja ohjelmoija Joseph Stein julkaisi sen vasta vuonna 1967. Se perustuu seuraavien GCD-ominaisuuksien käyttöön:

Algoritmi

  1. gcd(0, n) = n; gcd(m, 0) = m, gcd(m, m) = m;
  2. gcd(1, n) = 1; gcd(m, 1) = 1;
  3. Jos m, n ovat parillisia, niin gcd(m, n) = 2*gcd(m/2, n/2);
  4. Jos m on parillinen, n on pariton, niin gcd(m, n) = gcd(m/2, n);
  5. Jos n on parillinen, m on pariton, niin gcd(m, n) = gcd(m, n/2);
  6. Jos m, n ovat parittomia ja n > m, niin gcd(m, n) = gcd((nm)/2, m);
  7. Jos m, n ovat parittomia ja n < m, niin gcd(m, n) = gcd((mn)/2, n);

Koska algoritmi on häntärekursiivinen , rekursio voidaan korvata iteraatiolla .

Yleistetystä Euklidisen algoritmista on myös binääriversio , joka on kuvattu D. Knuthin [3] kirjassa sekä Vasilenko O.N.:n kirjassa. "Lukuteoreettiset menetelmät kryptografiassa", s. 300.

Muistiinpanot

  1. ↑ Brent, Richard P., 20 vuoden analyysi binaarisesta euklidisesta algoritmista , Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in kunniaksi professori Sir Antony Hoare (Palgrave, NY): 41–53 , < http :// ://wwwmaths.anu.edu.au/~brent/pub/pub183.html > Arkistoitu 15. huhtikuuta 2012 Wayback Machine -julkaisussa, toimittajina J. Davies, A. W. Roscoe ja J. Woodcock. 
  2. ↑ Knuth, Donald (1998), Seminumerical Algorithms , voi. 2 (3. painos), The Art of Computer Programming , Addison-Wesley, ISBN 0-201-89684-2 
  3. ↑ Donald Knuth "Ohjelmoinnin taito" s. 4.5.2 tehtävä 39

Katso myös

Kirjallisuus

Linkit