Algoritmo euclidiano para el máximo común divisor

Question

Utilizando el algoritmo euclidiano para $\gcd(121, 330)$ ¿cuántas divisiones son necesarias para el proceso?

Answer 1

Esto en Mathematica te dará el número de restas necesarias:

gcd[a_, b_] := gcd[Abs[a], Abs[b], 0];
gcd[a_, 0, step_] := {a, step};
gcd[0, b_, step_] := {b, step};
gcd[a_, b_, step_] := Which[
   a >= b, gcd[a - b, b, step + 1],
   b > a, gcd[a, b - a, step + 1]];

No está optimizado en absoluto (realiza manualmente cada resta en lugar de utilizar Mod ) y probablemente lo que quieres no son las restas, pero puedes hacer modificaciones. También te muestra cómo puedes hacer este tipo de cosas "algorítmicas" en Mathematica por coincidencia de patrones. Por ejemplo, el paso en el algoritmo que dice "si cualquiera de los números es 0, deténgase" está codificado en las líneas 2 y 3 del código.

Un gráfico de las sustracciones requeridas tiene este aspecto:

data = Table[gcd[i, j][[2]], {i, Range[0, 80]}, {j, Range[0, 80]}];
ListPlot3D[data, InterpolationOrder -> 2, Mesh -> None, Boxed -> False, PlotRange -> Full]

Sé que no es exactamente lo que buscas, pero quería aportar la perspectiva computacional. :)

Actualización

En respuesta al comentario de @Jyrki, aquí está la versión "más rápida" del algoritmo que resta tantos múltiplos como sea posible en un paso dado:

gcd[a_, b_] := gcd[Abs[a], Abs[b], 0];
gcd[a_, 0, step_] := {a, step};
gcd[0, b_, step_] := {b, step};
gcd[a_, b_, step_] := Which[
   a >= b, gcd[a - IntegerPart[a/b]*b, b, step + 1],
   b > a, gcd[a, b - IntegerPart[b/a]*a, step + 1]];

data = Table[gcd[i, j][[2]], {i, Range[0, 599]}, {j, Range[0, 599]}];

Como el algoritmo es rápido ( Max[data] muestra que dos números cualesquiera entre 0 y 599 se resolverán como máximo en 12 pasos), el valor salta rápidamente entre sólo unos pocos valores discretos (0-12), lo que hace que un gráfico 3D normal tenga mucho ruido. Por eso he utilizado un gráfico de densidad:

ListDensityPlot[data, ImageSize -> {600, 600}, PlotRangePadding -> None, Frame -> None, Axes -> False]

He aquí un "primer plano" obtenido trazando en un rango diferente:

data = Table[gcd[i, j][[2]], {i, Range[250949, 250949 + 599]}, {j, Range[0, 599]}];

Answer 2

Observe que \begin{align} \gcd(121,330) &= \gcd(121,88) \quad (88 = 330 - 2 \times 121.) \\ &= \gcd(33,88) \quad (33 = 121 - 1 \times 88.) \\ &= \gcd(33,22) \quad (22 = 88 - 2 \times 33.) \\ &= \gcd(11,22) \quad (11 = 33 - 1 \times 22.) \\ &= \gcd(11,0) = 11. \quad (0 = 22 - 2 \times 11.) \end{align} Por lo tanto, $ 5 $ pasos son necesarios para terminar el Algoritmo Euclidiano para el par $ (121,330) $ .

Al aplicar el Algoritmo Euclidiano, el número de pasos necesarios hasta la terminación nunca excede de $ 5 $ veces el número de cifras decimales del número más pequeño. Este hecho es consecuencia de Teorema de Lamé . (Algunos autores etiquetan el hecho en sí como Teorema de Lamé; véase este enlace para un debate interesante). La demostración del teorema, que también puede encontrarse en el enlace anterior, es interesante por su uso de los números de Fibonacci.

Answer 3

No necesitas ninguna división. Sólo necesitas restos, no cocientes. En cuanto a cuántos restos necesitas:

330/121 da un resto de 88
121/88 da un resto de 33

etc. Detente cuando obtengas un resto igual a 0 (y entonces la respuesta será el último resto distinto de cero). No te llevará mucho tiempo :-)