In mathematics, tetration is the next hyper operator after exponentiation, and is defined as iterated exponentiation.

Addition (a succeeded n times)

Multiplication (a added to itself, n times)

Exponentiation (a multiplied by itself, n times)

Tetration (a exponentiated by itself, n times)

The inverse relations of tetration are called the super-root, and the super-logarithm. Your task is to write a program that, given A and B, prints out the Bnd-order super-root of A.

For example:

  • if A = 65,536 and B = 4 it prints 2
  • if A = 7,625,597,484,987 and B = 3 it prints 3

A and B are positive integers and the result must be floating point number with a precision of 5 digits after the decimal point. The result belongs to the real domain.

Be careful, super-roots may have many solutions.

  • 1
    \$\begingroup\$ Are there minimum/maximum bounds on the input numbers? Should a valid answer support floating point answers, or only integer? \$\endgroup\$
    – Josh
    Commented Feb 7, 2014 at 15:32
  • 3
    \$\begingroup\$ If multiple solutions, should the program find all or just one? \$\endgroup\$ Commented Feb 7, 2014 at 15:37
  • 5
    \$\begingroup\$ So what is your winning criteria? \$\endgroup\$
    – Mohammad
    Commented Feb 7, 2014 at 17:27
  • 2
    \$\begingroup\$ Can you give a simple example of a super-root that has more than one solution for a given A and B ≥ 1? \$\endgroup\$
    – Tobia
    Commented Feb 7, 2014 at 20:39
  • 1
    \$\begingroup\$ Can you give the mathematical representation of a super-root? I'm afraid I still don't understand how it is defined. \$\endgroup\$
    – user8777
    Commented Feb 11, 2014 at 2:30

10 Answers 10


C — aiming for clarity, didn't attempt to squeeze the code

Considering input:

A: A ∈ ℝ, A ≥ 1.0
B: B ∈ ℕ, B ≥ 1

Then there should usually be only one solution in ℝ, which simplifies the problem considerably.

Code is:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define TOLERANCE    1.0e-09

double tetrate(double, int);

int main(int argc, char **argv)
    double target, max, min, mid, working;
    int levels;

    if (argc == 3)
        target = atof(argv[1]); // A
        levels = atoi(argv[2]); // B

        // Shortcut if B == 1
        if (levels == 1)
            printf("%f\n", target);
            return 0;

        // Get a first approximation
        max = 2.0;
        while (tetrate(max, levels) < target)
            max *= 2.0;

        min = max / 2.0;

        // printf("Answer is between %g and %g\n", min, max);

        // Use bisection to get a closer approximation
            mid = (min + max) / 2.0;
            working = tetrate(mid, levels);
            if (working > target)
                max = mid;
            else if (working < target)
                min = mid;
        while (max - min > TOLERANCE);

        // printf("%g: %f = %f tetrate %d\n", target, tetrate(mid, levels), mid, levels);
        printf("%f\n", mid);

    return 0;

double tetrate(double d, int i)
    double result = d;

    // If the result is already infinite, don't tetrate any more
    while (--i && isfinite(result))
        result = pow(d, result);

    return result;

To compile:

gcc -o tet_root tet_root.c -lm

To run:

./tet_root A B



$ ./tet_root 65536 4


$ ./tet_root 7625597484987 3


$ ./tet_root 1.340164183e18 3

n(2½) ➙ 2 as n ➙ ∞ ? (well known limit)

$ ./tet_root 2 10

$ ./tet_root 2 100

$ ./tet_root 2 1000


n(e1/e) ➙ ∞ as n ➙ ∞ ? (upper bounds)

$ ./tet_root 9.999999999e199 100

$ ./tet_root 9.999999999e199 1000

$ ./tet_root 9.999999999e199 10000

$ ./tet_root 9.999999999e199 100000

