¿Por qué los números de Fibonacci son malos para el Algoritmo de Euclides y cómo deducir este límite superior del número de pasos necesarios en general?

Question

Quiero preguntar dos cosas.

La primera es ¿por qué los números de Fibonacci consecutivos son el peor caso para el algoritmo de Euclides? Sigo viendo a la gente decirlo de pasada y entiendo que es realmente malo, pero ¿cómo sabemos que es el peor ?

La segunda pregunta se refiere a un límite superior en el número de aplicaciones del algoritmo de división necesarias para calcular el DGC de dos enteros positivos distintos. Me han dado la pista de que será de la forma $c \log b + d$ cuando $c, d$ son constantes y $b$ es el menor de los dos números con los que empiezas.

He visto a alguien mencionar que es $\frac{1}{2} \log b + 1$ pero, de nuevo, no sé cómo derivar esto y agradecería mucho una pista o un empujón en la dirección correcta.

Gracias de antemano.

Answer 1

El número de pasos necesarios para calcular $\gcd(a,b)$ viene dada por la longitud $^{(*)}$ de la fracción continua de $\frac{a}{b}$ . De ello se deduce que el peor caso para el algoritmo euclidiano viene dado por los convergentes de $\varphi=\frac{1+\sqrt{5}}{2}=[1;1,1,1,1,\ldots]$ es decir, por números de Fibonacci consecutivos.

(*) Explicación: asumir $a>b$ , un paso del algoritmo euclidiano trae la pareja $(a,b)$ en la pareja $(b,a\pmod{b})$ . Por otra parte, el mapa de Gauss $x\mapsto \frac{1}{x-\lfloor x\rfloor}$ aplicado a $x=\frac{a}{b}$ actúa exactamente de la misma manera. De ello se deduce que el cálculo de $\gcd(F_{n+1},F_n)$ requiere $n$ pasos ya que recorre los convergentes $[1],[1;1],[1;1,1],\ldots$ de $\frac{F_{n+1}}{F_n}$ en sentido contrario. Además, $\frac{F_{n+1}}{F_n}$ es el número racional $>1$ con una fracción continua de longitud $n$ y el menor numerador/denominador: los términos de una fracción continua, con la única excepción del primero, no pueden ser menores que $1$ . Se deduce que al considerar todas las fracciones continuas con la misma longitud, el mínimo de $\frac{a}{b}\to |a|+|b|$ se consigue mediante $[0;1,1,1,\ldots]$ .

Answer 2

Pista:

En cada iteración, $(a,b)$ se sustituye por $(b,a\bmod b)$ . El peor caso se produce cuando la disminución $a-b$ es el más pequeño, y esto ocurre cuando el cociente entero es $b/a=1$ (para que $a\bmod b=a-b$ ).

Por su propia definición, la sucesión de Fibonacci tiene esta propiedad en cada paso.

Ahora bien $F_k\le b\le F_{k-1}$ para algunos $k$ el número de iteraciones para $n$ no puede superar $F_k$ (en el peor de los casos).

A partir de la fórmula de Binet, $$F_k\approx\phi^k$$ y el límite es

$$k\approx\log_\phi n.$$

Answer 3

Digamos que una entrada al algoritmo euclidiano es un par $(a,b)$ de número natural $a,b\in\Bbb N$ (sin cero) con $a> b$ . Recuerde que para $a_0> b_0$ el algoritmo procede mediante

$$a_{i+1}=b_i,\qquad b_{i+1}=a_i\text{ mod } b_i$$

y termina después de $k$ iteraciones cuando $b_k=0$ . Sea $A_k$ es el conjunto de entradas para las que el algoritmo termina exactamente en $k$ pasos. Mostramos

Teorema . $A_k$ tiene un elemento componente-sabio más pequeño $(a,b)$ es decir, para todos $(c,d)\in A_k$ tenemos $c\ge a$ y $d\ge b$ .

