W matematyce tetracja to kolejny hiperoperator po potęgowaniu i jest definiowany jako potęgowanie iterowane.

Dodatek ( udało n razy)

Mnożenie ( dodaje się do siebie, n razy)

Potęgowanie ( mnożone przez siebie, n razy)

Tetracja ( potęgowania przez siebie, n razy)

Odwrotne relacje tetracji nazywane są super-rootem i super-logarytmem. Twoim zadaniem jest napisanie programu, który, biorąc pod uwagę A i B, wypisuje super-root B- ^drugiego rzędu A.

Na przykład:

• jeśli A = 65,536i B = 4drukuje2
• jeśli A = 7,625,597,484,987i B = 3drukuje3

A i B są dodatnimi liczbami całkowitymi, a wynik musi być liczbą zmiennoprzecinkową z dokładnością do 5 cyfr po przecinku. Wynik należy do prawdziwej domeny.

Uważaj, super-root może mieć wiele rozwiązań.

C - dążąc do przejrzystości, nie próbował ścisnąć kodu

Biorąc pod uwagę wkład:

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

Wtedy zwykle powinno być tylko jedno rozwiązanie w ℝ, co znacznie upraszcza problem.

Kod to:

#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;
}

Kompilować:

gcc -o tet_root tet_root.c -lm

Biegać:

./tet_root A B

Na przykład:

⁴ 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 ➙ ∞? (dobrze znany limit)

$ ./tet_root 2 10
1.416190

$ ./tet_root 2 100
1.414214

$ ./tet_root 2 1000
1.414214

Tak!

ⁿ (e ^{1 / e} ) ➙ ∞ as n ➙ ∞? (górne granice)

$ ./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

Fajne! (e ^{1 / e} ≅ 1,44466786101 ...)

Python, 87 znaków

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

Proste liniowe wyszukiwanie odpowiedzi.

Nie na temat, ale co * * $ (@! Działa z **operatorem python ?

>>> 1e200*1e200
inf
>>> 1e200**2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')

Mathematica, 35 40

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

Generuje listę wszystkich rozwiązań z dokładnością do 5 cyfr.

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

5 kolejnych postaci, aby uzyskać tylko prawdziwe rozwiązanie, którego wymagają zaktualizowane zasady.

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

Zignorowano instrukcję zmiennoprzecinkową, ponieważ pytanie określa tylko zachowanie liczb całkowitych.

Kiedy to stało się golfem kodowym? Pomyślałem, że wymyślenie najlepszego algorytmu to wyzwanie.

golf-golf

APL, 33 znaki

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

Jest to proste wyszukiwanie liniowe, zaczynające się od C = 1 + ^10-6 i zwiększające go o 10 ^-6, aż do
    log _C log _C log _C ⋯ A ≤ 1,
gdy funkcja log _C jest stosowana rekurencyjnie B razy.

Przykłady

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

Ten kod jest bardzo wolny, ale dla małych baz, takich jak 2 lub 3, kończy się w kilka sekund. Zobacz poniżej lepszą rzecz.

kod-wyzwanie

APL, złożoność logarytmiczna

Właściwie liniowa złożoność w kolejności pierwiastkowej, logarytmiczna w stosunku do wielkości wyniku i precyzji:

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

gdzie B jest porządkiem pierwiastka, C jest pytaną o bazę tetracji, a D jest liczbą zadawanych cyfr precyzji. Ta złożoność jest moim intuicyjnym zrozumieniem, nie przedstawiłem formalnego dowodu.

Algorytm ten nie wymaga dużych liczb całkowitych, używa tylko funkcji logu na zwykłych liczbach zmiennoprzecinkowych, dlatego jest dość wydajny na bardzo dużych liczbach, aż do limitu implementacji liczb zmiennoprzecinkowych (albo podwójna precyzja, albo dowolne duże liczby FP na Implementacje APL, które je oferują).

Precyzja wyniku może być kontrolowana poprzez ustawienie ⎕CT(tolerancji porównania) pożądanego dopuszczalnego błędu (w moim systemie domyślnie jest to 1e¯14, około 14 cyfr dziesiętnych)

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.
}

Nie jestem pewien, czy 1≥⍵⍟⍣npowyższe może zawieść z błędem domeny (ponieważ dziennik argumentu ujemnego może albo zawieść natychmiast, albo dać złożony wynik, którego nie byłoby w domenie ≥), ale nie byłem w stanie znaleźć przypadek, który zawodzi.

Przykłady

      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” pojawia się jako dokładna wartość, ponieważ zdarza się, że jest to jedna z wartości bezpośrednio dotkniętych przez wyszukiwanie binarne (od 2, podwojona do 4, dwusieczna do 3). W ogólnym przypadku tak się nie dzieje, więc wynik aproksymuje wartość pierwiastkową z błędem moreCT (a dokładniej, test logarytmiczny każdej kandydującej bazy przeprowadzany jest z tolerancją ⎕CT).

Rubinowy, 79 bajtów

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

Jest to to samo, co poniższy program, ale mniej dokładne, ponieważ uruchamia tylko 99 pętli.

Rubinowy, 87 bajtów

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

Wypróbuj online

To jest po prostu bisekcja. Nie golfowany:

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

k [52 znaki]

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

Zmodyfikowana wersja moim poście n ^-tego pierwiastka

Przykład:

{{{((%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

Haskell

Proste wyszukiwanie liniowe, zwraca pierwsze, najmniejsze znalezione dopasowanie.

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

Przykład

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

Mathematica, 41 bajtów bez optymalizacji

Mathematica została po prostu wymyślona w celu rozwiązania takich problemów. Jednym łatwym rozwiązaniem jest skonstruowanie problemu jako zagnieżdżonej serii mocy i przekazanie go do wbudowanej Reducefunkcji, która szuka analitycznych rozwiązań równań. W rezultacie, oprócz tego, że kod jest niezwykle zwięzły, nie jest też brutalną siłą.

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

Możesz usunąć to ograniczenie, aby zapewnić tylko rozwiązania liczb rzeczywistych, jeśli jesteś cierpliwy i chcesz zaoszczędzić sześć bajtów. Możesz również wyrazić niektóre z zagnieżdżonych funkcji w formie skróconej, aby zaoszczędzić jeszcze kilka bajtów. Jak podano, wraca w ten sposób

05AB1E , 16 bajtów

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

Port odpowiedzi Python @KeithRandall .

Wypróbuj online.

Wyjaśnienie:

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}może być również D²>и.»mdla tej samej liczby bajtów:

  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