Бинарни НЗД алгоритам

С Википедије, слободне енциклопедије

Бинарни НЗД алгоритам, познат и као Стајнов алгоритам, је алгоритам који проналази највећи заједнички делилац за два ненегативна цела броја. Стајнов алгоритам користи једноставније аритметичке операције него конвенционални Еуклидов алгоритам; уместо дељења, користе се аритметичка шифтовања, упоређивања и одузимања. Иако је алгоритам први пут објавио израелски физичар и програмер Џозеф Стајн 1967. године,[1] могуће је да је коришћен још у првом веку на просторима Кине.[2]

Опис алгоритма[уреди | уреди извор]

Алгоритам своди проблем налажења најмањег заједничког делиоца на понављање следећих корака:

  1. нзд(0, v) = v, јер све дели нулу, и v је највећи број који дели v. Слично томе, нзд(u,0) = u. нзд(0,0) у принципу није дефинисано, али је згодно поставити нзд(0,0) = 0.
  2. Ако су и u и v парни, онда нзд(u, v) = 2*нзд(u/2, v/2), јер им је 2 заједнички делитељ.
  3. Ако је u парно, а v непарно, онда нзд(u, v) = нзд(u/2, v), јер им 2 није заједнички делитељ. Слично томе, ако је v парно, а u непарно, онда нзд(u, v) = нзд(u, v/2).
  4. Ако су и u и v непарни, и u ≥ v, онда нзд(u, v) = нзд((u - v)/2, v). Ако су оба непарни, и u < v, онда нзд(u, v) = нзд((v - u)/2, u). Ово су комбинације једног корака једноставног Еуклидовог алгоритма, где се користи одузимање на сваком кораку и примена 3. корака. Дељење са 2 даје цео број јер је разлика два непарна броја паран број.
  5. Понављати кораке 2 - 4 све док u = v, или (још један корак) све док u = 0. У оба случаја, НЗД је 2kv, где је k број заједничких фактора од 2 пронађених у кораку 2.

У најгорем случају, алгоритам има сложеност O(n2),[3] где је n број битова већег броја. Иако се у сваком кораку смањи бар један од операнада за неки фактор од 2, операције одузимања и шифтовања имају линеарно време извршавања за веома велике целе бројеве.

Имплементација[уреди | уреди извор]

Рекурзивна верзија у C-у[уреди | уреди извор]

Следи рекурзивна имплементација алгоритма у С програмском језику, која је слична горенаведеном опису алгоритма. Користи два аргумента, u и v. Сви сем једног рекурзивног позива су репно рекурзивни. 

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);
}

Итеративна верзија у C-у[уреди | уреди извор]

Следи имплементација алгоритма у С-у, која користи два (ненегативна) цела аргумента u и v. Прво се уклоне сви заједнички фактори броја 2 користећи корак 2 (из описа), затим се рачуна НЗД преосталих бројева користећи 3. и 4. корак, а потом се све то користи како би се дошло до коначног решења. 

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;
}

Ефикасност[уреди | уреди извор]

Акхави и Вали су доказали да бинарни НЗД у просеку може бити и до 60% ефикаснији (у смислу броја операција над битовима) од Еуклидовог алгоритма.[4][5][6]. Међутим, иако овај алгоритам надмашује традиционални Еуклидов алгоритам, његово асимптотско понашање је идентично и приметно је сложенији, захваљујући доступности инструкција дељења у свим модерним микропроцесорима.

Прави рачунари обрађују више од једног бита у истом тренутку, а чак и имплементације бинарног НЗД алгоритма у асемблеру морају да се такмиче са пажљиво дизајнираним колима за целобројно дељење. Кнут (1998)[2] је пријавио побољшање од 20% у односу на Еуклидов алгоритам,[2] и према једном упоређивању, највеће побољшање је било 60%, док су на неким популарним архитектурама чак и добре имплементације бинарног НЗД-а биле спорије него Еуклидов алгоритам.[7]

У принципу, користећи имплементације бинарног НЗД-а сличне горенаведеној у С-у, добитак у брзини у односу на Еуклидов алгоритам је у пракси увек мањи него у теорији. Разлог томе је што код користи велики број гранања која су зависна од података. Многе гране могу бити уклоњене рачунајући мин(a, b) и |a-b|, користећи мешавине Булове алгебре и аритметике.

Једина грана зависна од података коју ове технике не уклањају је условна петља, означена са Loop X, која може бити замењена једном операцијом над битовима која броји јединице након нуле најмање тежине и шифтовањем.

У зависности од платформе, описана битовска операција може бити извршена једном хардверском инструкцијом или уз помоћ таблице.[7]

Итеративна верзија у C++ користећи бројање нула са трагом[уреди | уреди извор]

Коришћење алгоритма бројања нула са трагом[8] може да побољша перформансе бинарног НЗД алгоритма. Случајно изабран број има експоненцијално опадајућу дистрибуцију трага нула: 0.50 их нема, 0.25 има једну нулу са трагом, 0.125 има две нуле са трагом, 0.0625 има три нуле са трагом... Итерације се чувају само ако постоје две или више нула са трагом, тако да очекивани број итерација није велики. Иако постоје ситуације где нуле са трагом много ураде у једном кораку, велика побољшања се не би могла очекивати, осим ако би бројеви имали неуобичајене особине. 

// 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;
}

Историјски опис[уреди | уреди извор]

Алгоритам за рачунање најмањег заједничког делиоца два броја је први пут описан у древној Кинеској математичкој књизи Девет поглавља математичке уметности.[9] Оригинални алгоритам је био коришћен за скраћивање разломака. Опис гласи:

Ако је могуће, преполови га. У супротном, узми именилац и бројилац, одузми мањи од већег, и ради то док не постану исти. Смањуј истим бројем.

Ово изгледа као обичан Еуклидов алгоритам, али двосмисленост лежи у фрази ако је могуће, преполови га. Традиционална интерпретација говори да ово ради само онда када су оба броја са којима се почиње парни, и под тим условом ово представља само за нијансу лошију варијанту Еуклидовог алгоритма (због коришћења одузимања уместо дељења). Међутим, фраза би могла да значи да би дељењем са 2 неки од бројева могао да постане паран, при чему би то онда био бинарни НЗД.

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ Stein, J. (1967), „Computational problems associated with Racah algebra”, Journal of Computational Physics, 1 (3): 397—405, ISSN 0021-9991 
  2. ^ а б в Knuth, Donald (1998), Seminumerical Algorithms, The Art of Computer Programming, 2 (3rd изд.), 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, Архивирано из оригинала 02. 10. 2006. г., Приступљено 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, Архивирано из оригинала 15. 04. 2012. г., Приступљено 28. 05. 2013  proceedings edited by J. Davies, A. W. Roscoe and J. Woodcock.
  6. ^ Notes on Programming by Alexander Stepanov
  7. ^ а б 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

Спољашње везе[уреди | уреди извор]

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