Algoritmo del MCD de Lehmer

El algoritmo MCD de Lehmer , que recibe su nombre de D.H. Lehmer , es un algoritmo MCD rápido para aritmética de precisión múltiple , que mejora el algoritmo euclidiano más simple al realizar la mayoría de las operaciones utilizando solo los dígitos iniciales de los valores. Aquí, "dígito" no se refiere necesariamente a un dígito decimal; el algoritmo se usa a menudo con enteros representados usando una base β , como β = 1000 o β = ^2³² .

Lehmer señaló que la mayoría de los cocientes de cada paso de la división del algoritmo estándar son pequeños. (Por ejemplo, Knuth observó que los cocientes 1, 2 y 3 representan el 67,7 % del total de cocientes. ^{[ 1 ]} ) Estos cocientes pequeños pueden identificarse a partir de solo unos pocos dígitos iniciales. Por lo tanto, el algoritmo comienza separando esos dígitos iniciales y calculando la secuencia de cocientes siempre que sea correcta.

Digamos que queremos obtener el MCD de dos enteros a y b . Sea a ≥ b .

• Si b contiene solo un dígito (en la base elegida , por ejemplo β = 1000 o β = 2 ³² ), utilice algún otro método, como el algoritmo euclidiano , para obtener el resultado.
• Si a y b difieren en la longitud de los dígitos, reduce a módulo b e intercámbialos como en el algoritmo euclidiano estándar. Repite hasta que ambos tengan la misma longitud m .
• Bucle exterior: Iterar hasta que uno de los dos , a o b, sea cero:
  • Disminuya m en uno. Sea x el dígito principal (más significativo) en a , x = a div β ^{m e} y el dígito principal en b , y = b div β ^m .
  • Inicializa una matriz de 2 por 3.

  ${\displaystyle \textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}}$a una matriz identidad extendida${\displaystyle \textstyle {\begin{bmatrix}1&0&x\\0&1&y\end{bmatrix}},}$

  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 :

  • Calcula los cocientes w ₁ de las divisiones largas de ( x + A ) entre ( y + C ) y w ₂ de ( x + B ) entre ( y + D ), respectivamente. Si son iguales, también son iguales a w , el cociente (no calculado) del paso correspondiente del algoritmo euclidiano ordinario.

  • • Si w ₁ ≠ w ₂ , entonces salga de la iteración interna. De lo contrario, establezca w en w ₁ (o w ₂ ).
    • Reemplazar la matriz actual

    ${\displaystyle \textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}}$

    con el producto de matriz

    ${\displaystyle \textstyle {\begin{bmatrix}0&1\\1&-w\end{bmatrix}}\cdot {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}={\begin{bmatrix}C&D&y\\A-wC&B-wD&x-wy\end{bmatrix}}}$

    según la formulación matricial del algoritmo euclidiano extendido.

    • Si B ≠ 0, vaya al inicio del bucle interno.
  • Si B = 0, hemos llegado a un punto muerto ; realice un paso normal del algoritmo euclidiano con a y b , y reinicie el bucle externo.
  • Asigne a los valores aA + bB y b a Ca + Db (simultáneamente). Esto aplica los pasos del algoritmo euclidiano, realizados sobre los dígitos iniciales en forma comprimida, a los enteros largos a y b . Si b ≠ 0, vuelva al inicio del bucle externo.

• Kapil Paranjape , algoritmo de Lehmer