Algoritmo MCD binario

Algoritmo para calcular el máximo común divisor

Visualización del uso del algoritmo MCD binario para encontrar el máximo común divisor (MCD) de 36 y 24. Por lo tanto, el MCD es 2 ² × 3 = 12.

El algoritmo binario MCD , también conocido como algoritmo de Stein o algoritmo euclidiano binario , ^{[1] [2]} es un algoritmo que calcula el máximo común divisor (MCD) de dos números enteros no negativos. El algoritmo de Stein utiliza operaciones aritméticas más simples que el algoritmo euclidiano convencional ; reemplaza la división con desplazamientos aritméticos , comparaciones y restas.

Aunque el algoritmo en su forma contemporánea fue publicado por primera vez por el físico y programador Josef Stein en 1967, ^[3] ya era conocido en el siglo II a. C., en la antigua China. ^[4]

Algoritmo

El algoritmo encuentra el MCD de dos números no negativos y aplica repetidamente estas identidades: ${\displaystyle u}$ ${\displaystyle v}$

1. ${\displaystyle \gcd(u,0)=u}$:todo divide a cero, y es el mayor número que divide a . ${\displaystyle u}$ ${\displaystyle u}$
2. ${\displaystyle \gcd(2u,2v)=2\cdot \gcd(u,v)}$: es un divisor común. ${\displaystyle 2}$
3. ${\displaystyle \gcd(u,2v)=\gcd(u,v)}$si es impar: entonces no es un divisor común. ${\displaystyle u}$ ${\displaystyle 2}$
4. ${\displaystyle \gcd(u,v)=\gcd(u,v-u)}$si es impar y . ${\displaystyle u,v}$ ${\displaystyle u\leq v}$

Como MCD es conmutativo ( ), esas identidades aún se aplican si se intercambian los operandos: , si es impar, etc. ${\displaystyle \gcd(u,v)=\gcd(v,u)}$ ${\displaystyle \gcd(0,v)=v}$ ${\displaystyle \gcd(2u,v)=\gcd(u,v)}$ ${\displaystyle v}$

Implementación

Si bien la descripción anterior del algoritmo es matemáticamente correcta, las implementaciones de software de alto rendimiento generalmente difieren de ella en algunas formas notables:

• evitando la división de prueba en favor de un solo desplazamiento de bits y el primitivo de conteo de ceros finales ; esto es funcionalmente equivalente a aplicar repetidamente la identidad 3, pero mucho más rápido; ${\displaystyle 2}$
• expresando el algoritmo de forma iterativa en lugar de recursiva : la implementación resultante se puede diseñar para evitar trabajo repetido, invocando la identidad 2 al inicio y manteniendo como invariante que ambos números son impares al ingresar al bucle, que solo necesita implementar las identidades 3 y 4;
• haciendo que el cuerpo del bucle no tenga ramas excepto por su condición de salida ( ): en el ejemplo siguiente, el intercambio de y (asegurando ) compila hasta movimientos condicionales ; ^[5] las ramas difíciles de predecir pueden tener un impacto grande y negativo en el rendimiento. ^{[6] [7]} ${\displaystyle v=0}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\leq v}$

La siguiente es una implementación del algoritmo en Rust que ejemplifica esas diferencias, adaptada de uutils:

utilizar std :: cmp :: min ; utilizar std :: mem :: swap ;  pub fn gcd ( mut u : u64 , mut v : u64 ) -> u64 { // Casos base: gcd(n, 0) = gcd(0, n) = n si u == 0 { devuelve v ; } de lo contrario si v == 0 { devuelve u ; }                          // Usando las identidades 2 y 3: // mcd(2ⁱ u, 2ʲ v) = 2ᵏ mcd(u, v) con u, v impares y k = min(i, j) // 2ᵏ es la mayor potencia de dos que divide tanto a 2ⁱ u como a 2ʲ v let i = u . trailing_zeros (); u >>= i ; let j = v . trailing_zeros (); v >>= j ; let k = min ( i , j );                      loop { // u y v son impares al inicio del bucle debug_assert! ( u % 2 == 1 , "u = {} debería ser impar" , u ); debug_assert! ( v % 2 == 1 , "v = {} debería ser impar" , v );                 // Intercambie si es necesario para que u ≤ v si u > v { swap ( & mut u , & mut v ); }           // Identidad 4: mcd(u, v) = mcd(u, vu) cuando u ≤ v y u, v son ambos impares v -= u ; // v ahora es par     si v == 0 { // Identidad 1: mcd(u, 0) = u // El desplazamiento en k es necesario para volver a sumar el factor 2ᵏ que se eliminó antes del bucle return u << k ; }            // Identidad 3: mcd(u, 2ʲ v) = mcd(u, v) ya que u es impar v >>= v . trailing_zeros (); } }    

Nota : La implementación anterior acepta números enteros sin signo (no negativos); dado que , el caso con signo se puede manejar de la siguiente manera: ${\displaystyle \gcd(u,v)=\gcd(\pm {}u,\pm {}v)}$

/// Calcula el MCD de dos enteros con signo de 64 bits /// El resultado no tiene signo y no siempre se puede representar como i64: gcd(i64::MIN, i64::MIN) == 1 << 63 pub fn signed_gcd ( u : i64 , v : i64 ) -> u64 { gcd ( u . unsigned_abs (), v . unsigned_abs ()) }       

Complejidad

Asintóticamente , el algoritmo requiere pasos, donde es el número de bits en el mayor de los dos números, ya que cada dos pasos reducen al menos uno de los operandos en al menos un factor de . Cada paso implica solo unas pocas operaciones aritméticas ( con una constante pequeña); 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 máquina es del orden de , es decir . ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle 2}$ ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle \log _{2}(\max(u,v))}$

