Co jest najbardziej wydajne dla GCD?

Wiem, że algorytm Euclida jest najlepszym algorytmem do uzyskania GCD (wielkiego wspólnego dzielnika) listy dodatnich liczb całkowitych. Ale w praktyce możesz kodować ten algorytm na różne sposoby. (W moim przypadku zdecydowałem się na Javę, ale C / C ++ może być inną opcją).

Potrzebuję użyć najbardziej wydajnego kodu w moim programie.

W trybie rekurencyjnym możesz pisać:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

W trybie iteracyjnym wygląda to tak:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Istnieje również algorytm binarny dla GCD, który można kodować w następujący sposób:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Twoje dwa algorytmy są równoważne (przynajmniej w przypadku liczb całkowitych dodatnich to, co dzieje się z liczbami całkowitymi ujemnymi w wersji rozkazującej, zależy od semantyki Javy, dla %której nie znam na pamięć). W wersji rekurencyjne, niech I a b I jako argument I th wywołanie rekurencyjne: i + 1 = b I b i + 1 = I m o d b I$a_i$$b_i$$i$

W wersji imperatywu, niech ' ja i b ' i być wartości zmiennych i na początku í th iteracji pętli. a ′ i + 1 = b ′ i b ′ i + 1 = a ′ i m o d b ′ i$a'_i$$b'_i$ab$i$

Czy zauważyłeś podobieństwo? Twoja wersja imperatywna i wersja rekurencyjna obliczają dokładnie te same wartości. Ponadto oba kończy w tym samym czasie, gdy i = 0 (wzgl. " I = 0 ), tak, że wykonują ten sam liczby iteracji. Algorytmicznie rzecz biorąc, nie ma między nimi żadnej różnicy. Wszelkie różnice będą zależeć od implementacji, w dużej mierze zależnej od kompilatora, sprzętu, na którym działa, a być może nawet systemu operacyjnego i innych programów działających jednocześnie.$a_i=0$$a'_i=0$

Wersja rekurencyjna wykonuje tylko połączenia rekurencyjne z tyłu . Większość kompilatorów dla języków imperatywnych nie optymalizuje ich, więc jest prawdopodobne, że generowany przez nich kod będzie marnował trochę czasu i pamięci na tworzenie ramki stosu przy każdej iteracji. Dzięki kompilatorowi, który optymalizuje wywołania ogonowe (kompilatory dla języków funkcjonalnych prawie zawsze tak robią), wygenerowany kod maszynowy może być taki sam dla obu (zakładając, że zharmonizujesz te wywołania abs).

W przypadku małych liczb wystarczający jest binarny algorytm GCD.

GMP, dobrze utrzymana i przetestowana w świecie rzeczywistym biblioteka, przejdzie do specjalnego algorytmu połowy GCD po przejściu specjalnego progu, uogólnienia algorytmu Lehmera. Lehmer używa mnożenia macierzy, aby poprawić standardowe algorytmy euklidesowe. Według dokumentów asymptotyczny czas działania zarówno HGCD, jak i GCD jest O(M(N)*log(N)), gdzie M(N)jest czas pomnożenia dwóch liczb N-kończyn.

Szczegółowe informacje na temat ich algorytmu można znaleźć tutaj .

Jak wiem, Java ogólnie nie obsługuje optymalizacji rekurencji ogona, ale możesz przetestować swoją implementację Java; jeśli to nie obsługuje, prosta forpętla powinna być szybsza, w przeciwnym razie rekurencja powinna być równie szybka. Z drugiej strony są to optymalizacje bitowe, wybierz kod, który Twoim zdaniem jest łatwiejszy i bardziej czytelny.

Powinienem również zauważyć, że najszybszym algorytmem GCD nie jest algorytm Euclida , algorytm Lehmera jest nieco szybszy.

Po pierwsze, nie używaj rekurencyjności do zamiany ciasnej pętli. To jest wolne. Nie polegaj na kompilatorze, aby go zoptymalizować. Po drugie, w kodzie wywołujesz Math.abs () w ramach wszystkich wywołań rekurencyjnych, co jest bezużyteczne.

W swojej pętli możesz łatwo uniknąć zmiennych tymczasowych i zamiany aib przez cały czas.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Zamiana za pomocą a ^ = b ^ = a ^ = b powoduje, że źródło jest krótsze, ale jego wykonanie wymaga wielu instrukcji. Będzie wolniejszy niż nudna zamiana z tymczasową zmienną.

W przypadku małych liczb % jest dość kosztowną operacją, być może prostszą rekurencyjną

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

jest szybszy? (Przepraszamy, kod Mathematica, a nie C ++)

Algorytm Euclid jest najbardziej wydajny do obliczania GCD:

Statyczny długi gcd (długi a, długi b)
{
jeśli (b == 0)
zwrócić a;
jeszcze
zwraca gcd (, a% b);
}

przykład:-

Niech A = 16, B = 10.
GCD (16, 10) = GCD (10, 16% 10) = GCD (10, 6)
GCD (10, 6) = GCD (6, 10% 6) = GCD (6, 4)
GCD (6, 4) = GCD (4, 6% 4) = GCD (4, 2)
GCD (4, 2) = GCD (2, 4% 2) = GCD (2, 0)


Ponieważ B = 0, więc GCD (2, 0) zwróci 2.