Czy istnieje skuteczna implementacja tetration?

Po niedawnym udzieleniu odpowiedzi na pytanie dotyczące funkcji Ackermana, której częścią jest funkcja obliczania tetracji liczby. Co skłoniło mnie do zastanowienia się, czy jest na to skuteczniejszy sposób. Zrobiłem kilka testów na własną rękę, ale jestem ograniczony głównie tym, że nawet liczba taka jak 5 ^^ 3 = 5^3125 podana 5^3 to w przybliżeniu 10^2, co oznacza 5^3125 ~ = 10^(3125 * 2/3) około 2000 cyfr.Czy istnieje skuteczna implementacja tetration?

Funkcja ta nie nadaje się do podziału i podbijać sposobów ze względu na charakter jak potęgowanie jest wykonywana, to znaczy:

2 ^^ 2^= 5 (2^(2^(2^2)))) = 2^(2^(2^4)) = 2^(2^16) = 2^65536 ~ = 10^(65536 * 3/10), czyli około 20 tys. Cyfr ...

Natura problemu, ponieważ zaczyna się na szczycie drzewa mocy i działa w dół, uderza mnie jako czynnik. Algorytm szybkiego zasilania może być oczywiście użyty do wykonania operacji potęgowania, ale nie jestem w stanie zobaczyć sposobu zmniejszenia liczby operacji potęgowania.

W przypadku gdy ktoś jest jasne, co mówię tutaj jest wiki article istocie chociaż tetracja jest:

^^ b = a^a^A ....^A, B razy, a następnie zaczynając potęgowanie w górnym elemencie drzewa mocy i praca w dół.

Algorytm obecnie używam byłoby (chociaż używam wersji rubinowy czy faktycznie chcę wartości):

long int Tetration(int number, int tetrate) 
{ 
    long int product=1; 
    if(tetrate==0) 
     return product; 
    product=number; 
    while(tetrate>1) 
    { 
     product=FastPower(number,product); 
     tetrate--; 
    } 
    return product; 
}

Wszelkie myśli będą mile widziane.

Źródło

2009-06-08 JSchlather

Myślę, że wiele zależy od tego, jakiego rodzaju reprezentacji numerycznej potrzebujesz. Czy potrzebujesz dokładnej reprezentacji całkowitej? Czy też przybliżona reprezentacja liczbowa (zmiennoprzecinkowa) jest wystarczająca? – RBarryYoung

To czysto pytanie z ciekawości, więc chciałbym zobaczyć, jak można napisać skuteczniejszy algorytm z reprezentacją zmiennoprzecinkową. – JSchlather

Spojrzałem na to, ale szybko zdałem sobie sprawę, że problem z liczbą cyfr całkowitych (który Dave wyjaśnia poniżej) będzie również nękał wykładnik dowolnego wyjścia funkcji tetracyjnej, tylko przy jednej rekursji mniej. Zasadniczo zmiennoprzecinkowe może obsługiwać produkty potęgowania, ponieważ jest to reprezentacja w formacie LOG. IMO, aby efektywnie obsługiwać produkty tetracyjne, musiałbyś opracować format oparty na superlogach. Brzmi to trudne, ale interesujące, może nawet tezę godną (w każdym razie Masters). – RBarryYoung

W przypadku tetration, jeśli ostateczna odpowiedź to cyfry d, wszystkie wyniki pośrednie są cyframi O (log d), w przeciwieństwie do O (d) cyfr z potęgowaniem. Ponieważ wyniki pośrednie dla tetration są tak małe w porównaniu do wyniku końcowego, nie ma oszczędności, które można uzyskać poprzez dzielenie i podbijanie. Jest również mało prawdopodobne, że istnieje użyteczny sposób na zapisywanie operacji potęgowania w jednostkowej pamięci RAM, ponieważ potęgowanie nie jest asocjacyjne.

Źródło

2009-06-09 01:42:30 Dave

Więc biorę to, że nie? – JSchlather

Szybki test potwierdza, można użyć tego samego typu SpeedUp jak dla algorytmu zasilania:

↑↑ 2b = (a^a)

a nawet bardziej ogólnie: ↑ ⁿ 2b = (a ↑ ⁿ⁻¹ a) ↑ ⁿ b

kod używany, aby to potwierdzić:

for(long a = 2; a < 5; a++) { 
     for(long b = 2; b < 5; b++) { 
      if(b%2 == 0) { 
       System.out.println(a+"↑↑"+b+"="+tetration(BigInteger.valueOf(a), BigInteger.valueOf(b))); 
       long pow = (long) Math.pow(a, a); // pow = tetration(a,2) 
       System.out.println(pow+"↑↑"+b/2+"="+tetration(BigInteger.valueOf(pow), BigInteger.valueOf(b/2))); 
      } 
     } 
    }

Źródło

2016-11-12 22:56:54 fejfo

-1

nie sądzę, że istnieje prosty sposób zrobić tetracja, Zrobiłem to:

<!DOCTYPE html> 
    <html> 
     <head> 
      <script> 
       var x = 1 
       //That is ▽ The Number You Are Powering// 
       var test = 3 
       var test2 = test 
       setInterval (function() { 
        // that is ▽ How many times you power it so this would be 3 tetra 3  which is 7625597484987// 
        if (x < 3) { 
         document.getElementById('test').innerHTML = test=test2**test 
         x++ 
        } 
       }, 1); 
      </script> 
      <p id="test">0</p>

Źródło

2016-12-08 15:37:59 derpman1

Czy możesz wyjaśnić, jak to działa? – sanastasiadis

Czy istnieje skuteczna implementacja tetration?

Odpowiedz

Powiązane problemy