Para números arbitrariamente grandes, la complejidad asintótica de este algoritmo es , ^[8] ya que cada operación aritmética (restar y desplazar) implica un número lineal de operaciones de máquina (una por palabra en la representación binaria de los números). Si los números se pueden representar en la memoria de la máquina, es decir, el tamaño de cada número se puede representar con una sola palabra de máquina, este límite se reduce a: ${\displaystyle O(n^{2})}$ $${\displaystyle O\left({\frac {n^{2}}{\log _{2}n}}\right)}$$

Esto es lo mismo que para el algoritmo euclidiano, aunque un análisis más preciso de Akhavi y Vallée demostró que el MCD binario utiliza alrededor de un 60% menos de operaciones de bits. ^[9]

Extensiones

El algoritmo MCD binario se puede ampliar de varias maneras, ya sea para generar información adicional, manejar números enteros arbitrariamente grandes de manera más eficiente o para calcular MCD en dominios distintos a los números enteros.

El algoritmo binario extendido MCD , análogo al algoritmo euclidiano extendido , encaja en el primer tipo de extensión, ya que proporciona los coeficientes de Bézout además del MCD: números enteros y tales que . ^{[10] [11] [12]} ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\cdot {}u+b\cdot {}v=\gcd(u,v)}$

En el caso de números enteros grandes, la mejor complejidad asintótica es , con el costo de la multiplicación de -bits; esto es casi lineal y mucho más pequeño que el del algoritmo MCD binario , aunque las implementaciones concretas solo superan a los algoritmos más antiguos para números mayores a aproximadamente 64 kilobits ( es decir , mayores a 8×10 ¹⁹²⁶⁵ ). Esto se logra extendiendo el algoritmo MCD binario usando ideas del algoritmo de Schönhage–Strassen para la multiplicación rápida de números enteros. ^[13] ${\displaystyle O(M(n)\log n)}$ ${\displaystyle M(n)}$ ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

El algoritmo binario MCD también se ha extendido a dominios distintos de los números naturales, como los números enteros gaussianos , ^[14] los números enteros de Eisenstein , ^[15] los anillos cuadráticos, ^{[16] [17]} y los anillos enteros de cuerpos numéricos . ^[18]

Descripción histórica

Un algoritmo para calcular el MCD de dos números era conocido en la antigua China, bajo la dinastía Han , como método para reducir fracciones:

Si es posible, se divide por la mitad; de lo contrario, se toma el denominador y el numerador, se resta el menor al mayor y se hace así alternativamente para que sean iguales. Se reduce por el mismo número.

—  Fangtian – Topografía, Los nueve capítulos sobre el arte matemático

La frase "si es posible, reducirlo a la mitad" es ambigua, ^[4]

• Si esto se aplica cuando cualquiera de los números se vuelve par, el algoritmo es el algoritmo MCD binario;
• Si esto sólo se aplica cuando ambos números son pares, el algoritmo es similar al algoritmo euclidiano .

Véase también

• Portal de programación informática

• Algoritmo euclidiano
• Algoritmo euclidiano extendido
• Mínimo común múltiplo

Referencias

