Función GCD en la biblioteca C++ sans cmath

Question

Escribo una clase numérica mixta y necesito una función rápida y sencilla de 'máximo divisor común'. ¿Alguien puede darme el código o un enlace al código?

Answer 1

Tengo la tentación de votar para cerrar - parece difícil creer que una implementación sería difícil de encontrar, pero quién sabe con certeza.

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

Answer 2

Una versión recursiva rápida:

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

o la versión iterativa equivalente si está opusieron violentamente a la recursividad ^(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; 
} 

Sólo sustituto en su propio tipo de datos, comparación cero, asignación y método de módulo (si está utilizando algún tipo no básico como una clase bignum, por ejemplo).

Esta función en realidad vino de un earlier answer of mine para trabajar relaciones de aspecto integrales para tamaños de pantalla, pero la fuente original fue el algoritmo euclidiano que aprendí hace mucho tiempo, detallado here on Wikipedia si quiere saber las matemáticas detrás de él.

---

^(a) El problema con algunas soluciones recursivas es que se acercan a la respuesta tan lentamente que tienden a quedarse sin espacio de pila antes de llegar allí, por ejemplo, con la muy mal pensado (pseudo- código):

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

Encontrarás que muy caro en algo como sum (1, 1000000000) a medida que (intentar) utiliza un mil millones o menos marcos de pila. El caso de uso ideal para la recursión es algo así como una búsqueda binaria en la que se reduce el espacio de la solución a la mitad para cada iteración. El divisor común más grande también es uno en el que el espacio de solución se reduce rápidamente, por lo que los temores sobre el uso masivo de la pila son infundados allí.

Answer 3

Euclidean El algoritmo es bastante fácil de escribir en C.

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

Answer 4

La biblioteca de algoritmos libstdC++ tiene una función oculta mcd (estoy usando g ++ 4.6.3).

#include <iostream> 
#include <algorithm> 

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

que son bienvenidos :)

ACTUALIZACIÓN: Como @ chema989 señalar que, en C++ 17 hay std::gcd() polivalente con <numeric> cabecera.

Answer 5

Mis dos centavos; algoritmo de Euclides con plantilla usando XOR swap para los tipos de enteros sin signo:

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

para C++ 17 puede utilizar std::gcd se define en la cabecera <numeric>:

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