Daré una prueba, pero permítanme decir primero lo siguiente: estos elementos componentes-sabios más pequeños pueden ser considerados como el peor entradas del algoritmo euclidiano. ¿Por qué? Porque esperamos que las entradas más pequeñas termien antes. Pero estos elementos mínimos específicos no $-$ son relativamente pequeños pero necesitan $k$ pasos como todos los demás elementos mayores de $A_k$ también. Así que estos mínimos son los peores cuando se trata de tiempo de ejecución en relación con el tamaño.

Prueba .

La prueba es por inducción. Es bastante fácil ver que $A_1=\{(ka,a)\mid a,k\in\Bbb N,k\ge 2\}$ . Entonces $A_1$ es $(2,1)$ .

También es fácil ver que si $(a,b)\in A_k$ entonces $(a+b,a)\in A_{k+1}$ . Afirmo que si $(a,b)$ es mínimo en $A_k$ entonces $(a+b,a)$ es mínimo en $A_{k+1}$ .

Demostrémoslo por contradicción. Supongamos que existe un elemento $(c,d)\in A_{k+1}$ avec $c<a+b$ o $d<a$ . Podemos excluir el último caso, porque una iteración de los algoritmos euclidianos generaría $(d,c\text{ mod } d)\in A_k$ para lo cual $(a,b)$ no es menor ahora, en contradicción con su elección. Por tanto, tenemos $d\ge a$ pero $c<a+b$ . También vemos que $(c\text{ mod } d)\ge b$ lo que equivale a $c-kd\ge b$ para algunos $k\in\Bbb N$ especialmente $c-d\ge b$ . Pero ahora

$$c<a+b\le d+(c-d)=c.$$

Contradicción. $\quad\square$

Así que tenemos un peor elemento en $A_k$ en algún sentido preciso. Y si sigues la construcción de estos elementos en la prueba, puedes ver que siguen la regla de generación del Números de Fibonacci .

Si está familiarizado con los números de Fibonacci $F_k$ entonces probablemente sepa que $F_k$ crece exponencialmente como $\phi^k$ donde $\phi$ es la proporción áurea $\phi\approx 1.618...$ . Así pues, esta construcción da como resultado un par de entrada con elementos de tamaño mínimo $\sim\phi^k$ en $A_k$ que termina después de $k$ pasos. Si se le da la vuelta, en el peor de los casos, para un par de entrada con elementos de tamaño mínimo $s$ el algoritmo euclidiano termina después de $\sim \log_\phi s$ pasos.

Answer 4

Observamos que cada paso del algoritmo euclidiano (EA) no es más que un desentrañamiento de la recurrencia hacia atrás que comienza $f_{n+2}=1\cdot f_{n+1}+f_{n}$ hasta que, después de $n$ pasos que alcanzamos $f_{3}=2\cdot f_{2}+0$ por el cual $f_{1}=f_{2}=1$ es siempre el $\gcd$ de números de Fibonacci adyacentes: $(f_{n+1},f_{n})=1$ .

\begin{align*} f_{n+2}&=1\cdot f_{n+1}+f_{n}\\ f_{n+1}&=1\cdot f_{n}+f_{n-1}\\ \dots\dots &\dots\dots \dots\dots\dots\\ f_{4}&=1\cdot f_{3}+f_{2}\\ f_{3}&=2\cdot f_{2} \end{align*} Esto muestra el peor escenario para la EA, ya que todos los cocientes parciales, excepto el último, son $1$ por lo que tardará un máximo de $n$ pasos. De hecho, el menor de tales números que toman un máximo de $n$ pasos son números de Fibonacci adyacentes, como mostramos ahora.

