Comparación de poderes sin logaritmos

Question

Relacionado con esta cuestión , y este Proyecto de Euler del problema (Problema 99), me vino con un algoritmo recursivo para comparar dos números de la forma $x^y$ ( $x>1$ $y\ge 0$ ) sin uso explícito de los logaritmos.

Para comparar los $x_1^{y_1}$ o $x_2^{y_2}$ (lo que resulta en "$\lt$", "$=$", o "$\gt$"):

1. Si $x_1=x_2$, compare $y_1$ $y_2$y devolver el resultado.
2. Si $x_1\gt x_2$, compare $x_2^{y_2}$ $x_1^{y_1}$ y devolver el resultado opuesto.
3. (Ahora $x_1 \lt x_2$.) Si $y_1\le y_2$, a continuación, volver "$\lt$".
4. (Ahora $y_1 \gt y_2$.) Compare $x_1^{y_1-y_2}$ $\left(x_2/x_1\right)^{y_2}$y devolver el resultado.

El último paso se justifica señalando que $$ x_1^{y_1} - x_2^{y_2} = x_1^{y_2}\left(x_1^{y_1-y_2}-(x_2/x_1)^{y_2}\right), $$ de modo que la nueva comparación tiene el mismo resultado que el anterior; y el algoritmo converge, en el sentido de que los exponentes y las bases disminuyen en cada iteración (a $0$ $1$ respectivamente). Mi pregunta es, ¿qué es exactamente este algoritmo haciendo, y cómo muchas iteraciones debo esperar que tome para hacerlo? Parece que el método de Euclides para encontrar el máximo común divisor, un poco. Es allí una manera más precisa la correspondencia, y se la recorre en sentido?

Answer 1

Este es un poco largo para un comentario, así que voy a empezar a convertirlo en una respuesta, aunque puede que haya más que decir por ejemplo, sobre el significado de la iteración.

Me parece un poco más fácil pensar en el algoritmo correspondiente para la comparación de productos sin la multiplicación; como se discute en los comentarios, este es directamente análoga. Vamos a ver cómo esto se desempeña en un ejemplo (suponiendo que ninguno de los pasos intermedios de rendimiento de un éxito de la comparación):

$$ \begin{eqnarray} 54a&\lessgtr&21b\\ 33a&\lessgtr&21(b-a)\\ 12a&\lessgtr&21(b-2a)\\ 12(3a-b)&\lessgtr&9(b-2a)\\ 3(3a-b)&\lessgtr&9(2b-5a)\\ 3(8a-3b)&\lessgtr&6(2b-5a)\\ 3(13a-5b)&\lessgtr&3(2b-5a)\\ \end{eqnarray}$$

El algoritmo termina con $\gcd(54,21)=3$ y una comparación directa de los números de $13a-5b$$2b-5a$, que es la misma como la comparación de $18a$$7b$, el original de la comparación reducido por el mcd.

La eficiencia del algoritmo de Euclides se analizan generalmente contando cada uno de cociente y el resto de cálculo como un paso; en ese caso, el peor de los casos es de dos números de Fibonacci consecutivos, de manera que el algoritmo toma alrededor de $\log n/\log\phi$ pasos. Sin embargo, si realiza individuales sustracciones en su lugar, esto puede tomar tiempo lineal, en el peor de los casos en este escenario, cuando uno de los exponentes es $1$ y usted es simplemente muy ineficientemente multiplicando el poder en el otro lado un factor a la vez. Al principio pensé que su algoritmo puede ser una forma eficiente de organizar la exponenciación al cuadrado, pero este ejemplo muestra que es más algo complementario. De hecho, usted puede combinar los dos y hacer la complejidad logarítmica haciendo los pasos intermedios uso repetido de cuadratura.

Dos comentarios más: Las bases nunca influir en el flujo de control, excepto por acabar con ella; la secuencia de los cálculos, está totalmente determinado por el algoritmo de Euclides se aplica a los exponentes. Y si usted está buscando para la precisión y tratando de comparar los números de cerca uno del otro, no creo que usted está ganando mucho más que reducir por el mcd, ya que usted está explícitamente calcular las proporciones de los altos poderes de las bases, cuyo cociente es (el mcd-ésima raíz de) el cociente de los números que se comparan.