Funkcja GCD w bibliotece C++ sans cmath

Question

Piszę mieszaną klasę liczbową i potrzebuję szybkiej i łatwej funkcji "największego wspólnego dzielnika". Czy ktoś może mi podać kod lub link do kodu?

Answer 1

Kusi mnie, abym zagłosował, aby zamknąć - wydaje się, że trudno uwierzyć, że trudno byłoby znaleźć wdrożenie, ale kto wie na pewno.

unsigned GCD(unsigned u, unsigned v) { 
    while (v != 0) { 
     unsigned r = u % v; 
     u = v; 
     v = r; 
    } 
    return u; 
} 

Answer 2

Szybkie wersja rekurencyjna:

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2); 
} 

lub równowartość wersja iteracyjna jeśli gwałtownie sprzeciwia się rekursji ^(a):

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    unsigned int tmp; 
    while (n2 != 0) { 
     tmp = n1; 
     n1 = n2; 
     n2 = tmp % n2; 
    } 
    return n1; 
} 

tylko substytutem w swoim własnym typ danych, porównanie zerowe, przypisanie i metoda modulacji (jeśli używasz jakiegoś typu innego niż podstawowy, na przykład klasy bignum).

Ta funkcja faktycznie pochodzi z earlier answer of mine dla opracowania integralnych współczynników proporcji dla rozmiarów ekranu, ale pierwotnym źródłem był algorytm Euklidesa, którego nauczyłem się dawno temu, szczegółowy here on Wikipedia, jeśli chcesz poznać matematykę za nim.

---

^(a) Problem z niektórymi rekurencyjnych rozwiązań jest to, że zbliżają się odpowiedź tak wolno, masz tendencję do zabrakło miejsca stosu zanim się tam dostać, jak się bardzo źle przemyślane (pseudo- kod):

def sum (a:unsigned, b:unsigned): 
    if b == 0: return a 
    return sum (a + 1, b - 1) 

Przekonasz się, że bardzo drogie na coś podobnego sum (1, 1000000000) jak (spróbuj) zużywają miliard albo tak układać ramek. Idealny przypadek użycia dla rekurencji jest czymś w rodzaju binarnego wyszukiwania, w którym zmniejsza się przestrzeń rozwiązania o połowę dla każdej iteracji. Największy wspólny dzielnik to także taki, w którym przestrzeń rozwiązania szybko maleje, więc obawy związane z użyciem ogromnego stosu są tam nieuzasadnione.

Answer 3

Algorytm Euclidean jest dość łatwo pisać w C

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

Answer 4

libstdC++ biblioteki algorytm posiada ukrytą funkcję GCD (używam g ++ 4.6.3).

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    cout << std::__gcd(100,24); 
    return 0; 
} 

Zapraszamy :)

UPDATE: Jak @ chema989 zauważyć go w C++ 17 jest std::gcd() funkcja dostępna <numeric> cel.

Answer 5

Moje dwa centy; Algorytm Euklidesa matrycy za pomocą XOR swap dla niepodpisanych typów całkowitych:

template <class Unsigned> 
Unsigned gcd(Unsigned a, Unsigned b) 
{ 

    static_assert(
     std::numeric_limits<Unsigned>::is_integer && 
     !std::numeric_limits<Unsigned>::is_signed, "Unsigned required."); 

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

Answer 6

dla C++ 17 można użyć std::gcd zdefiniowane w nagłówku <numeric>:

auto res = std::gcd(10, 20);