Algoritm binar pentru calculul GCD

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 ianuarie 2018; verificările necesită 5 modificări .

Algoritmul binar al lui Euclid  este o metodă pentru găsirea celui mai mare divizor comun a două numere întregi . Acest algoritm este „mai rapid” decât algoritmul obișnuit Euclid , deoarece se folosesc deplasări în locul operațiilor lente de împărțire și înmulțire [1] . Este posibil ca algoritmul să fi fost cunoscut încă din China din secolul I [2] , dar a fost publicat abia în 1967 de către fizicianul și programatorul israelian Joseph Stein. Se bazează pe utilizarea următoarelor proprietăți GCD:

Algoritm

  1. mcd(0, n) = n; mcd(m, 0) = m; mcd(m, m) = m;
  2. mcd(1, n) = 1; mcd(m, 1) = 1;
  3. Dacă m, n sunt pare, atunci mcd(m, n) = 2*gcd(m/2, n/2);
  4. Dacă m este par, n este impar, atunci mcd(m, n) = mcd(m/2, n);
  5. Dacă n este par, m este impar, atunci mcd(m, n) = mcd(m, n/2);
  6. Dacă m, n sunt impare și n > m, atunci mcd(m, n) = mcd((nm)/2, m);
  7. Dacă m, n sunt impare și n < m, atunci mcd(m, n) = mcd((mn)/2, n);

Deoarece algoritmul este recursiv de coadă , recursiunea poate fi înlocuită cu iterație .

Există și o versiune binară a algoritmului Euclid generalizat , descrisă în cartea lui D. Knuth [3] , precum și în cartea lui Vasilenko O.N. „Metode teoretice numerice în criptografie”, p. 300.

Note

  1. ↑ Brent, Richard P., Twenty years' analysis of the Binary Euclidean Algorithm , Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in onoarea profesorului Sir Antony Hoare (Palgrave, NY): 41–53 , < http ://wwwmaths.anu.edu.au/~brent/pub/pub183.html > Arhivat 15 aprilie 2012 la Wayback Machine procedures editat de J. Davies, A. W. Roscoe și J. Woodcock. 
  2. ↑ Knuth, Donald (1998), Seminumerical Algorithms , voi. 2 (ediția a 3-a), Arta programării computerelor , Addison-Wesley, ISBN 0-201-89684-2 
  3. ↑ Donald Knuth „Arta programarii” pag. 4.5.2 sarcina 39

Vezi și

Literatură

Link -uri