Related to this question and this Project Euler problem (Problem 99), I came up with a recursive algorithm for comparing two numbers of the form $x^y$ (with $x>1$ and $y\ge 0$) without explicit use of logarithms.
To compare $x_1^{y_1}$ or $x_2^{y_2}$ (resulting in "$\lt$", "$=$", or "$\gt$"):
- If $x_1=x_2$, compare $y_1$ to $y_2$ and return the result.
- If $x_1\gt x_2$, compare $x_2^{y_2}$ and $x_1^{y_1}$ and return the opposite result.
- (Now $x_1 \lt x_2$.) If $y_1\le y_2$, then return "$\lt$".
- (Now $y_1 \gt y_2$.) Compare $x_1^{y_1-y_2}$ to $\left(x_2/x_1\right)^{y_2}$ and return the result.
The last step is justified by noting that $ 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), $ so the new comparison has the same result as the old one; and the algorithm converges, in the sense that the exponents and the bases decrease at each iteration (to $0$ and to $1$ respectively). My question is, what exactly is this algorithm doing, and how many iterations should I expect it to take to do it? It looks like Euclid's method for finding the greatest common divisor, a little. Is there a more precise correspondence, and are the iterates meaningful?