Euclidean GCD

Categoría: Math

El problema

Encontrar el máximo común divisor (GCD) de dos enteros no negativos — el entero más grande que divide a ambos sin dejar resto. El enfoque directo — contar hacia atrás desde el número más pequeño, probando cada candidato — es O(min(a, b)). Para dos números grandes que resultan ser coprimos (su único divisor común es 1), ese recorrido tiene que llegar hasta 1 sin nada que mostrar antes de eso.

La solución

Una sola identidad sostiene todo el algoritmo: gcd(a, b) = gcd(b, a mod b). Reemplazar repetidamente el par (a, b) por (b, a mod b) reduce los números rápidamente — al menos tan rápido como crece la secuencia de Fibonacci, que es el propio peor caso clásico del algoritmo (dos números de Fibonacci consecutivos fuerzan la cantidad máxima posible de pasos para números de ese tamaño). Incluso ese peor caso es de solo O(log(min(a, b))) pasos — muy lejos del recorrido lineal que reemplaza.

flowchart LR
    A["gcd(48, 18)"] --> B["gcd(18, 48 mod 18 = 12)"]
    B --> C["gcd(12, 18 mod 12 = 6)"]
    C --> D["gcd(6, 12 mod 6 = 0)"]
    D --> E["6"]

Ejemplo clásico

classic/EuclideanGcd implementa el algoritmo iterativo basado en módulo, un lcm construido directamente sobre él (lcm(a, b) = (a / gcd(a, b)) * b), y bruteForceGcd, incluido específicamente para el benchmark a continuación. EuclideanGcdTest cubre un par ordinario, las identidades con argumento cero, un número contra sí mismo, un par coprimo, y — un guiño deliberado al propio peor caso clásico del algoritmo — un par de números de Fibonacci consecutivos, además de confirmar que la fuerza bruta coincide con Euclides en todos los casos probados.

Ejemplo aplicado: proporción de split payment en marketplace vía PIX

applied/PaymentSplitReducer reduce una regla de split payment de marketplace vía PIX a su mínima expresión — una plataforma que retiene 3,000 unidades base y un vendedor que recibe 7,000 de un total de 10,000 se reduce a la proporción canónica 3:7, que es exactamente el tipo de representación auditable y mínima que un motor de reglas de liquidación quiere almacenar, en lugar de los números originales (equivalentes, pero innecesariamente grandes). PaymentSplitReducerTest cubre un split reducible, un split que ya está en su mínima expresión, y la protección contra participaciones no positivas.

Benchmark

./gradlew :math:euclidean-gcd:jmh

Ejecución real en esta máquina (JMH 1.37, JDK 26.0.2, 2 iteraciones de calentamiento + 3 de medición, 1 fork). Ambos métodos se ejecutan contra pares de enteros consecutivos (n, n-1) — siempre coprimos, por lo que su GCD verdadero es siempre 1. Ese es el peor caso del recorrido de fuerza bruta (nunca encuentra un divisor común antes de tiempo, así que siempre recorre todo hasta el final) y está cerca del mejor caso de Euclides (n mod (n-1) es siempre 1, resolviéndose en esencialmente dos pasos sin importar n):

Euclides se mantiene completamente estable a lo largo de cuatro órdenes de magnitud de n — realmente realiza las mismas dos operaciones de módulo sin importar cuán grandes sean los números. La fuerza bruta sigue su predicción de O(n) casi con exactitud: un aumento de 100x en n produjo un aumento de 100.1x en el costo (100 → 10,000), y un aumento de 89.6x en el siguiente paso de 100x (10,000 → 1,000,000). En n=1,000,000, la fuerza bruta es ~448,971x más lenta que Euclides para la misma respuesta.

Cuándo no usarlo

• ¿Ya tiene las factorizaciones primas de ambos números disponibles por otro motivo? Multiplicar directamente los factores primos compartidos puede ser más simple — el algoritmo de Euclides se justifica específicamente porque encuentra el GCD sin factorizar ninguno de los números.
• ¿Necesita el GCD de más de dos números? Aplique el algoritmo de Euclides de a pares — gcd(a, b, c) = gcd(gcd(a, b), c) — en lugar de recurrir a una técnica diferente; la identidad se generaliza de forma directa.
• ¿Necesita no solo el GCD, sino también los coeficientes enteros x, y tales que ax + by = gcd(a, b) (necesarios para inversos modulares, entre otras cosas)? Ese es el algoritmo de Euclides extendido — una extensión directa de este, no implementada por separado aquí.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de branches (JaCoCo). Reprodúzcalo usted mismo:

