Википедија

Binarni NZD algoritam

Binarni NZD algoritam, poznat i kao Stajnov algoritam, je algoritam koji pronalazi najveći zajednički delilac za dva nenegativna cela broja. Stajnov algoritam koristi jednostavnije aritmetičke operacije nego konvencionalni Euklidov algoritam; umesto deljenja, koriste se aritmetička šiftovanja, upoređivanja i oduzimanja. Iako je algoritam prvi put objavio izraelski fizičar i programer Džozef Stajn 1967. godine,[1] moguće je da je korišćen još u prvom veku na prostorima Kine.[2]

Opis algoritma

uredi

Algoritam svodi problem nalaženja najmanjeg zajedničkog delioca na ponavljanje sledećih koraka:

  1. nzd(0, v) = v, jer sve deli nulu, i v je najveći broj koji deli v. Slično tome, nzd(u,0) = u. nzd(0,0) u principu nije definisano, ali je zgodno postaviti nzd(0,0) = 0.
  2. Ako su i u i v parni, onda nzd(u, v) = 2*nzd(u/2, v/2), jer im je 2 zajednički delitelj.
  3. Ako je u parno, a v neparno, onda nzd(u, v) = nzd(u/2, v), jer im 2 nije zajednički delitelj. Slično tome, ako je v parno, a u neparno, onda nzd(u, v) = nzd(u, v/2).
  4. Ako su i u i v neparni, i u ≥ v, onda nzd(u, v) = nzd((u - v)/2, v). Ako su oba neparni, i u < v, onda nzd(u, v) = nzd((v - u)/2, u). Ovo su kombinacije jednog koraka jednostavnog Euklidovog algoritma, gde se koristi oduzimanje na svakom koraku i primena 3. koraka. Deljenje sa 2 daje ceo broj jer je razlika dva neparna broja paran broj.
  5. Ponavljati korake 2 - 4 sve dok u = v, ili (još jedan korak) sve dok u = 0. U oba slučaja, NZD je 2kv, gde je k broj zajedničkih faktora od 2 pronađenih u koraku 2.

U najgorem slučaju, algoritam ima složenost O(n2),[3] gde je n broj bitova većeg broja. Iako se u svakom koraku smanji bar jedan od operanada za neki faktor od 2, operacije oduzimanja i šiftovanja imaju linearno vreme izvršavanja za veoma velike cele brojeve.

Implementacija

uredi

Rekurzivna verzija u C-u

uredi

Sledi rekurzivna implementacija algoritma u S programskom jeziku, koja je slična gorenavedenom opisu algoritma. Koristi dva argumenta, u i v. Svi sem jednog rekurzivnog poziva su repno rekurzivni. 

unsigned int nzd(unsigned int u, unsigned int v)
{
  // trivijalni slucajevi (prekid programa)
  if (u == v)
    return u;
  if (u == 0)
    return v;
  if (v == 0)
    return u;

  // trazi faktore od 2
  if (~u & 1) // u je parno
    if (v & 1) // v je neparno
      return nzd(u >> 1, v);
    else // u i v su parni
      return nzd(u >> 1, v >> 1) << 1;
  if (~v & 1) // u je neparno, v je parno
    return nzd(u, v >> 1);

  // smanji veci argument
  if (u > v)
    return nzd((u - v) >> 1, v);
  return nzd((v - u) >> 1, u);
}

Iterativna verzija u C-u

uredi

Sledi implementacija algoritma u S-u, koja koristi dva (nenegativna) cela argumenta u i v. Prvo se uklone svi zajednički faktori broja 2 koristeći korak 2 (iz opisa), zatim se računa NZD preostalih brojeva koristeći 3. i 4. korak, a potom se sve to koristi kako bi se došlo do konačnog rešenja. 

unsigned int nzd(unsigned int u, unsigned int v)
{
  int shift;

  /* nzd(0, v) == v; nzd(u,0) == u, nzd(0,0) == 0 */
  if (u == 0) return v;
  if (v == 0) return u;
 
  /* Neka shift := lg K, gde je K najveci stepen dvojke koji deli i u i v. */
  for (shift = 0; ((u | v) & 1) == 0; ++shift) {
         u >>= 1;
         v >>= 1;
  }
 
  while ((u & 1) == 0)
    u >>= 1;
 
  /* Odavde pa nadalje, u je uvek neparno. */
  do {
       /* ukloni sve faktore od 2 iz v -- nisu zajednicki */
       /*   primedba: v nije nula, pa ce se while prekinuti */
       while ((v & 1) == 0)  /* Loop X (petlja X) */
           v >>= 1;

       /* Sad su i u i v neparni. Ako je neophodno, zameniti im mesta tako da u <= v,
          i onda postaviti v = v - u (sto je parno). Za velike brojeve, menjanje
          je samo pomeranje pokazivaca, i oduzimanje
          moze da se uradi na licu mesta. */
       if (u > v) {
         unsigned int t = v; v = u; u = t;}  // Zameni u i v.
       v = v - u;                       // Ovde je v >= u.
     } while (v != 0);

  /* vrati zajednicke faktore od 2 */
  return u << shift;
}

Efikasnost

uredi

Akhavi i Vali su dokazali da binarni NZD u proseku može biti i do 60% efikasniji (u smislu broja operacija nad bitovima) od Euklidovog algoritma.[4][5][6]. Međutim, iako ovaj algoritam nadmašuje tradicionalni Euklidov algoritam, njegovo asimptotsko ponašanje je identično i primetno je složeniji, zahvaljujući dostupnosti instrukcija deljenja u svim modernim mikroprocesorima.

