Esiste un'implementazione efficiente della tetration?

Dopo aver recentemente rispondendo ad una domanda che coinvolge la funzione parte Ackerman di che ha coinvolto una funzione per il calcolo del tetrazione di un numero. Il che mi ha portato a riflettere se esistesse un modo più efficiente per farlo. Ho fatto alcuni test da sola, ma ho limitato principalmente per il fatto che anche un numero, ad esempio 5 ^^ 3 = 5^3125 data 5^3 è circa il 10^2, che significa 5^3125 ~ = 10^(3125 * 2/3) circa 2000 cifre.Esiste un'implementazione efficiente della tetration?

La funzione non si presta a dividere e conquistare metodi a causa della natura di come l'esponente è ottenuto, ossia:

2 ^^ 5 = 2^(2^(2^(2^2)))) = 2^(2^(2^4)) = 2^(2^16) = 2^65536 ~ = 10^(65536 * 3/10) quindi circa 20k cifre ...

La natura del problema, dal momento che inizia nella parte superiore dell'albero del potere e funziona in basso, mi sembra fattoriale. Un algoritmo di potenza veloce può essere utilizzato per eseguire l'operazione exponentiation ovviamente, ma non sono stati in grado di vedere un modo per ridurre il numero di operazioni di elevazione a potenza.

Nel caso qualcuno non è chiaro che cosa sto parlando qui è la wiki article, in sostanza, se tetrazione è:

un ^^ b = a^a^A ....^a, b volte e poi a partire l'esponenziazione nell'elemento più in alto dell'albero di potere e in giù.

L'algoritmo Attualmente sto usando sarebbe (anche se sto utilizzando una versione rubino se io in realtà voglio valori):

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

Ogni pensiero sarebbe apprezzato.

fonte

2009-06-08 JSchlather

Penso che molto dipenda dal tipo di rappresentazione numerica di cui hai bisogno. Hai bisogno di una rappresentazione intera esatta? O è sufficiente una rappresentazione numerica approssimativa (virgola mobile)? – RBarryYoung

E 'puramente una domanda per curiosità, così sarei curioso di vedere come si potrebbe scrivere un algoritmo più efficiente con galleggianti rappresentazione in virgola. – JSchlather

ho guardato in questo, ma presto si rese conto che il problema lunghezza cifre intere (che Dave spiega qui di seguito) sarà anche affliggere l'esponente di qualsiasi emissione di funzioni tetrazione, proprio in un ricorsione meno. Fondamentalmente, la virgola mobile può gestire i prodotti di esponenziazione perché è una rappresentazione formattata LOG. IMO, per gestire in modo efficiente i prodotti di tetration, è necessario sviluppare un formato basato su superLog. Sembra difficile ma interessante, forse anche una tesi degna (maestri comunque). – RBarryYoung

Con tetrazione, se la risposta finale d cifre, quindi tutti i risultati intermedi sono O (log d) cifre, al contrario di O (d) cifre con esponenziazione. Poiché i risultati intermedi per la tetratura sono così piccoli rispetto al risultato finale, non ci sono risparmi da ottenere tramite divide et impera. È anche improbabile che ci sia un modo utile per salvare le operazioni di esponenziazione in una RAM a costo unitario, poiché l'esponenziazione non è associativa.

fonte

2009-06-09 01:42:30 Dave

Quindi ho capito che è un no? – JSchlather

Un test rapido conferma è possibile utilizzare lo stesso tipo di aumento di velocità, come per l'algoritmo di potenza:

un ↑↑ 2b = (a^a)

e ancora più generale: una ↑ ⁿ 2b = (a ↑ ⁿ⁻¹ a) ↑ ⁿ b

codice utilizzato per confermarlo:

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

fonte

2016-11-12 22:56:54 fejfo

-1

non credo che ci sia un modo semplice per fare tetrazione, Così ho fatto questo:

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

fonte

2016-12-08 15:37:59 derpman1

Puoi spiegare come funziona un po '? – sanastasiadis

Esiste un'implementazione efficiente della tetration?

risposta

Problemi correlati