First I tried it directly, but it overflowed:

In[1]:= 2^3^2^3^5^8 < 3^2^2^7^6^7
During evaluation of In[1]:= General::ovfl: Overflow occurred in computation. >>
During evaluation of In[1]:= General::ovfl: Overflow occurred in computation. >>

Out[1]= Indeterminate < Indeterminate

Using double Log did not help either:

In[2]:= Log[Log[2]] + Log[3] 2^3^5^8 < Log[Log[3]] + Log[2] 2^7^6^7  
During evaluation of In[2]:= General::ovfl: Overflow occurred in computation. >>
During evaluation of In[2]:= General::ovfl: Overflow occurred in computation. >>

Out[2]= Overflow[] < Overflow[]

Then I tried to use the WolframAlpha function, and it seemed to be able to handle this and even much higher towers:

In[3]:= WolframAlpha["2^3^2^3^5^8 < 3^2^2^7^6^7", "MathematicaForms"][[2, 1]]
Out[3]= True

In[4]:= WolframAlpha["2^2^5^2^7^4^9^3^7^6^9^9^9^9^3^2 < 3^3^6^3^9^4^2^3^2^2^2^2^2^3^3^3", "MathematicaForms"][[2, 1]]
Out[4]= True

But then I discovered that it failed to perform certain comparisons:

In[5]:= WolframAlpha["4^6^8^8^9 < 3^2^3^3^3", "MathematicaForms"]
Out[5]= {}

And sometimes even gave wrong answers, even in seemingly trivial cases:

In[6]:= WolframAlpha["3^3^3^3^3 < 4^4^3^3^3", "MathematicaForms"][[2, 1]]
Out[6]= False

Can anybody suggest a correct and robust method to compare two expressions given in the form Hold[a^b^...^z], where a,b,...,z are positive integers?

  • 4
    $\begingroup$ Related question. $\endgroup$ May 7, 2013 at 20:14
  • 6
    $\begingroup$ Just because it caused me a lot of consternation, the top answer on the Math Stack Exchange is mathematically incorrect. $\endgroup$
    – Guillochon
    May 8, 2013 at 0:50
  • 4
    $\begingroup$ @Guillochon Both are incorrect and misleading as it is also pointed out in comments. Strange thing that they are sill there. $\endgroup$
    – Kuba
    May 8, 2013 at 1:02
  • 5
    $\begingroup$ @Rojo Even if they might be seen as equal in some representations, there is actually a huge difference between them: 4^4^3^3^3 - 3^3^3^3^3 > 10^10^4591067155680. $\endgroup$ May 8, 2013 at 2:47
  • 6
    $\begingroup$ I started a bounty worth +350 at math.stackexchange.com/questions/101138/… $\endgroup$ May 8, 2013 at 3:15

1 Answer 1


The idea

The idea is that if we have

$\log(a+b),\qquad a\gg b$ ,

then we can equivalently write this as

$\log a + \log(1 + b/a)$

and the second part will be small, so that one can first compare the first part(s). The power towers with base numbers larger than 1 naturally lead to such logarithms when we repeatedly take the $\log$ of them. So, there seems to be a natural separation of a dominant part and a sub-leading part, which is what I think allows one to compare the towers in many or most cases.


OK, here is my attempt. To illustrate what I am going to do, first define these functions:

SetAttributes[symbolicConvert, {HoldAll, Listable}];
symbolicConvert[num_] := Unevaluated[num] /. Power -> power

which replaces Power to power, and

log[power[base_, exp_]] := exp * log[base];

log[HoldPattern[Times[args__]]] := Total@Map[log, {args}];

log[(main : (_log*_power)) + rest_] :=  log[main] + log[1 + rest/main];

log[main_ + rest : log[1 + _]] := log[main] + log[1 + rest/main];

which is a function to perform the transformation I need. Here is an illustration:

start = symbolicConvert[2^3^2^3^5^8]

(* power[2, power[3, power[2, power[3, power[5, 8]]]]]  *)

and then

