# Efficiently Verifying “identities” in Arithmetic

So suppose I have two expressions $A,B$ both consisting of some combination of parenthesis $()$, addition $+$, multiplication $\times$, exponentiation $\text{^}$.

What is an efficient way to check if $A=B$?

## My Ideas:

So immediately one thing is that we could just evaluate $A$ as a number in some base, and do the same for $B$ and then compare. The problem is that given expressions such as

$$A = (1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)}}}}}\times (1+1+1)^{(1+1+1)}+1$$ $$B = ((1+1)\times(1+1)+1)^{(((1+1)\times(1+1)+1))^{((1+1)\times(1+1)+1))^{((1+1)\times(1+1)+1)}}}+1$$

This gets extremely out of hand, as the #of digits is simply too much to reasonable store. In this case: $$(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)^{(1+1)}}}}} = 2^{2^{2^{2^{2^{2}}}}}$$ has $2^{65536}$ digits and would be hopeless to process in this universe, by just "evaluating" the expression.

Now one thought was to modify the notion of "base-2" arithmetic to include, instead of sums of powers, say, sums of powers and power-towers, but there doesn't appear to be a natural way to generalize, and simple things like addition, and multiplication become tricky.

• Comparing extremely large numbers can be very difficult. But in the case of power towers not too high, you can calculate the logarithms or the double logarithms to compare $A$ and $B$ – Peter Dec 4 '16 at 22:11
• @Peter but can we exploit the fact we are mostly interested in checking inequality? I don't need to know which is larger ,just that they are unequal – frogeyedpeas Dec 4 '16 at 22:12
• If you only want to verify whether power towers are equal , this should be possible, but I do not know a method covering all possible cases. Can you show us a "difficult" example, where you do not know how to verify the equality ? – Peter Dec 4 '16 at 22:14