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.

  • 1
    $\begingroup$ 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$ $\endgroup$ – Peter Dec 4 '16 at 22:11
  • $\begingroup$ @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 $\endgroup$ – frogeyedpeas Dec 4 '16 at 22:12
  • $\begingroup$ 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 ? $\endgroup$ – Peter Dec 4 '16 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.