./gradlew :math:euclidean-gcd:jacocoTestReport

Informe en math/euclidean-gcd/build/reports/jacoco/test/html/index.html.

Lectura complementaria

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3.ª/4.ª ed., Capítulo 31.2, "Greatest common divisor" — demuestra la cota O(log(min(a, b))) mediante el argumento de peor caso de Fibonacci que el propio test de este módulo cita directamente.
• Knuth — The Art of Computer Programming, Volume 2, Seminumerical Algorithms — la Sección 4.5.2 es el tratamiento clásico y profundo del algoritmo de Euclides, incluyendo sus orígenes históricos como (muy probablemente) el algoritmo no trivial más antiguo todavía en uso común.

Pruebas unitarias

package com.algorithms.math.euclideangcd.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class EuclideanGcdTest {

    @Test
    void computesTheGcdOfTwoOrdinaryNumbers() {
        assertThat(EuclideanGcd.gcd(48, 18)).isEqualTo(6);
    }

    @Test
    void gcdWithZeroReturnsTheOtherNumber() {
        assertThat(EuclideanGcd.gcd(0, 5)).isEqualTo(5);
        assertThat(EuclideanGcd.gcd(5, 0)).isEqualTo(5);
    }

    @Test
    void gcdOfANumberWithItselfIsItself() {
        assertThat(EuclideanGcd.gcd(42, 42)).isEqualTo(42);
    }

    @Test
    void coprimeNumbersHaveGcdOne() {
        assertThat(EuclideanGcd.gcd(17, 13)).isEqualTo(1);
    }

    @Test
    void handlesConsecutiveFibonacciNumbersTheAlgorithmsOwnWorstCase() {
        // Consecutive Fibonacci numbers force the maximum number of steps for a given magnitude.
        assertThat(EuclideanGcd.gcd(89, 55)).isEqualTo(1);
    }

    @Test
    void computesTheLcmOfTwoOrdinaryNumbers() {
        assertThat(EuclideanGcd.lcm(4, 6)).isEqualTo(12);
    }

    @Test
    void lcmWithZeroIsZero() {
        assertThat(EuclideanGcd.lcm(0, 5)).isZero();
        assertThat(EuclideanGcd.lcm(5, 0)).isZero();
    }

    @Test
    void bruteForceAgreesWithEuclidOnEveryCase() {
        assertThat(EuclideanGcd.bruteForceGcd(48, 18)).isEqualTo(EuclideanGcd.gcd(48, 18));
        assertThat(EuclideanGcd.bruteForceGcd(0, 5)).isEqualTo(EuclideanGcd.gcd(0, 5));
        assertThat(EuclideanGcd.bruteForceGcd(5, 0)).isEqualTo(EuclideanGcd.gcd(5, 0));
        assertThat(EuclideanGcd.bruteForceGcd(17, 13)).isEqualTo(EuclideanGcd.gcd(17, 13));
    }

    @Test
    void rejectsNegativeInputs() {
        assertThatThrownBy(() -> EuclideanGcd.gcd(-1, 5)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> EuclideanGcd.gcd(5, -1)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> EuclideanGcd.bruteForceGcd(-1, 5)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> EuclideanGcd.lcm(-1, 5)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsBothInputsBeingZero() {
        assertThatThrownBy(() -> EuclideanGcd.gcd(0, 0)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> EuclideanGcd.bruteForceGcd(0, 0)).isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.math.euclideangcd.applied;

import com.algorithms.math.euclideangcd.applied.PaymentSplitReducer.SplitRatio;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class PaymentSplitReducerTest {

    private final PaymentSplitReducer reducer = new PaymentSplitReducer();

    @Test
    void reducesAMarketplaceSplitToItsLowestTerms() {
        assertThat(reducer.reduceToLowestTerms(3_000, 7_000)).isEqualTo(new SplitRatio(3, 7));
    }

    @Test
    void anAlreadyReducedRatioIsUnchanged() {
        assertThat(reducer.reduceToLowestTerms(1, 4)).isEqualTo(new SplitRatio(1, 4));
    }

    @Test
    void rejectsNonPositiveShares() {
        assertThatThrownBy(() -> reducer.reduceToLowestTerms(0, 5)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> reducer.reduceToLowestTerms(5, 0)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> reducer.reduceToLowestTerms(-1, 5)).isInstanceOf(IllegalArgumentException.class);
    }
}

Ver informe completo de cobertura JaCoCo →