El algoritmo binario GCD , también conocido como algoritmo de Stein o el algoritmo binario euclidiano , [1] [2] es un algoritmo que calcula el máximo común divisor de dos enteros no negativos. El algoritmo de Stein usa operaciones aritméticas más simples que el algoritmo euclidiano convencional ; reemplaza la división con cambios aritméticos , comparaciones y restas.
Aunque el algoritmo en su forma contemporánea fue publicado por primera vez por el físico y programador israelí Josef Stein en 1967, [3] puede haber sido conocido en el siglo II a. C., en la antigua China. [4] [5]
Algoritmo
El algoritmo reduce el problema de encontrar el MCD de dos números no negativos v y u aplicando repetidamente estas identidades:
- mcd (0, v ) = v , porque todo divide a cero y v es el número más grande que divide a v . De manera similar, mcd ( u , 0) = u .
- mcd ( 2u , 2v ) = 2 · mcd ( u , v )
- mcd ( 2u , v ) = mcd ( u , v ), si v es impar (2 no es un divisor común). De manera similar, mcd ( u , 2v ) = mcd ( u , v ) si u es impar.
- mcd ( u , v ) = mcd (| u - v |, min ( u , v )), si tanto u como v son impares.
Implementación
Versión recursiva en C
Lo que sigue es un recursivo implementación del algoritmo en C . La implementación es similar a la descripción del algoritmo dada anteriormente y está optimizada para la legibilidad en lugar de la velocidad, aunque todas las llamadas recursivas menos una son recursivas de cola .
unsigned int gcd ( unsigned int u , unsigned int v ) { // Casos base // gcd (n, n) = n if ( u == v ) return u ; // Identidad 1: gcd (0, n) = gcd (n, 0) = n if ( u == 0 ) return v ; si ( v == 0 ) devuelve u ; if ( u & 1 ) { // u es impar if ( v % 2 == 0 ) // v es par return gcd ( u , v / 2 ); // Identidad 3 // Identidades 4 y 3 (uyv son impares, por lo que se sabe que uv y vu son pares) if ( u > v ) return gcd (( u - v ) / 2 , v ); de lo contrario, devuelve mcd (( v - u ) / 2 , u ); } else { // u es par si ( v & 1 ) // v es impar return gcd ( u / 2 , v ); // Identidad 3 else // tanto u como v son pares return 2 * gcd ( u / 2 , v / 2 ); // Identidad 2 } }
Versión iterativa en Rust
A continuación se muestra una implementación del algoritmo en Rust , adaptado de uutils . Elimina todos los factores comunes de 2, usando la identidad 2, luego calcula el MCD de los números restantes usando las identidades 3 y 4, combinándolos para formar la respuesta final.
pub fn gcd ( mut u : u64 , mut v : u64 ) -> u64 { use std :: cmp :: min ; use std :: mem :: swap ; // Casos base: mcd (n, 0) = mcd (0, n) = n if u == 0 { return v ; } más si v == 0 { return u ; } // Usando las identidades 2 y 3: // mcd (2ⁱ u, 2ʲ v) = 2ᵏ mcd (u, v) con u, v impar y k = min (i, j) // 2ᵏ es la mayor potencia de dos que divide tanto a u como a v, sea i = u . trailing_zeros (); u >> = yo ; sea j = v . trailing_zeros (); v >> = j ; sea k = min ( i , j ); bucle { // ¡uyv son impares al comienzo del ciclo debug_assert! ( u % 2 == 1 , "u = {} es par" , u ); debug_assert! ( v % 2 == 1 , "v = {} es par" , v ); // Intercambiar si es necesario para que u <= v if u > v { intercambiar ( & mut u , & mut v ); } // Usando la identidad 4 (mcd (u, v) = mcd (| vu |, min (u, v)) v - = u ; // Identidad 1: gcd (u, 0) = u // El cambio de k es necesario para volver a sumar el factor 2ᵏ que se eliminó antes del ciclo si v == 0 { return u << k ; } // Identidad 3: mcd (u, 2ʲ v) = mcd (u, v) (se sabe que u es impar) v >> = v . trailing_zeros (); }}
Esta implementación muestra varias optimizaciones de rendimiento:
- La división de prueba por 2 se evita en favor de un desplazamiento de bits único y la primitiva de recuento de ceros finales u64 :: trailing_zeros . Esto realiza el equivalente a aplicar repetidamente la identidad 3, en una cantidad de tiempo mucho menor.
- El bucle está diseñado para evitar trabajos repetidos; por ejemplo, la eliminación de 2 como factor de v se movió a la parte posterior del bucle, y después de la condición de salida, ya que se sabe que v es impar al ingresar al bucle.
- El cuerpo del bucle no tiene ramificaciones excepto por su condición de salida ( v == 0 ), ya que el intercambio de u y v (asegurando que u ≤ v ) se compila en movimientos condicionales . [6] Las ramas difíciles de predecir pueden tener un gran impacto negativo en el rendimiento. [7] [8]
Eficiencia
El algoritmo requiere O ( n ) pasos, donde n es el número de bits en el mayor de los dos números, ya que cada 2 pasos reduce al menos uno de los operandos en al menos un factor de 2. Cada paso implica solo unas pocas operaciones aritméticas. operaciones (O (1) con una pequeña constante); cuando se trabaja con números del tamaño de una palabra , cada operación aritmética se traduce en una sola operación de máquina, por lo que el número de operaciones de la máquina está en el orden de log (max ( u , v )).
Sin embargo, la complejidad asintótica de este algoritmo es O (n 2 ), [9] ya que esas operaciones aritméticas (restar y desplazar) toman tiempo lineal para números de tamaño arbitrario (una operación de máquina por palabra de la representación). Esto es lo mismo que para el algoritmo euclidiano, aunque un análisis más preciso de Akhavi y Vallée demostró que el GCD binario usa aproximadamente un 60% menos de operaciones de bits. [10]
Extensiones
El algoritmo binario de GCD se puede ampliar de varias formas, ya sea para generar información adicional, tratar con números enteros arbitrariamente grandes de manera más eficiente o para calcular GCD en dominios distintos de los enteros.
El extendida binario GCD algoritmo, análogo al algoritmo de Euclides extendido , se ajusta en el primer tipo de extensión, ya que proporciona los coeficientes de Bézout además de la GCD, es decir, números enteros una y b tales que a · u + b · v = gcd ( u , v ). [11] [12] [13]
En el caso de números enteros grandes, la mejor complejidad asintótica es O (log n M ( n )), siendo M ( n ) el costo de la multiplicación de n bits; esto es casi lineal y mucho más pequeño que el O (n 2 ) del algoritmo binario GCD, aunque las implementaciones concretas solo superan a los algoritmos más antiguos para números mayores de aproximadamente 64 kilobits ( es decir, mayores de 8 × 10 19265 ). Esto se logra extendiendo el algoritmo binario GCD usando ideas del algoritmo de Schönhage-Strassen para la multiplicación rápida de enteros. [14]
El algoritmo binario GCD también se ha extendido a dominios distintos de los números naturales, como los enteros gaussianos , [15] los enteros de Eisenstein , [16] anillos cuadráticos, [17] [18] y dominios de factorización únicos arbitrarios . [19]
Descripción histórica
En la antigua China, bajo la dinastía Han , se conocía un algoritmo para calcular el GCD de dos números como método para reducir fracciones:
Si es posible, córtelo por la mitad; de lo contrario, tome el denominador y el numerador, reste el menor del mayor y hágalo alternativamente para que sean iguales. Reducir por el mismo número.
- Fangtian - Agrimensura, los nueve capítulos sobre el arte matemático
La frase "si es posible, reducir a la mitad" es ambigua, [4] [5]
- si esto se aplica cuando cualquiera de los números se vuelve par, el algoritmo es el algoritmo binario GCD;
- si esto solo se aplica cuando ambos números son pares, el algoritmo es similar al algoritmo euclidiano .
Ver también
Referencias
- ^ Brent, Richard P. (13 a 15 de septiembre de 1999). Veinte años de análisis del algoritmo binario euclidiano . 1999 Simposio Oxford-Microsoft en honor al profesor Sir Antony Hoare. Oxford.
- ^ Brent, Richard P. (noviembre de 1999). Análisis adicional del algoritmo binario euclidiano (Informe técnico). Laboratorio de Computación de la Universidad de Oxford. arXiv : 1303.2772 . PRG TR-7-99.
- ^ Stein, J. (febrero de 1967), "Problemas computacionales asociados con el álgebra de Racah", Journal of Computational Physics , 1 (3): 397–405, Bibcode : 1967JCoPh ... 1..397S , doi : 10.1016 / 0021-9991 (67) 90047-2 , ISSN 0021-9991
- ^ a b Knuth, Donald (1998), Algoritmos seminuméricos , El arte de la programación informática , 2 (3a ed.), Addison-Wesley, ISBN 978-0-201-89684-8
- ^ a b Zhang, Shaohua (5 de octubre de 2009). "El concepto de números primos y el algoritmo para contar el máximo común divisor en la antigua China". arXiv : 0910.0095 [ math.HO ].
- ^ Godbolt, Matt. "Explorador del compilador" . Consultado el 4 de noviembre de 2020 .
- ^ Kapoor, Rajiv (21 de febrero de 2009). "Evitar el costo de la predicción errónea de la rama" . Zona de desarrolladores Intel .
- ^ Lemire, Daniel (15 de octubre de 2019). "Las ramas mal pronosticadas pueden multiplicar sus tiempos de ejecución" .
- ^ "GNU MP 6.1.2: GCD binario" .
- ^ Akhavi, Ali; Vallée, Brigitte (2000), "Promedio de complejidad de bits de los algoritmos euclidianos" , Actas ICALP'00, Lecture Notes Computer Science 1853 : 373–387, CiteSeerX 10.1.1.42.7616
- ^ Knuth 1998 , p. 646, respuesta al ejercicio 39 del apartado 4.5.2
- ^ Menezes, Alfred J .; van Oorschot, Paul C .; Vanstone, Scott A. (octubre de 1996). "§14.4 Mayores algoritmos de divisor común" (PDF) . Manual de criptografía aplicada . Prensa CRC. págs. 606–610. ISBN 0-8493-8523-7. Consultado el 9 de septiembre de 2017 .
- ^ Cohen, Henri (1993). "Capítulo 1: Algoritmos fundamentales de teoría de números". Un curso de teoría de números algebraicos computacionales . Textos de Posgrado en Matemáticas . 138 . Springer-Verlag . págs. 17-18. ISBN 0-387-55640-0.
- ^ Stehlé, Damien; Zimmermann, Paul (2004), "Un algoritmo gcd recursivo binario" (PDF) , Teoría algorítmica de números , Lecture Notes in Comput. Sci., 3076 , Springer, Berlín, págs. 411–425, CiteSeerX 10.1.1.107.8612 , doi : 10.1007 / 978-3-540-24847-7_31 , ISBN 978-3-540-22156-2, MR 2138011 , Informe de investigación de INRIA RR-5050.
- ^ Weilert, André (julio de 2000). "Cálculo GCD (1 + i) -ary en Z [i] como un análogo al algoritmo GCD binario". Revista de Computación Simbólica . 30 (5): 605–617. doi : 10.1006 / jsco.2000.0422 .
- ^ Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (12 al 15 de agosto de 2003). Algoritmos eficientes para GCD y residuo cúbico en el anillo de enteros de Eisenstein . XIV Simposio Internacional sobre los Fundamentos de la Teoría de la Computación. Malmö , Suecia . págs. 109-117. doi : 10.1007 / 978-3-540-45077-1_11 .Mantenimiento CS1: formato de fecha ( enlace )
- ^ Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (13 al 18 de junio de 2004). Algoritmos binarios tipo GCD para algunos anillos cuadráticos complejos . Simposio de teoría algorítmica de números. Burlington, VT , Estados Unidos. págs. 57–71. doi : 10.1007 / 978-3-540-24847-7_4 .Mantenimiento CS1: formato de fecha ( enlace )
- ^ Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (20 al 24 de marzo de 2006). Un nuevo algoritmo GCD para anillos numéricos cuadráticos con factorización única . VII Simposio Latinoamericano de Informática Teórica. Valdivia, Chile . págs. 30–42. doi : 10.1007 / 11682462_8 .Mantenimiento CS1: formato de fecha ( enlace )
- ^ Wikström, Douglas (11 al 15 de julio de 2005). Sobre el algoritmo l-Ary GCD en anillos de enteros . Autómatas, Lenguajes y Programación, 32º Coloquio Internacional. Lisboa , Portugal . págs. 1189–1201. doi : 10.1007 / 11523468_96 .Mantenimiento CS1: formato de fecha ( enlace )
Otras lecturas
- Knuth, Donald (1998). "§4.5 Aritmética racional". Algoritmos seminuméricos . El arte de la programación informática . 2 (3ª ed.). Addison-Wesley. págs. 330–417. ISBN 978-0-201-89684-8.
Cubre el GCD binario extendido y un análisis probabilístico del algoritmo.
- Cohen, Henri (1993). "Capítulo 1: Algoritmos fundamentales de teoría de números". Un curso de teoría de números algebraicos computacionales . Textos de Posgrado en Matemáticas . 138 . Springer-Verlag . págs. 12-24. ISBN 0-387-55640-0.
Cubre una variedad de temas, incluido el algoritmo GCD binario extendido que genera coeficientes de Bézout , el manejo eficiente de enteros de precisión múltiple utilizando una variante del algoritmo GCD de Lehmer y la relación entre GCD y expansiones de fracciones continuas de números reales.
- Vallée, Brigitte (septiembre-octubre de 1998). "Dinámica del algoritmo binario euclidiano: análisis funcionales y operadores" . Algoritmica . 22 (4): 660–685. doi : 10.1007 / PL00009246 . S2CID 27441335 . Archivado desde el original (PS) el 13 de mayo de 2011.Mantenimiento CS1: formato de fecha ( enlace )
Un análisis del algoritmo en el caso promedio, a través de la lente del análisis funcional : los parámetros principales de los algoritmos se proyectan como un sistema dinámico , y su valor promedio está relacionado con la medida invariante del operador de transferencia del sistema .
enlaces externos
- Diccionario NIST de algoritmos y estructuras de datos: algoritmo binario GCD
- Cortar el nudo: algoritmo binario de Euclides al cortar el nudo
- Análisis del algoritmo binario euclidiano (1976), un artículo de Richard P. Brent , que incluye una variante que usa desplazamientos a la izquierda