¿El promedio de duración del algoritmo de Euclides?

Question

¿Cuál es la duración promedio del algoritmo de Euclides con respecto a todos los posibles pares de entrada $(m,n)$ tal que $\gcd(m,n) = d$?

Parece muy difícil deducir el % de repetición $T(m,n) = T(n, m \bmod n)+1$.

¿Alguna idea mejor?

Answer 1

El número de pasos necesarios para calcular el $\gcd(m,n)$ viene dado por la longitud de la fracción continua de $\frac{m}{n}$, por lo tanto, el peor de los casos es calcular el $\gcd$ de dos números de Fibonacci consecutivos (desde $\frac{F_{n+1}}{F_n}=[1;1,\ldots,1]$) y un límite superior para el número de pasos es: %#% $ $$ 1+\frac{\log(\max(m,n))}{\log\varphi} $ #% Dónde está la proporción áurea $\varphi$.