Un teorema de Gabriel Lame muestra que el número de divisiones requeridas por la EA es como máximo $5$ veces el número de dígitos del menor de los números. Para ello necesitamos la desigualdad \begin{equation} f_{n+5}>10f_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$}\tag{1} \end{equation} Esto es válido para $n=2$ . Para $n\geq3$ \begin{align*} f_{n+5}&=f_{n+4}+f_{n+3}=2f_{n+3}+f_{n+2}=3f_{n+2}+2f_{n+1}\\ &=5f_{n+1}+3f_{n}=8f_{n}+5f_{n-1} \end{align*} Como la sucesión de Fibonacci no es decreciente, tenemos $f_{n}=f_{n-1}+f_{n-2}\leq 2f_{n-1}$ lo que implica $2f_{n}\leq 4f_{n-1}$ . Por lo tanto $f_{n+5}=8f_{n}+5f_{n-1}>8f_{n}+4f_{n-1}\geq10f_{n}$ lo que implica $f_{n+5}>10f_{n}$ según sea necesario. Utilicemos ahora la inducción para el caso general: \begin{equation} f_{n+5k}>10^kf_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$; $k=1,\,2,\,3,\dotsc$}\tag{2} \end{equation} En $k=1$ se ha demostrado que es cierto para algunos casos arbitrarios. $k\in\mathbb{N}$ y mostrar por $k+1$ : \begin{align*} f_{n+5(k+1)}&=f_{n+5+5k}=f_{n+4+5k}+f_{n+3+5k}=2f_{n+3+5k}+f_{n+2+5k}\\ &=3f_{n+2+5k}+2f_{n+1+5k} =5f_{n+1+5k}+3f_{n+5k}\\ &=8f_{n+5k}+5f_{n-1+5k} \end{align*} Como antes $f_{n+5k}=f_{n-1+5k}+f_{n-2+5k}\leq 2f_{n-1+5k}$ lo que implica $2f_{n+5k}\leq 4f_{n-1+5k}$ . Por lo tanto \begin{align*} f_{n+5(k+1)}&=8f_{n+5k}+5f_{n-1+5k}>8f_{n+5k}+4f_{n-1+5k}\\ &\geq10f_{n+5k}>10\cdot10^k f_{n}=10^{k+1}f_{n} \end{align*} por hipótesis, lo que implica $f_{n+5(k+1)}>10^{k+1}f_{n}$ según sea necesario para completar la inducción.

Ahora dejemos que $a_{0}$ y $a_{1}\in\mathbb{N}$ con $a_1<a_0$ y asumir que se necesita $j$ divisiones para encontrar $(a_0,a_1)$ por la EA: \begin{align*} a_{0}&=q_1\cdot a_{1}+a_{2}\\ a_{1}&=q_2\cdot a_{2}+a_{3}\\ \dots&\dots\dots\dots \dots\dots\dots\\ a_{j-2}&=q_{j-1}\cdot a_{j-1}+a_{j}\\ a_{j-1}&=q_j\cdot a_{j} \end{align*} Ahora $q_j\neq1$ desde entonces $a_{j-1}=a_{j}$ . Así $a_{j-1}=q_j\cdot a_{j}\geq2a_{j}\geq2=f_3$ . Por lo tanto $a_{j-2}\geq a_{j-1}+a_{j}\geq f_3+f_2=f_4$ , $a_{j-3}\geq a_{j-2}+a_{j-1}\geq f_4+f_3=f_5$ hasta llegar a $a_1\geq f_{j}+f_{j-1}=f_{j+1}$ y $a_1\geq f_{j+1}+f_{j}=f_{j+2}$ . Si $j\geq5k+1$ entonces $a_1\geq f_{5k+2}>10^kf_2=10^k$ por $(2)$ y así tiene al menos $k+1$ dígitos. Por lo tanto, si $a_1$ tiene $k$ dígitos, entonces $j\leq5k$ es decir, para $a_1$ teniendo $k$ dígitos, como máximo $5k$ Las divisiones se exigen en la EA según sea necesario. Estas desigualdades demuestran la afirmación anterior de que los números de Fibonacci adyacentes $f_{j+2}$ y $f_{j+1}$ son los que menos hay que tomar $j$ pasos para completar la EA y si tarda $j$ iteraciones para encontrar $(a_0,a_1)$ como arriba, entonces $a_0\geq f_{j+2}$ y $a_1\geq f_{j+1}$ .

