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;
}
algorithms
recursion
arithmetic
jonaprieto
źródło
źródło
Odpowiedzi:
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, dlazaja bja ja
%
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 IW 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 ′ iza′ja b′ja ja
a
b
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= 0 za′ja= 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
).źródło
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))
, gdzieM(N)
jest czas pomnożenia dwóch liczb N-kończyn.Szczegółowe informacje na temat ich algorytmu można znaleźć tutaj .
źródło
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
for
pę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.
źródło
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.
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ą.
źródło
W przypadku małych liczb % jest dość kosztowną operacją, być może prostszą rekurencyjną
jest szybszy? (Przepraszamy, kod Mathematica, a nie C ++)
źródło
Algorytm Euclid jest najbardziej wydajny do obliczania GCD:
przykład:-
źródło