Algoritmo de Euclides para el máximo común divisor

Dados dos enteros no negativos $a$ y $b$ , hay que encontrar su GCD (greatest common divisor / máximo común divisor), es decir, el mayor número que es divisor de $a$ y de $b$ . Se denota habitualmente $\gcd(a, b)$ . Matemáticamente se define como:

$\gcd(a, b) = \max {k > 0 : (k \mid a) \text{ and } (k \mid b) }$

(acá el símbolo ” $\mid$ ” denota divisibilidad, es decir, “ $k \mid a$ ” significa “ $k$ divide a $a$ ”)

Cuando uno de los números es cero y el otro no, su máximo común divisor, por definición, es el segundo número. Cuando ambos números son cero, su máximo común divisor está indefinido (puede ser un número arbitrariamente grande), pero conviene definirlo también como cero para preservar la asociatividad de $\gcd$ . Eso da una regla simple: si uno de los números es cero, el máximo común divisor es el otro número.

El algoritmo de Euclides, que se discute más abajo, permite encontrar el máximo común divisor de dos números $a$ y $b$ en $O(\log \min(a, b))$ . Como la función es asociativa, para encontrar el GCD de más de dos números podemos hacer $\gcd(a, b, c) = \gcd(a, \gcd(b, c))$ y así sucesivamente.

El algoritmo se describió por primera vez en los “Elementos” de Euclides (alrededor del 300 a. C.), pero es posible que tenga orígenes aún anteriores.

Algoritmo

Originalmente, el algoritmo de Euclides se formulaba así: restar el número más chico del más grande hasta que uno de los números sea cero. En efecto, si $g$ divide a $a$ y a $b$ , también divide a $a-b$ . Por otro lado, si $g$ divide a $a-b$ y a $b$ , entonces también divide a $a = b + (a-b)$ , lo que significa que los conjuntos de divisores comunes de ${a, b}$ y de ${b,a-b}$ coinciden.

Nótese que $a$ sigue siendo el número más grande hasta que se le reste $b$ al menos $\left\lfloor\frac{a}{b}\right\rfloor$ veces. Por lo tanto, para acelerar, se sustituye $a-b$ por $a-\left\lfloor\frac{a}{b}\right\rfloor b = a \bmod b$ . Entonces el algoritmo se formula de forma extremadamente simple:

$\gcd(a, b) =$

Implementación


int gcd (int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}

Usando el operador ternario en C++, se puede escribir en una sola línea.


int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

Y por último, acá hay una implementación no recursiva:


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

Nótese que desde C++17, gcd está implementado como una función estándar en C++.

Complejidad temporal

El tiempo de ejecución del algoritmo se estima con el teorema de Lamé, que establece una conexión sorprendente entre el algoritmo de Euclides y la sucesión de Fibonacci:

Si $a > b \geq 1$ y $b < F_n$ para algún $n$ , el algoritmo de Euclides realiza a lo sumo $n-2$ llamadas recursivas.

Además, se puede mostrar que la cota superior de este teorema es óptima. Cuando $a = F_n$ y $b = F_{n-1}$ , $gcd(a, b)$ realiza exactamente $n-2$ llamadas recursivas. En otras palabras, los números de Fibonacci consecutivos son la entrada de peor caso para el algoritmo de Euclides.

Dado que los números de Fibonacci crecen de forma exponencial, obtenemos que el algoritmo de Euclides trabaja en $O(\log \min(a, b))$ .

Otra forma de estimar la complejidad es notar que $a \bmod b$ para el caso $a \geq b$ es al menos $2$ veces más chico que $a$ , así que el número más grande se reduce al menos a la mitad en cada iteración del algoritmo. Aplicando este razonamiento al caso en que calculamos el GCD del conjunto de números $a_1,\dots,a_n \leq C$ , esto también nos permite estimar el tiempo total como $O(n + \log C)$ , en lugar de $O(n \log C)$ , porque cada iteración no trivial del algoritmo reduce el candidato actual a GCD al menos por un factor de $2$ .

Mínimo común múltiplo

Calcular el mínimo común múltiplo (habitualmente denotado LCM) se reduce a calcular el GCD con la siguiente fórmula simple:

$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$

Así, el LCM se puede calcular usando el algoritmo de Euclides con la misma complejidad temporal:

Una implementación posible, que evita inteligentemente los desbordamientos enteros dividiendo primero $a$ por el GCD, se da acá:


int lcm (int a, int b) {
    return a / gcd(a, b) * b;
}

GCD binario

El algoritmo Binary GCD es una optimización del algoritmo de Euclides normal.

La parte lenta del algoritmo normal son las operaciones de módulo. Las operaciones de módulo, aunque las vemos como $O(1)$ , son mucho más lentas que operaciones más simples como suma, resta u operaciones de bits. Así que sería mejor evitarlas.

Resulta que se puede diseñar un algoritmo rápido de GCD que evita las operaciones de módulo. Se basa en unas pocas propiedades:

Si ambos números son pares, podemos factorizar un dos de ambos y calcular el GCD de los números restantes: $\gcd(2a, 2b) = 2 \gcd(a, b)$ .
Si uno de los números es par y el otro es impar, podemos quitar el factor 2 del par: $\gcd(2a, b) = \gcd(a, b)$ si $b$ es impar.
Si ambos números son impares, restar uno del otro no cambia el GCD: $\gcd(a, b) = \gcd(b, a-b)$

Usando solo estas propiedades, y algunas funciones de bits rápidas de GCC, podemos implementar una versión rápida:


int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

Nótese que esa optimización normalmente no es necesaria, y la mayoría de los lenguajes de programación ya tienen una función GCD en sus bibliotecas estándar. Por ejemplo, C++17 tiene la función std::gcd en el header numeric.