La fórmula cerrada de Binet para los números de Fibonacci es $$f_{n}=\frac{\varphi^{n}-\psi^{n}}{\varphi -\psi}=\frac{\varphi^{n}-\psi ^{n}}{\sqrt {5}}$$ donde $$\varphi =\frac{1+\sqrt {5}}{2}\approx1.6180339887\dotsc \quad\text{and}\quad\psi =\frac{1-\sqrt {5}}{2}\approx-0.6180339887\dotsc$$ La fórmula de Binet muestra $f_n$ es asintótica a $\varphi^n/\sqrt{5}$ lo que implica

\begin{equation}\label{eq:logfnsqrt5} n\approx \log_{\varphi}(f_n\sqrt{5})\approx \log_{\varphi}f_n \end{equation}

Por lo tanto, si para números enteros $0<a<b$ la EA exige $n+1$ pasos, entonces $b\geq f_{n+3}$ , $a\geq f_{n+2}\geq \varphi^{n}$ entonces $n<\log_{\varphi}a$ .

Desde $f_n\sim \varphi^n/\sqrt{5}$ también tenemos el número de dígitos en $f_n$ dado aproximadamente como \begin{equation}\label{eq:digitsfn}\log_{10}\,f_n \approx n\log_{10}\varphi\approx0.20899n \end{equation} donde utilizamos la base $10$ ya que estamos en decimal.

Por lo tanto, si la EA toma $n+1$ pasos $0.2n<\log_{10}\varphi \log_{\varphi}a =\log_{10}a$ . Así, $n<5\log_{10}a$ lo que implica que la EA siempre necesita menos de $O(\text{#digits of $ a $})$ divisiones.

La EA también se conoce como algoritmo de fracciones continuas ya que el $q_i$ de la EA forman los cocientes parciales de la fracción $a_0/a_1$ fracción continua.

Sea $a_0$ y $a_1$ ser como antes, teniendo $j$ ecuaciones lineales obtenidas mediante la EA. Para $i=1,\dotsc, j-1$ deje $$\frac{a_{i-1}}{a_{i}}=q_{i}+\frac{1}{\frac{a_i}{a_{i+1}}}\quad\text{and}\quad\frac{a_{j-1}}{a_j}=q_j$$ Esto da una fracción continua simple $$\frac{a_0}{a_1}=[q_1;\,q_2,\dotsc,q_{j-1},\,q_j]$$ donde todos los numeradores son $1$ . Ahora $q_1$ es un número entero, y como $a_{i-1}>a_i$ , $q_2,\dotsc,q_j$ son números naturales. Entonces al aplicar esto a la secuencia de Fibonacci $$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,1]\tag{3}$$ donde hay $(n-1)$ $1s$ después del punto y coma; nótese que también podríamos escribirlo como $$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,2]$$ con $(n-3)$ $1s$ Después del punto y coma y una terminación $2$ en la fracción continua para $n\geq3$ . Observamos el número de cocientes parciales en la fracción continua en $(3)$ y así en general para dos enteros cualesquiera, da el número de pasos necesarios en el EA.

Answer 5

Puedes demostrarlo usando inducción sobre el número de llamadas a gcd().

Para probar: Si un par (a,b) requiere n pasos para calcular el gcd, entonces

1. a >= F_(k+2)
2. b >= F_(k+1) Con una suposición a >= b

Caso base n = 1, el lema es cierto.

Consideremos que el lema es cierto para n = k - 1, k > 1

Sea un par (a,b) tal que se necesiten k pasos para calcular el gcd. Por lo tanto (b, a mod b) tomará k - 1 pasos. Por lo tanto b >= F_(k+1) ... por hipótesis Y a mod b >= F_(k)

Ahora, a = b×q + a mod b >= b + a mod b >= F_(k+1) + F_(k) >= F(k+2)

Por lo tanto, hemos demostrado que los números de Fibonacci consecuentes son el peor caso. Más concretamente, son el menor de los números para dar un cierto número arbitrario de pasos.