Co jest najbardziej wydajne dla GCD?

26

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;
}
jonaprieto
źródło
3
Myślę, że jest to zbyt subiektywne, a może nawet lepiej nadaje się do StackOverflow. „Najbardziej wydajny w praktyce” zależy od wielu (nawet nieprzewidywalnych) czynników, takich jak podstawowa architektura, hierarchia pamięci, wielkość i forma danych wejściowych itp.
Juho
5
Jest to ten sam algorytm wyrażony w sposób rekurencyjny i iteracyjny. Myślę, że ich różnica jest znikoma, ponieważ algorytm Euclid zbiega się dość szybko. Wybierz taki, który pasuje do twoich preferencji.
pad
6
Możesz spróbować profilować te dwa. Ponieważ wersja rekurencyjna jest wywołaniem ogonowym, nie jest wykluczone, że kompilator faktycznie emituje prawie ten sam kod.
Louis
1
To jest źle. powinno być, gdy b! = 0, a następnie zwrócić a. W przeciwnym razie powoduje błąd przy dzieleniu przez zero. także nie używaj rekurencji, jeśli masz naprawdę duże gcds .... dostajesz stos stanów i funkcji ... dlaczego po prostu nie iterować?
Cris Stringfellow
4
Zauważ, że istnieją asymptotycznie szybsze algorytmy GCD. Np. En.wikipedia.org/wiki/Binary_GCD_alameterm
Neal Young

Odpowiedzi:

21

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 Izajabjaja

zaja+1=bjabja+1=zajamorebja

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 izajabjaabja

zaja+1=bjabja+1=zajamorebja

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.zaja=0zaja=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).

Gilles „SO- przestań być zły”
źródło
8

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 .

qwr
źródło
Link naprawdę nie podaje pełnych szczegółów, a nawet nie określa, czym jest „kończyna” ...
einpoklum - przywraca Monikę
2

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.

PJTraill
źródło
Masz na myśli o ile mi wiadomo ? Czy masz na myśli, że specyfikacja języka nie nakazuje tej optymalizacji (byłoby zaskakujące, gdyby tak zrobiła), lub że większość implementacji jej nie implementuje?
PJTraill,
1

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ą.

Florian F.
źródło
3
„Unikaj rekurencyjności. Jest powolny ”- przedstawiony jako ogólna rada, to nieprawda. To zależy od kompilatora. Zwykle nawet w przypadku kompilatorów, które nie optymalizują rekurencji, nie jest to powolne, a jedynie zajmuje dużo miejsca.
Gilles 'SO - przestań być zły'
3
Ale w przypadku takiego krótkiego kodu różnica jest znacząca. Zużycie w stosie oznacza pisanie do i czytanie z pamięci. To jest powolne. Powyższy kod działa na 2 rejestrach. Rekurencyjność oznacza także wykonywanie połączeń, które są dłuższe niż skok warunkowy. Wywołanie rekurencyjne jest znacznie trudniejsze dla przewidywania gałęzi i trudniejsze do wstawienia.
Florian F
-2

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 ++)

Per Alexandersson
źródło
To nie wygląda dobrze. Dla b == 1 powinien zwrócić 1. A GCD [2 1000000000] będzie wolny.
Florian F
Ach, tak, popełniłem błąd. Naprawiono (tak myślę) i wyjaśniono.
Per Alexandersson,
Zwykle GCD [a, 0] powinien również zwrócić a. Twoje pętle na zawsze.
Florian F
Oddaję głos, ponieważ twoja odpowiedź zawiera tylko kod. Lubimy koncentrować się na pomysłach na tej stronie. Na przykład dlaczego% jest kosztowną operacją? Spekulacje na temat fragmentu kodu nie są, moim zdaniem, dobrą odpowiedzią na tę stronę.
Juho
1
Myślę, że pomysł, że modulo jest wolniejszy niż odejmowanie, można uznać za folklor. Dotyczy to zarówno małych liczb całkowitych (odejmowanie zwykle zajmuje jeden cykl, modulo rzadko), jak i dużych liczb całkowitych (odejmowanie jest liniowe, nie jestem pewien, jaka jest najlepsza złożoność dla modulo, ale jest zdecydowanie gorsza). Oczywiście należy również wziąć pod uwagę liczbę niezbędnych iteracji.
Gilles 'SO - przestań być zły'
-2

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. 
Rohit-Pandey
źródło
4
To nie odpowiada na pytanie. Pytający przedstawia dwie wersje Euclida i pyta, co jest szybsze. Wydaje się, że tego nie zauważyłeś i po prostu deklarujesz, że wersja rekurencyjna jest jedynym algorytmem Euclida, i bez żadnego dowodu, że jest szybsza niż wszystko inne.
David Richerby