Comparing powers without logarithms

This is a bit long for a comment, so I'll start turning it into an answer, though there may well be more to say e.g. about the meaning of the iterates.

I find it slightly easier to think about the corresponding algorithm for comparing products without multiplication; as discussed in the comments, this is directly analogous. Let's see how this plays out in an example (assuming that none of the intermediate steps yield a successful comparison):

$$ \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}$$

The algorithm ends with $\gcd(54,21)=3$ and a direct comparison of the numbers $13a-5b$ and $2b-5a$, which is the same as comparing $18a$ and $7b$, the original comparison reduced by the gcd.

The efficiency of the Euclidean algorithm is usually analyzed counting each quotient and remainder computation as one step; in that case the worst case is two consecutive Fibonacci numbers, so the algorithm takes about $\log n/\log\phi$ steps. However, if you perform individual subtractions instead, this may take linear time, the worst case in this scenario being if one of the exponents is $1$ and you're merely very inefficiently multiplying out the power on the other side one factor at a time. At first I thought your algorithm might be an efficient way to organize exponentiation by squaring, but that example shows that it's more somewhat complementary to that. Indeed you could combine the two and make the complexity logarithmic by doing the intermediate steps using repeated squaring.

Two more comments: The bases never influence the control flow, except by ending it; the sequence of computations is entirely determined by the Euclidean algorithm being applied to the exponents. And if you're looking for precision and trying to compare numbers close to each other, I don't think you're gaining much other than reducing by the gcd, since you're explicitly calculating ratios of high powers of the bases, whose quotient is (the gcd-th root of) the quotient of the numbers being compared.