1. Fundamento matemático

El algoritmo se basa en la propiedad:

\(\text{MCD}(a, b) = \text{MCD}(b, a \bmod b)\) con \(b \neq 0\)

Al iterar la operación de módulo, el segundo argumento disminuye rápidamente hasta llegar a cero, momento en el que el primer argumento contiene el MCD.

2. Algoritmo paso a paso

1. Si b es 0, el MCD es a.
2. Calcular r = a mod b.
3. Reemplazar a por b y b por r.
4. Repetir hasta que b = 0.

3. Implementación en Python

def gcd_iterative(a: int, b: int) -> int:
    """Calcula el MCD usando el algoritmo de Euclides iterativo.
    Args:
        a (int): Primer número entero (puede ser negativo).
        b (int): Segundo número entero.
    Returns:
        int: Máximo común divisor (valor siempre positivo).
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    return a if b == 0 else gcd_recursive(b, a % b)

4. Complejidad y rendimiento

El algoritmo de Euclides tiene una complejidad O(log min(a,b)). En la práctica, el número de iteraciones rara vez supera 5 × log₁₀ n.

import timeit
# 10⁹ y 10⁹‑1 son pares difíciles para el algoritmo binario pero fáciles para Euclides
stmt = 'gcd_iterative(10**9, 10**9-1)'
print(timeit.timeit(stmt, globals=globals(), number=100_000))

5. Comparativa con el algoritmo binario (Stein)

El algoritmo binario evita la operación de módulo usando desplazamientos de bits. Es útil en entornos donde la división es costosa (por ejemplo, microcontroladores).

En la mayoría de los proyectos Python, el algoritmo de Euclides es la opción preferida por su claridad y rendimiento.

6. Buenas prácticas y optimizaciones

• Normalizar los operandos: usar abs() para evitar resultados negativos.
• Controlar la recursión: prefiera la versión iterativa en producción.
• Tipado estático opcional: anotar con def f(a: int, b: int) -> int para herramientas como mypy.
• Cacheo de resultados en casos de llamadas repetidas con los mismos pares (ej. functools.lru_cache).
• Uso de math.gcd a partir de Python 3.5, que está implementado en C y supera a cualquier versión Python pura.

from functools import lru_cache
@lru_cache(maxsize=None)
def gcd_cached(a: int, b: int) -> int:
    return gcd_iterative(a, b)

7. Casos de uso reales

El cálculo del MCD es fundamental en:

• Reducción de fracciones en sistemas de álgebra computacional.
• Algoritmos de criptografía (p. ej., generación de claves RSA, donde se necesita un coprimo).
• Resolución de ecuaciones diofánticas.
• Compresión de datos mediante factorización de tasas de muestreo.

8. Depuración y troubleshooting

Si el algoritmo devuelve 0 o un valor inesperado, verifique:

1. Que ambos argumentos sean enteros (no flotantes).
2. Que no haya overflow en entornos con límites de entero (en Python esto no ocurre).
3. Que no se haya alcanzado el límite de recursión en la versión recursiva.

Ejemplo de manejo de errores:

def safe_gcd(a, b):
    if not isinstance(a, int) or not isinstance(b, int):
        raise TypeError('Los argumentos deben ser enteros')
    return gcd_iterative(a, b)

9. Futuras extensiones

Para proyectos que necesiten GCD múltiple (de más de dos números) basta aplicar la función de forma acumulativa:

from functools import reduce
def gcd_multiple(*numbers):
    return reduce(gcd_iterative, numbers)

En entornos de alto rendimiento, considere NumPy o Cython para procesar arrays gigantes de valores simultáneamente.