Calculate the super root of a number

Question

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 B^nd-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.

Answer 1

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
        do
        {
            mid = (min + max) / 2.0;
            working = tetrate(mid, levels);
            if (working > target)
                max = mid;
            else if (working < target)
                min = mid;
            else
                break;
        }
        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

E.g.:

⁴2

$ ./tet_root 65536 4
2.000000

³3

$ ./tet_root 7625597484987 3
3.000000

³π

$ ./tet_root 1.340164183e18 3
3.141593

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

$ ./tet_root 2 10
1.416190

$ ./tet_root 2 100
1.414214

$ ./tet_root 2 1000
1.414214

Yes!

ⁿ(e^1/e) ➙ ∞ as n ➙ ∞ ? (upper bounds)

$ ./tet_root 9.999999999e199 100
1.445700

$ ./tet_root 9.999999999e199 1000
1.444678

$ ./tet_root 9.999999999e199 10000
1.444668

$ ./tet_root 9.999999999e199 100000
1.444668

Cool! (e^1/e ≅ 1.44466786101...)

Answer 2

Python, 87 chars

E=lambda x,n:x**E(x,n-1)if n else 1
def S(A,B):
 x=1.
 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
inf
>>> 1e200**2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')

Answer 3

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.

Answer 4

Julia

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)
2
julia> s(7625597484987,3)     
3

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

Answer 5

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

---

code-golf

APL, 33 chars

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

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

Examples

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

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.

---

code-challenge

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.

Examples

      4 sroot 65536
1.9999999999999964
      4 sroot 65537
2.000000185530773
      3 sroot 7625597484987
3
      3 sroot 7625597400000
2.999999999843567
      3 sroot 7625597500000
3.000000000027626

'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.)

Answer 6

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
        else
            lower = middle
        end
    end

    print middle
}

Answer 7

05AB1E, 16 bytes

1[ÐU²FXm}¹@#5(°+

Port of @KeithRandall's Python answer.

Try it online.

Explanation:

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

Answer 8

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 n^th root

Example:

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

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

Answer 9

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

Answer 10

Haskell

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))

Example

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