calcolo dei valori più grandi della funzione di Ackermann

Question

ho qualche codice:

int CalculateAckermann(int x, int y) 
{ 
    if(!x) 
    { 
     return y++; 
    } 
    if(!y) 
    { 
     return CalculateAckermann(x--,1); 
    } 
    else 
    { 
     return CalculateAckermann(x--, CalculateAckermann(x, y--)); 
    } 
} 

progettato per calcolare la funzione di Ackermann. Sopra un numero piuttosto basso di xey l'applicazione provoca uno stack overflow perché ricorre troppo profondamente e genera numeri piuttosto grandi. Come faccio a calcolare lentamente una soluzione?

Answer 1

Come nota, se si desidera utilizzare solo il modulo chiuso, gli algoritmi per m < 4 sono semplici. Se desideri estendere alla tetration, ti suggerisco di scrivere un algoritmo fastpower usando probabilmente il metodo binario e quindi con quel metodo puoi scrivere una funzione di tetration. Quale sarebbe simile:

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

Poi si può coprire casi fino a n == 4 e dopo che usare la definizione ricorsiva ei valori di un overflow (5, n) ad un tasso ridicolo, quindi è davvero di nessuna preoccupazione. Sebbene il tuo insegnante probabilmente non sarà soddisfatto con un algoritmo come questo, ma funzionerà molto più velocemente. In una delle mie classi discrete quando ho chiesto di scrivere un algoritmo per calcolare i numeri di Fibonacci e poi trovare la sua O (n), ho scritto la forma chiusa e poi ho scritto O (1) e ho ottenuto pieno credito, alcuni professori apprezzavano risposte intelligenti.

Ciò che è importante notare della funzione Ackerman è essenzialmente definire l'heirachy delle funzioni additive sugli interi, A (1, n) è addizione, A (2, n) è moltiplicazione, A (3, n) è l'esponenziazione, A (4, n) è tetrazione e dopo il 5 le funzioni crescono troppo velocemente per essere applicabili a molto.

Un altro modo di guardare addizione, moltiplicazione, etc è:

Φ0 (x, y) = y + 1 
Φ1 (x, y) = +(x, y) 
Φ2 (x, y) = ×(x, y) 
Φ3 (x, y) = ↑ (x, y) 
Φ4 (x, y) = ↑↑ (x, y) 
      = Φ4 (x, 0) = 1 if y = 0 
      = Φ4 (x, y + 1) = Φ3 (x, Φ4 (x, y)) for y > 0 

(Usa prefisso notazione cioè + (x, y) = x + y, (x, y) = x y.

Answer 2

È necessario pre-decrementare, non post-decrementare, o si stanno solo passando gli stessi valori di xey alla funzione in ogni punto. Si consiglia inoltre di creare alcune sicurezze per assicurarsi di non avere parametri negativi poiché la funzione Ackerman non è definita se xey è negativo.

int CalculateAckermann(int x, int y) 
{ 
    if (x < 0 || y < 0) 
    { 
     abort(); 
    } 

    if(x == 0) 
    { 
     return y+1; 
    } 
    if(y == 0) 
    { 
     return CalculateAckermann(x-1,1); 
    } 
    else 
    { 
     return CalculateAckermann(x-1, CalculateAckermann(x, y-1)); 
    } 
} 

Answer 3

(si sente come una questione compiti a casa, ma io ti risponderò comunque ...)

Leggi un po 'di più sulla funzione di Ackermann. Per exmaple, il WikiPedia article dice

"Il suo valore cresce rapidamente, anche per piccoli ingressi. Ad esempio A (4,2) è un numero intero da 19.729 cifre decimali".

Ho il sospetto che i numeri interi a 32 bit (o 64 bit, a seconda dell'architettura) siano straripanti e che tu stia entrando in loop infiniti a causa di questi problemi. Il semplice debug in stile printf mostrerebbe gli overflow interi. Se vuoi effettivamente calcolare la funzione Ackermann, dovrai usare una libreria bignum di precisione infinita, come GNU MP.

Inoltre, leggere su Tail Recursion e come ottimizzarlo.

Answer 4

IIRC, una proprietà interessante della funzione Ackermann è che la profondità massima dello stack necessaria per valutarla (in livelli di chiamate) è la stessa della risposta alla funzione. Ciò significa che ci saranno dei limiti severi sul calcolo effettivo che può essere fatto, imposto dai limiti della memoria virtuale del tuo hardware. Non è sufficiente avere un pacchetto aritmetico multi-precisione; hai rapidamente bisogno di più bit per memorizzare i logaritmi dei logaritmi dei numeri di quante siano le particelle subatomiche nell'universo.

Ancora, IIRC, è possibile derivare formule relativamente semplici chiuse per A (1, N), A (2, N) e A (3, N), lungo le linee di seguito (mi sembra di ricordare 3 calcolando nella risposta, ma i dettagli sono probabilmente errata):

• a (1, N) = 3 + N
• a (2, n) = 3 * N
• a (3, N) = 3^N

La formula per A (4, N) prevede alcuni movimenti a mano e impilamento degli esponenti N-profondità. La formula per A (5, N) implica quindi l'impilamento delle formule per A (4, N) ... diventa dannatamente strano e costoso molto rapidamente.

Man mano che le formule diventano più complesse, il calcolo diventa completamente ingestibile.

---

L'articolo di Wikipedia sul Ackermann function comprende una sezione 'Tabella dei valori'.La mia memoria è arrugginito (ma era 20 anni fa ho ultimo guardato questo in dettaglio), e dà le formule chiuse:

• A (0, N) = N + 1
• A (1 , N) = 2 + (N + 3) - 3
• A (2, N) = 2 * (N + 3) - 3
• A (3, N) = 2^(N + 3) - 3

E A (4, N) = 2^2^2^... - 3 (dove 2 è elevato alla potenza di 2, N + 3 volte).