El algoritmo GCD de Lehmer , que lleva el nombre de Derrick Henry Lehmer , es un algoritmo GCD rápido , una mejora del algoritmo euclidiano más simple pero más lento . Se utiliza principalmente para números enteros grandes que tienen una representación como una cadena de dígitos en relación con alguna base del sistema numérico elegido , digamos β = 1000 o β = 2 32 .
Algoritmo
Lehmer señaló que la mayoría de los cocientes de cada paso de la parte de división del algoritmo estándar son pequeños. (Por ejemplo, Knuth observó que los cocientes 1, 2 y 3 comprenden el 67,7% de todos los cocientes. [1] ) Esos pequeños cocientes pueden identificarse con sólo unos pocos dígitos iniciales. Por lo tanto, el algoritmo comienza dividiendo esos dígitos iniciales y calculando la secuencia de cocientes siempre que sea correcta.
Decimos que queremos obtener el MCD de los dos enteros una y b . Sea a ≥ b .
- Si b contiene solo un dígito (en la base elegida , digamos β = 1000 o β = 2 32 ), utilice algún otro método, como el algoritmo euclidiano , para obtener el resultado.
- Si un y b difieren en la longitud de dígitos, realice una división de modo que una y b son iguales en longitud, con una longitud igual a m .
- Bucle externo: iterar hasta que uno de a o b sea cero:
- Disminuya m en uno. Vamos x ser el (más significativo) dígitos líder en una , x = un div β m y y el dígito líder en b , y = b div β m .
- Inicializar una matriz de 2 por 3
- a una matriz de identidad extendida
- y realizar el algoritmo euclidiano simultáneamente en los pares ( x + A , y + C ) y ( x + B , y + D ), hasta que los cocientes difieran. Es decir, iterar como un bucle interno :
- Calcule los cocientes w 1 de las divisiones largas de ( x + A ) por ( y + C ) y w 2 de ( x + B ) por ( y + D ) respectivamente. Sea también w el cociente (no calculado) de la división larga actual en la cadena de divisiones largas del algoritmo euclidiano.
- Si w 1 ≠ w 2 , salga de la iteración interna. De lo contrario, configure w a w 1 (o w 2 ).
- Reemplazar la matriz actual
- con el producto de matriz
- según la formulación matricial del algoritmo euclidiano extendido.
- Si B ≠ 0, vaya al inicio del bucle interior.
- Si B = 0, hemos llegado a un punto muerto ; realizar un paso normal del algoritmo de Euclides con un y b , y reiniciar el bucle exterior.
- Establecer una a aA + bB y b a Ca + Db (de nuevo simultáneamente). Esto se aplica los pasos del algoritmo de Euclides que se realizaron en los dígitos principales en forma comprimida a los largos números enteros una y b . Si b ≠ 0, vaya al inicio del bucle exterior.
Referencias
- ^ Knuth , El arte de la programación informática vol 2 "Algoritmos seminuméricos" , capítulo 4.5.3 Teorema E.