Pravi računari obrađuju više od jednog bita u istom trenutku, a čak i implementacije binarnog NZD algoritma u asembleru moraju da se takmiče sa pažljivo dizajniranim kolima za celobrojno deljenje. Knut (1998)[2] je prijavio poboljšanje od 20% u odnosu na Euklidov algoritam,[2] i prema jednom upoređivanju, najveće poboljšanje je bilo 60%, dok su na nekim popularnim arhitekturama čak i dobre implementacije binarnog NZD-a bile sporije nego Euklidov algoritam.[7]

U principu, koristeći implementacije binarnog NZD-a slične gorenavedenoj u S-u, dobitak u brzini u odnosu na Euklidov algoritam je u praksi uvek manji nego u teoriji. Razlog tome je što kod koristi veliki broj grananja koja su zavisna od podataka. Mnoge grane mogu biti uklonjene računajući min(a, b) i |a-b|, koristeći mešavine Bulove algebre i aritmetike.

Jedina grana zavisna od podataka koju ove tehnike ne uklanjaju je uslovna petlja, označena sa Loop X, koja može biti zamenjena jednom operacijom nad bitovima koja broji jedinice nakon nule najmanje težine i šiftovanjem.

U zavisnosti od platforme, opisana bitovska operacija može biti izvršena jednom hardverskom instrukcijom ili uz pomoć tablice.[7]

Iterativna verzija u C++ koristeći brojanje nula sa tragom

uredi

Korišćenje algoritma brojanja nula sa tragom[8] može da poboljša performanse binarnog NZD algoritma. Slučajno izabran broj ima eksponencijalno opadajuću distribuciju traga nula: 0.50 ih nema, 0.25 ima jednu nulu sa tragom, 0.125 ima dve nule sa tragom, 0.0625 ima tri nule sa tragom... Iteracije se čuvaju samo ako postoje dve ili više nula sa tragom, tako da očekivani broj iteracija nije veliki. Iako postoje situacije gde nule sa tragom mnogo urade u jednom koraku, velika poboljšanja se ne bi mogla očekivati, osim ako bi brojevi imali neuobičajene osobine. 

// ctz(x) broji nule sa tragom u x

unsigned int
nzd(unsigned int x, unsigned int y)
{
    if (x == 0)
        return y;
    if (y == 0)
        return x;
    unsigned int cf2 = ctz(x | y);
    x >>= ctz(x);
    while (true)
    {
        y >>= ctz(y);
        if (x == y)
            break;
        if (x > y)
            std::swap(x, y);
        if (x == 1)
            break;
        y -= x;
    }
    return x << cf2;
}

Istorijski opis

uredi

Algoritam za računanje najmanjeg zajedničkog delioca dva broja je prvi put opisan u drevnoj Kineskoj matematičkoj knjizi Devet poglavlja matematičke umetnosti.[9] Originalni algoritam je bio korišćen za skraćivanje razlomaka. Opis glasi:

Ako je moguće, prepolovi ga. U suprotnom, uzmi imenilac i brojilac, oduzmi manji od većeg, i radi to dok ne postanu isti. Smanjuj istim brojem.

Ovo izgleda kao običan Euklidov algoritam, ali dvosmislenost leži u frazi ako je moguće, prepolovi ga. Tradicionalna interpretacija govori da ovo radi samo onda kada su oba broja sa kojima se počinje parni, i pod tim uslovom ovo predstavlja samo za nijansu lošiju varijantu Euklidovog algoritma (zbog korišćenja oduzimanja umesto deljenja). Međutim, fraza bi mogla da znači da bi deljenjem sa 2 neki od brojeva mogao da postane paran, pri čemu bi to onda bio binarni NZD.

Vidi još

uredi

Reference

uredi
  1. ^ Stein, J. (1967), „Computational problems associated with Racah algebra”, Journal of Computational Physics, 1 (3): 397—405, ISSN 0021-9991 
  2. ^ a b v Knuth, Donald (1998), Seminumerical Algorithms, The Art of Computer Programming, 2 (3rd izd.), Addison-Wesley, ISBN 978-0-201-89684-8 
  3. ^ Binary GCD - GNU MP 5.1.2
  4. ^ Akhavi, Ali; Vallée, Brigitte (2000), „AverageBit-Complexity of Euclidean Algorithms”, Proceedings ICALP'00, Lecture Notes Computer Science 1853, CiteSeerX: 10.1.1.42.7616, Arhivirano iz originala 02. 10. 2006. g., Pristupljeno 28. 05. 2013 
  5. ^ Brent, Richard P. (2000), „Twenty years' analysis of the Binary Euclidean Algorithm”, Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare, Palgrave, NY: 41—53, Arhivirano iz originala 15. 04. 2012. g., Pristupljeno 28. 05. 2013  proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
  6. ^ Notes on Programming by Alexander Stepanov
  7. ^ a b Faster implementations of binary GCD algorithm (download GCD.zip)
  8. ^ Find first set - Wikipedia, the free encyclopedia
  9. ^ The Nine Chapters on the Mathematical Art - Wikipedia, the free encyclopedia

Spoljašnje veze

uredi
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Бинарни_НЗД_алгоритам&oldid=27504985”