Cool! (e1/e ≅ 1.44466786101...)

  • \$\begingroup\$ You actually know a lot about math I can tell :) (This answer) ∈ (ℝeally impressive stuff) \$\endgroup\$ Commented Feb 16, 2014 at 23:19
  • \$\begingroup\$ @AlbertRenshaw This is just an implementation of bisection. Not very hard at all. \$\endgroup\$ Commented Aug 8, 2019 at 18:22

Python, 87 chars

E=lambda x,n:x**E(x,n-1)if n else 1
def S(A,B):
 while E(x,B)<A:x+=1e-5
 return x

A simple linear search for the answer.

Off-topic, but what the *#$(@! is up with the python ** operator?

>>> 1e200*1e200
>>> 1e200**2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')
  • \$\begingroup\$ Worthy of a bug report? \$\endgroup\$
    – Josh
    Commented Feb 7, 2014 at 18:49
  • \$\begingroup\$ Is associativity getting in the way? Perhaps you are comparing (1e200)**2 to 1e(200**2)? \$\endgroup\$
    – danmcardle
    Commented Feb 7, 2014 at 20:36
  • 2
    \$\begingroup\$ @Josh: I reported a bug: bugs.python.org/issue20543 Basically, working as intended - they are not much for IEEE float. If they were to fix anything, it would be to generate an OverflowError in the first case. \$\endgroup\$ Commented Feb 8, 2014 at 1:17

Mathematica, 35 40

