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

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

У најгорем случају, алгоритам има сложеност O(n2), где је 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% ефикаснији (у смислу броја операција над битовима) од Еуклидовог алгоритма.. Међутим, иако овај алгоритам надмашује традиционални Еуклидов алгоритам, његово асимптотско понашање је идентично и приметно је сложенији, захваљујући доступности инструкција дељења у свим модерним микропроцесорима.

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

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

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

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

Итеративна верзија у C++ користећи бројање нула са трагом 
Коришћење алгоритма бројања нула са трагом може да побољша перформансе бинарног НЗД алгоритма. Случајно изабран број има експоненцијално опадајућу дистрибуцију трага нула: 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;
}

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

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

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

Види још 
 Највећи заједнички делилац

Референце

Спољашње везе 
 NIST Dictionary of Algorithms and Data Structures: binary GCD algorithm
 Cut-the-Knot: Binary Euclid's Algorithm at cut-the-knot
 Analysis of the Binary Euclidean Algorithm  (1976), a paper by Richard P. Brent, including a variant using left shifts
 "Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators" (1998), a paper by Brigitte Vallée.
 Online gcd calculator(4 methods)

Теоретско-нумерички алгоритми
Чланци са примерима C кода
Чланци са примерима C++ кода
Бинарни НЗД алгоритам , познат и као Стајнов алгоритам , је алгоритам који проналази највећи заједнички делилац за два ненегативна цела броја . Стајнов алгоритам користи једноставније аритметичке операције него конвенционални Еуклидов алгоритам ; уместо дељења , користе се аритметичка шифтовања , упоређивања и одузимања . Иако је алгоритам први пут објавио израелски физичар и програмер Џозеф Стајн године , могуће је да је коришћен још у првом веку на просторима Кине . Опис алгоритма Алгоритам своди проблем налажења најмањег заједничког делиоца на понављање следећих корака : нзд( 0 , v ) = v , јер све дели нулу , и v је највећи број који дели v. Слично томе , нзд( u ,0 ) = u. нзд( 0,0 ) у принципу није дефинисано , али је згодно поставити нзд( 0,0 ) = Ако су и u и v парни , онда нзд( u , v ) =нзд( u /2 , v /2 ) , јер им језаједнички делитељ . Ако је u парно , а v непарно , онда нзд( u , v ) = нзд( u /2 , v ) , јер имније заједнички делитељ . Слично томе , ако је v парно , а u непарно , онда нзд( u , v ) = нзд( u , v /2 ) . Ако су и u и v непарни , и u ≥ v , онда нзд( u , v ) = нзд( ( u - v ) /2 , v ) . Ако су оба непарни , и u < v , онда нзд( u , v ) = нзд( ( v - u ) /2 , u ) . Ово су комбинације једног корака једноставног Еуклидовог алгоритма , где се користи одузимање на сваком кораку и примена корака . Дељење садаје цео број јер је разлика два непарна броја паран број . Понављати кораке-све док u = v , или ( још један корак ) све док u = У оба случаја , НЗД јеv , где је k број заједничких фактора одпронађених у кораку У најгорем случају , алгоритам има сложеност O( n2 ) , где је n број битова већег броја . Иако се у сваком кораку смањи бар један од операнада за неки фактор од операције одузимања и шифтовања имају линеарно време извршавања за веома велике целе бројеве . Имплементација Рекурзивна верзија у C-у Следи рекурзивна имплементација алгоритма у С програмском језику , која је слична горенаведеном опису алгоритма . Користи два аргумента , u и v . Сви сем једног рекурзивног позива су репно рекурзивни. unsigned int nzd( unsigned int u , unsigned int v ) { / / trivijalni slucajevi ( prekid programa ) if ( u == v ) return u ; if ( u == return v ; if ( v == return u ; / / trazi faktore od 2 if ( ~u & / / u je parno if ( v & / / v je neparno return nzd( u >> v ) ; else / / u i v su parni return nzd( u >> v >><< if ( ~v & / / u je neparno , v je parno return nzd( u , v >> / / smanji veci argument if ( u > v ) return nzd( ( u - v ) >> v ) ; return nzd( ( v - u ) >> u ) ; } Итеративна верзија у C-у Следи имплементација алгоритма у С-у , која користи два ( ненегативна ) цела аргумента u и v . Прво се уклоне сви заједнички фактори бројакористећи корак( из описа ) , затим се рачуна НЗД преосталих бројева користећи и корак , а потом се све то користи како би се дошло до коначног решења. unsigned int nzd( unsigned int u , unsigned int v ) { int shift ; / * nzd( 0 , v ) == v ; nzd( u ,0 ) == u , nzd( 0,0 ) == * / if ( u ==return v ; if ( v ==return u ; / * Neka shift \ := lg K , gde je K najveci stepen dvojke koji deli i u i v . * / for ( shift = ( ( u | v ) &== ++shift ) { u >>= v >>= } while ( ( u &== u >>= / * Odavde pa nadalje , u je uvek neparno . * / do { / * ukloni sve faktore odiz v -- nisu zajednicki * / / * primedba : v nije nula , pa ce se while prekinuti * / while ( ( v &== / * Loop X ( petlja X ) * / v >>= / * 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 != / * vrati zajednicke faktore od * / return u << shift ; } Ефикасност Акхави и Вали су доказали да бинарни НЗД у просеку може бити и до ефикаснији ( у смислу броја операција над битовима ) од Еуклидовог алгоритма .. Међутим , иако овај алгоритам надмашује традиционални Еуклидов алгоритам , његово асимптотско понашање је идентично и приметно је сложенији , захваљујући доступности инструкција дељења у свим модерним микропроцесорима . Прави рачунари обрађују више од једног бита у истом тренутку , а чак и имплементације бинарног НЗД алгоритма у асемблеру морају да се такмиче са пажљиво дизајнираним колима за целобројно дељење . Кнутје пријавио побољшање од у односу на Еуклидов алгоритам , и према једном упоређивању , највеће побољшање је било , док су на неким популарним архитектурама чак и добре имплементације бинарног НЗД-а биле спорије него Еуклидов алгоритам . У принципу , користећи имплементације бинарног НЗД-а сличне горенаведеној у С-у , добитак у брзини у односу на Еуклидов алгоритам је у пракси увек мањи него у теорији . Разлог томе је што код користи велики број гранања која су зависна од података . Многе гране могу бити уклоњене рачунајући мин( a , b ) и |a-b| , користећи мешавине Булове алгебре и аритметике . Једина грана зависна од података коју ове технике не уклањају је условна петља , означена са Loop X , која може бити замењена једном операцијом над битовима која броји јединице након нуле најмање тежине и шифтовањем . У зависности од платформе , описана битовска операција може бити извршена једном хардверском инструкцијом или уз помоћ таблице . Итеративна верзија у C++ користећи бројање нула са трагом Коришћење алгоритма бројања нула са трагом може да побољша перформансе бинарног НЗД алгоритма . Случајно изабран број има експоненцијално опадајућу дистрибуцију трага нула:50 их нема,25 има једну нулу са трагом,125 има две нуле са трагом ,0625 има три нуле са трагом ... Итерације се чувају само ако постоје две или више нула са трагом , тако да очекивани број итерација није велики . Иако постоје ситуације где нуле са трагом много ураде у једном кораку , велика побољшања се не би могла очекивати , осим ако би бројеви имали неуобичајене особине . / / ctz( x ) broji nule sa tragom u x unsigned int nzd( unsigned int x , unsigned int y ) { if ( x == return y ; if ( y == 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 == break ; y -= x ; } return x << cf2 ; } Историјски опис Алгоритам за рачунање најмањег заједничког делиоца два броја је први пут описан у древној Кинеској математичкој књизи Девет поглавља математичке уметности . Оригинални алгоритам је био коришћен за скраћивање разломака . Опис гласи : Ако је могуће , преполови га . У супротном , узми именилац и бројилац , одузми мањи од већег , и ради то док не постану исти . Смањуј истим бројем . Ово изгледа као обичан Еуклидов алгоритам , али двосмисленост лежи у фрази ако је могуће , преполови га . Традиционална интерпретација говори да ово ради само онда када су оба броја са којима се почиње парни , и под тим условом ово представља само за нијансу лошију варијанту Еуклидовог алгоритма ( због коришћења одузимања уместо дељења ) . Међутим , фраза би могла да значи да би дељењем санеки од бројева могао да постане паран , при чему би то онда био бинарни НЗД . Види још Највећи заједнички делилац Референце Спољашње везе NIST Dictionary of Algorithms and Data Structures : binary GCD algorithm Cut-the-Knot : Binary Euclid's Algorithm at cut-the-knot Analysis of the Binary Euclidean Algorithm a paper by Richard P . Brent , including a variant using left shifts " Dynamics of the Binary Euclidean Algorithm : Functional Analysis and Operators " a paper by Brigitte Vallée . Online gcd calculator( 4 methods ) Теоретско-нумерички алгоритми Чланци са примерима C кода Чланци са примерима C++ кода