Which number is bigger?

Question

Define f(a,b) := a if b=1; a^f(a,b-1) if b>1 (Tetration, where ^ means power) for positive integers a and b, given four positive integers a,b,c,d, compare f(a,b) and f(c,d).

Your program should output three constant values to mean "greater", "less" and "equal".

Samples:

a b c d f(a,b) output f(c,d)
3 2 2 3 27     >      16
4 2 2 4 256    <      65536
4 1 2 2 4      =      4

Lowest time complexity to max{a,b,c,d} win, with tie-breaker code length(the shorter the better) and then answer time(the earlier the better).

Complexity assumption

• Your code should handle a,b,c,d up to 100, and your algorithm should handle all legal input
• You can assume integer calculations (that your language directly support) in O((a+b+c+d)^k) cost O(1) time if can be done in O(1) for 2k bit numbers if k bit computing can be done in O(1)
• For example, both plus(+) and multiply(*) can be done in O(1) for 2k bit numbers if k bit computing for both can be done in O(1), so both satisy the requirement. It's fine if multiply can't be done without plus, or even if both can't be done without each other.
• Float calculations in O(log(a+b+c+d)) bit precision in ±2^O((a+b+c+d)^k), takes O(1), with same requirements like integer calculations.

Answer 1

Java (JDK 10), 295 bytes

int f(Long a,long b,long c,long d){return a>c?-f(c,d,a,b):a<c?b>d?d==1?(a==2&((b==2&c==4)|(b==3&c==16)))|(a==3&b==2&c==27)?0:1:b-d>1?1:f(t(a,b),1,c,d):-1:a<2?0:a.signum(b-d);}long t(long a,long b){long t=1;for(;b-->0;)t=p(a,t);return t;}long p(long a,long b){long p=1;for(;b-->0;)p*=a;return p;}

Try it online!

Codes:

• 1 if a^^b > c^^d
• -1 if a^^b < c^^d
• 0 is a^^b == c^^d

Answer 2

APL (Dyalog Unicode), 30 19 bytes^SBCS

{f←*/⍴⍨⋄×(f/⍺)-f/⍵}

Try it online! Thanks to @ngn for saving 11 bytes by defining tetration in a much clever and shorter way:

f ← */⍴⍨   ⍝ Define f to be the tetration function
       ⍨   ⍝ Taking a on the right and b on the left, 
      ⍴    ⍝   creating an array of b occurrences of the number a
    */     ⍝ and then building the tower of exponentials.

Now if I have a vector with two integers, f/ applies the function to those two integers, e.g. f/ 2 4 gives 65536 and f/ 4 2 gives 256. We need this in our main function:

{f←*/⍴⍨⋄×(f/⍺)-f/⍵}  ⍝ Dyadic function (g) expecting two vectors of 2 integers, e.g. 4 2 g 2 4
{f←*/⍴⍨            }  ⍝ Define the auxiliar function as above
{      ⋄           }  ⍝ and then:
{              f/⍵}   ⍝ Apply aux function to the right vector of integers
{        (f/⍺)     }  ⍝ Apply aux function to the left vector of integers
{             -    }  ⍝ Subtract the two values and finally
{       ×          }  ⍝ get the sign of that difference.

This means my function returns 1 if the left integers give a larger value, 0 if they are the same or ¯1 if the left integers give a smaller value.

My original submission had a recursive definition of tetration:

{f←{⍵=1:⍺⋄⍺*⍺∇⍵-1}⋄×(f/⍺)-f/⍵}

with tetration as:

{               }  ⍝ Dyadic function expecting 2 integers
{⍵=1:⍺         }  ⍝ If the right argument is 1, return the left argument;
{      ⋄        }  ⍝ otherwise (separate previous statement from the next one)
{       ⍺*      }  ⍝ Take the left argument to the power of
{         ⍺∇⍵-1}  ⍝ the recursive call of this function with same left argument and decremented right argument.

Answer 3

Haskell, 46 bytes

a#1=a
a#b=a^a#(b-1)
(a!b)c d=compare(a#b)(c#d)

Prints GT for >, LT for < and EQfor =.

Try it online!