1. Brent, Richard P. (13–15 de septiembre de 1999). Análisis de veinte años del algoritmo binario euclidiano. Simposio Oxford-Microsoft de 1999 en honor del profesor Sir Antony Hoare. Oxford.
2. Brent, Richard P. (noviembre de 1999). Further analysis of the Binary Euclidean algorithm (Informe técnico). Laboratorio de Computación de la Universidad de Oxford. arXiv : 1303.2772 . PRG TR-7-99.
3. 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
4. Knuth, Donald (1998), Algoritmos seminuméricos , El arte de la programación informática , vol. 2 (3.ª ed.), Addison-Wesley, ISBN 978-0-201-89684-8
5. Godbolt, Matt. "Compiler Explorer" . Consultado el 4 de febrero de 2024 .
6. Kapoor, Rajiv (21 de febrero de 2009). "Cómo evitar el costo de una predicción errónea de las ramificaciones". Intel Developer Zone .
7. Lemire, Daniel (15 de octubre de 2019). "Las ramificaciones mal predichas pueden multiplicar los tiempos de ejecución".
8. "GNU MP 6.1.2: MCD binario".
9. Akhavi, Ali; Vallée, Brigitte (2000), "Complejidad de bits promedio de algoritmos euclidianos", Actas ICALP'00, Lecture Notes Computer Science 1853 : 373–387, CiteSeerX 10.1.1.42.7616 
10. Knuth 1998, p. 646, respuesta al ejercicio 39 de la sección 4.5.2
11. Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (octubre de 1996). "§14.4 Algoritmos del máximo común divisor" (PDF) . Manual de criptografía aplicada. CRC Press. págs. 606–610. ISBN 0-8493-8523-7. Recuperado el 9 de septiembre de 2017 .
12. Cohen, Henri (1993). "Capítulo 1: Algoritmos fundamentales de teoría de números". Un curso de teoría de números algebraica computacional. Textos de posgrado en matemáticas . Vol. 138. Springer-Verlag . Págs. 17-18. ISBN. 0-387-55640-0.
13. Stehlé, Damien; Zimmermann, Paul (2004), "Un algoritmo binario recursivo de mcd" (PDF) , Teoría algorítmica de números , Lecture Notes in Comput. Sci., vol. 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, S2CID  3119374, Informe de investigación INRIA RR-5050.
14. Weilert, André (julio de 2000). "Cálculo del MCD (1+i)-ario en Z[i] como análogo al algoritmo del MCD binario". Journal of Symbolic Computation . 30 (5): 605–617. doi : 10.1006/jsco.2000.0422 .
15. Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (12 a 15 de agosto de 2003). Algoritmos eficientes para MCD y residuosidad cúbica en el anillo de enteros de Eisenstein . XIV Simposio Internacional sobre los Fundamentos de la Teoría de la Computación. Malmo , Suecia. págs. 109-117. doi :10.1007/978-3-540-45077-1_11.
16. Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (13–18 de junio de 2004). Algoritmos binarios tipo MCD para algunos anillos cuadráticos complejos . Simposio de teoría algorítmica de números. Burlington, VT , EE. UU., págs. 57–71. doi :10.1007/978-3-540-24847-7_4.
17. Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (20–24 de marzo de 2006). Un nuevo algoritmo MCD para anillos numéricos cuadráticos con factorización única . 7º Simposio Latinoamericano de Informática Teórica. Valdivia, Chile. pp. 30–42. doi :10.1007/11682462_8.
18. Wikström, Douglas (11–15 de julio de 2005). On the l-Ary MCD-Algorithm in Rings of Integers [Sobre el algoritmo MCD l-ario en anillos de enteros] . Autómatas, lenguajes y programación, 32.º coloquio internacional. Lisboa, Portugal. pp. 1189–1201. doi :10.1007/11523468_96.

Lectura adicional

• Knuth, Donald (1998). "§4.5 Aritmética racional". Algoritmos seminuméricos . El arte de la programación informática . Vol. 2 (3.ª ed.). Addison-Wesley. págs. 330–417. ISBN 978-0-201-89684-8.

Cubre el MCD 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 algebraica computacional. Textos de posgrado en matemáticas . Vol. 138. Springer-Verlag . Págs. 12-24. ISBN. 0-387-55640-0.

Cubre una variedad de temas, incluido el algoritmo binario MCD extendido que genera coeficientes de Bézout , el manejo eficiente de números enteros de precisión múltiple utilizando una variante del algoritmo MCD de Lehmer y la relación entre MCD y expansiones de fracciones continuas de números reales.

• Vallée, Brigitte (septiembre-octubre de 1998). «Dinámica del algoritmo euclidiano binario: análisis funcional y operadores». Algorithmica . 22 (4): 660–685. doi :10.1007/PL00009246. S2CID  27441335. Archivado desde el original (PS) el 13 de mayo de 2011.

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 presentan 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 MCD binario
• Cortar el nudo: algoritmo binario de Euclides en cut-the-knot
• Análisis del algoritmo binario euclidiano (1976), un artículo de Richard P. Brent , que incluye una variante que utiliza desplazamientos a la izquierda