NestList[log, start,4]

enter image description here

where I used an image since it better shows the resulting structure. The main thing to note is that the log[1+something] part will be small in (almost) all cases, because the "something" will be quite small. Therefore, the idea is to compare the parts in the sum which do not involve this log, first. If they are equal, we can compare these logs.

This function will tell us how long we will have to nest the application of log:

getNestingLength[expr_power] := 
   Length[{expr /. power -> Sequence}] - 1; 

This is a helper function we will need to extract the dominant part:

getMain[main_ + log[1 + _]] := main;
getMain[x_ /; FreeQ[x, power]] := x;

This function will prepare our expressions for comparison:

SetAttributes[prep, HoldAll];
prep[fst_Power, sec_Power] :=
  With[{nest = Max[getNestingLength /@ #]},
     Map[Nest[log, #, nest] &, #]] &@symbolicConvert[{fst, sec}];

for the first examplein the question, this will produce:

prep[2^3^2^3^5^8, 3^2^2^7^6^7]

enter image description here

Note that so far, everything has been exact - while we represent the logs in this form, I did not employ any approximation yet.

Here is then the comparison function, which may be a bit ad hoc and might not cover all cases, but it worked on a few I tested:

less[fst_, sec_] /; And @@ Map[
          MatchQ[#, (_ + log[1 + _]) | (x_ /; FreeQ[x, power])] &, 
          {fst, sec}] && getMain[fst] =!= getMain[sec] :=
   getMain[fst] < getMain[sec] /. log -> (If[# <= 0, 0, Log[#]] &);

less[fst : (main_ + log[1 + fr_/rmain_]), sec : (main_ + log[1 + sr_/rmain_])] :=
   less[rmain + fr, rmain + sr];

less[a_log + b_/c_power, a_log + d_/c_power] := less[b, d]; 


less @@ prep[2^3^2^3^5^8, 3^2^2^7^6^7]

(* True *)

less @@ prep[10^3^4^5, 3^3^4^5]

(* False *)

less @@ prep[2^2^5^2^7^4^9^3^7^6^9^9^9^9^3^2, 3^3^6^3^9^4^2^3^2^2^2^2^2^3^3^3]

(* True *)


It may well be that the current implementation does contain some bugs or does not cover some cases, but I think that the main idea behind it should work. Note that my approach should work in most cases except when the bases are so huge that even their logs can overcome the powers they are divided over.

  • 3
    $\begingroup$ failing example: less @@ prep[2^4, 4^2] $\endgroup$ May 8, 2013 at 15:11
  • 4
    $\begingroup$ @LeonidShifrin: The result seems to be incorrect (True) in this case: less @@ prep[2^2^2^2^2^2^2^2^2^2^2^2^2^2^4^2^2^2, 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9]. I have not yet analyzed why. $\endgroup$ May 8, 2013 at 15:25
  • 1
    $\begingroup$ @VladimirReshetnikov It is interesting that slightly rewriting your example less @@ prep[2^2^2^2^2^2^2^2^2^2^2^2^2^2^4^16, 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9] gives a different result. I guess my approcimation breaks down when I take logs to many times. The "main" part of the log should be substantially larger than 1, while for this example I end up comparing 2 log[2] + log[log[2]] and log[log[9 log[9] + log[log[9]]]], both of which are really close to 1. I will add some condition for that. $\endgroup$ May 8, 2013 at 15:42
  • 1
    $\begingroup$ @LeonidShifrin You might want to publish your algorithm or just a link to this answer at math.stackexchange.com/questions/101138/… The +350 bounty ends in several hours and I think your algorithm is the best from all that were suggested and it looks having a polynomial complexity. $\endgroup$ May 14, 2013 at 17:13
  • 1
    $\begingroup$ @LeonidShifrin I awarded the bounty to your answer as the best and closest to a complete solution so far. I still cannot mark it as an accepted answer because it errs on some corner cases. I hope you will find a time to make it perfect! Thanks! $\endgroup$ Jul 17, 2013 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.