Gibt es eine effiziente Implementierung von Tetration?

Nach kurzem Beantworten einer Frage, die die Ackerman-Funktion beinhaltete, von der ein Teil eine Funktion zum Berechnen der Tetration einer Zahl beinhaltete. Was mich dazu brachte, darüber nachzudenken, ob es einen effizienteren Weg dafür gab. Ich habe selbst einige Tests gemacht, aber ich beschränke mich hauptsächlich auf die Tatsache, dass sogar eine Zahl wie 5 ^^ 3 = 5^3125 gegeben 5^3 ungefähr 10^2 ist, also 5^3125 ~ = 10^(3125 * 2/3) um 2000 Ziffern.Gibt es eine effiziente Implementierung von Tetration?

Die Funktion eignet sich nicht Methoden auf Grund der Natur des zu unterteilen und zu erobern, wie der Potenzierung ausgeführt wird, das heißt:

2 ^^ 5 = 2^(2^(2^(2^2)))) = 2^(2^(2^4)) = 2^(2^16) = 2^65536 ~ = 10^(65536 * 3/10) also etwa 20k Ziffern ...

Die Natur des Problems, da es an der Spitze des Machtbaums beginnt und es nach unten bearbeitet, erscheint mir als Faktor. Ein schneller Leistungsalgorithmus kann verwendet werden, um die Exponentierungsoperation offensichtlich auszuführen, aber ich war nicht in der Lage, eine Möglichkeit zu sehen, die Anzahl der Potenzierungsoperationen zu verringern.

Falls jemand ist unklar, was ich rede hier ist die wiki article, im Wesentlichen obwohl tetration ist:

a ^^ b = a^a^a ....^a, b-mal und dann starten die Potenzierung am obersten Element des Potenzbaums und Abarbeiten.

Der Algorithmus Ich bin zur Zeit wäre mit (obwohl ich eine Ruby-Version bin mit, wenn ich tatsächlich Werte wollen):

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

Irgendwelche Gedanken geschätzt würde.

Quelle

2009-06-08 JSchlather

Ich denke, dass eine Menge davon abhängt, welche Art von numerischer Darstellung Sie benötigen. Brauchen Sie eine exakte Integer-Darstellung? Oder ist eine ungefähre numerische (Gleitkomma-) Darstellung ausreichend? – RBarryYoung

Es ist nur eine Frage aus Neugier, also wäre ich gespannt, wie Sie einen effizienteren Algorithmus mit Gleitkommadarstellung schreiben könnten. – JSchlather

Ich habe mir das angeschaut, aber ich habe schnell gemerkt, dass das Problem der Integer-Ziffernlänge (das Dave unten erklärt) auch den Exponenten einer Tetrationsfunktionsausgabe betrifft, nur bei einer Rekursion weniger. Floating-Point kann Exponentiationsprodukte verarbeiten, da es sich um eine LOG-formatierte Darstellung handelt. IMO, um Tetration-Produkte effizient zu handhaben, müssten Sie ein SuperLog-basiertes Format entwickeln. Das klingt schwierig, aber interessant, vielleicht sogar These wert (Masters sowieso). – RBarryYoung

Mit Tetration, wenn die endgültige Antwort d Ziffern ist, dann sind alle Zwischenergebnisse O (log d) Ziffern, im Gegensatz zu O (d) Ziffern mit Potenzierung. Da die Zwischenergebnisse für die Tetration im Vergleich zum Endergebnis so gering sind, gibt es keine Einsparungen durch Divide and Conquer. Es ist auch unwahrscheinlich, dass es eine nützliche Möglichkeit gibt, Exponentierungsoperationen in einem Einheitskosten-RAM zu speichern, da die Potenzierung nicht assoziativ ist.

Quelle

2009-06-09 01:42:30 Dave

Also nehme ich das ist ein Nein? – JSchlather

Ein schneller Test bestätigt Sie die gleiche Art von Speedup wie für den Leistungs Algorithmus verwenden:

ein ↑↑ 2b = (a^a)

und noch allgemeiner: a ↑ ⁿ 2b = (a ↑ ⁿ⁻¹ a) ↑ ⁿ b

Code verwendet, dies zu bestätigen:

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

Quelle

2016-11-12 22:56:54 fejfo

-1

ich denke nicht, dass es eine einfache Möglichkeit ist tetration zu tun, Also tat ich das:

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

Quelle

2016-12-08 15:37:59 derpman1

Können Sie erklären, wie es ein bisschen funktioniert? – sanastasiadis

Gibt es eine effiziente Implementierung von Tetration?

Antwort

Verwandte Themen