n /. Solve[Nest[#^(1/n) &, a, b] == n]~N~5

Generates a list of all solutions, with 5 digit precision.

n /. Last@Solve[Nest[#^(1/n) &, a, b] == n]~N~5

5 more characters to get only the real solution, which the updated rules demand.


When did this become a code golf? I thought it was a code challenge to come up with the best algorithm!

APL, 33 chars


This is a simple linear search, starting from C = 1 + 10-6 and incrementing it by 10-6 until
    logC logC logC ⋯ A ≤ 1
where the logC function is applied recursively B times.


      4 {r←⍵⋄⍺{1≥⍵⍟⍣⍺⊢r:⍵⋄⍺∇⍵+i}1+i←1e¯6} 65536
      3 {r←⍵⋄⍺{1≥⍵⍟⍣⍺⊢r:⍵⋄⍺∇⍵+i}1+i←1e¯6} 7625597484987

This code is very slow, but for small bases such as 2 or 3 it completes in a few seconds. See below for a better thing.

APL, logarithmic complexity

Actually linear complexity on the root order, logarithmic on the result size and precision:

    time = O(B × log(C) + B × log(D))

where B is the root order, C is the tetration base being asked for, and D is the number of digits of precision asked. This complexity is my intuitive understanding, I have not produced a formal proof.

This algorithm does not require big integers, it only uses the log function on regular floating point numbers, therefore it's quite efficient on very large numbers, up to the limit of the floating point implementation (either double precision, or arbitrary large FP numbers on the APL implementations that offer them.)

The precision of the result can be controlled by setting ⎕CT (comparison tolerance) to the desired acceptable error (on my system it defaults to 1e¯14, roughly 14 decimal digits)

sroot←{              ⍝ Compute the ⍺-th order super-root of ⍵:
  n←⍺ ⋄ r←⍵          ⍝ n is the order, r is the result of the tetration.
  u←{                ⍝ Compute u, the upper bound, a base ≥ the expected result:
    1≥⍵⍟⍣n⊢r:⍵       ⍝   apply ⍵⍟ (log base ⍵) n times; if ≤1 then upper bound found
    ∇2×⍵             ⍝   otherwise double the base and recurse
  }2                 ⍝ start the search with ⍵=2 as a first guess.
  (u÷2){             ⍝ Perform a binary search (bisection) to refine the base:
    b←(⍺+⍵)÷2        ⍝   b is the middle point between ⍺ and ⍵
    t←b⍟⍣n⊢r         ⍝   t is the result of applying b⍟ n times, starting with r;
    t=1:b            ⍝   if t=1 (under ⎕CT), then b is the super-root wanted;
    t<1:⍺∇b          ⍝   if t<1, recurse between ⍺ and b
    b∇⍵              ⍝   otherwise (t>1) returse between b and ⍵
  }u                 ⍝ begin the search between u as found earlier and its half.

I'm not sure whether 1≥⍵⍟⍣n above could fail with a Domain Error (because the log of a negative argument could either fail immediately, or give a complex result, which would not be in the domain of ) but I haven't been able to find a case that fails.


      4 sroot 65536
      4 sroot 65537
      3 sroot 7625597484987
      3 sroot 7625597400000
      3 sroot 7625597500000

'3' comes out as an exact value because it happens to be one of the values directly hit by the binary search (starting from 2, doubled to 4, bisect to 3). In the general case that does not happen, so the result will approximate the root value with a ⎕CT error (more precisely, the logarithmic test of every candidate base is performed with ⎕CT tolerance.)



julia> t(a,b)=(c=a;for j=1:b-1;c=a^c;end;c)
julia> s(c,b)=(i=1;while t(i,b)!=c;i+=1;end;i)
julia> s(65536,4)
julia> s(7625597484987,3)     

Ignored floating point instruction since the the question only defines behavior for integers.


Ruby, 79 bytes

->a,b{x=y=1.0;z=a;eval"y=(x+z)/2;x,z=a<eval('y**'*~-b+?y)?[x,y]:[y,z];"*99;p y}

This is the same as the below program, but less accurate since it only runs 99 loops.

Ruby, 87 bytes

->a,b{x=y=1.0;z=a;(y=(x+z)/2;x,z=a<eval("y**"*~-b+?y)?[x,y]:[y,z])while y!=(x+z)/2;p y}

Try it online

This is simply bisection. Ungolfed:

-> a, b {
    # y^^b by evaluating the string "y ** y ** ..."
    tetration =-> y {eval "y ** " * (b-1) + ?y}
    lower = middle = 1.0
    upper = a
    while middle != (lower + upper) / 2 do
        middle = (lower + upper) / 2
        if tetration[middle] > a
            upper = middle
            lower = middle
    print middle

k [52 chars]

{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}

A modified version of my own post nth root


{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}[7625597484987;3]

{{{((%x)*(z*x-1)+y%z xexp x-1)}[x;y]/[2]}[y]/[y<;x]}[65536;4]


Simple linear search, returns first, smallest match found.

    The value of a is the result of exponentiating b some number of times.
    This function computes that number.
superRoot a b = head [x | x<-[2..a], tetrate x b == a]

    compute b^b^...^b repeated n times
tetrate b 1 = b
tetrate b n = b^(tetrate b (n-1))


*Main> superRoot 65536 4
*Main> superRoot 7625597484987 3

Mathematica, 41 bytes without optimization

Mathematica was basically invented to solve problems like this. One easy solution is to construct the problem as a nested power series and pass it to the built-in Reduce function, which seeks analytical solutions to equations. As a result, the following, in addition to being unusually concise code, is also not brute force.

Reduce[Nest[Power[#, 1/x] &, a, b] == x, x, Reals]

You can remove the restriction to provide only Real number solutions if you're patient and want to save six bytes. You can also express some of the nested functions in abbreviated form to save a few more bytes. As given, it returns thusly

enter image description here


05AB1E, 16 bytes


Port of @KeithRandall's Python answer.

Try it online.


1                 # Push a 1
 [                # Start an infinite loop:
  Ð               #  Triplicate the top value on the stack
   U              #  Pop and store one in variable `X`
    ²F            #  Inner loop the second input amount of times:
      Xm          #   And take the top value to the power `X`
        }         #  After the inner loop:
         ¹@       #  If the resulting value is larger than or equal to the first input:
           #      #   Stop the infinite loop
                  #   (after which the top of the stack is output implicitly as result)
            5(°+  #  If not: increase the top value by 10^-5

ÐU²FXm} could also be D²>и.»m for the same byte-count:

  D               #   Duplicate the top value on the stack
   ²>             #   Push the second input + 1
     и            #   Repeat the top value that many times as list
      .»          #   Reduce it by:
        m         #    Taking the power

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.