Implementazione alternativa della funzione Ackermann in C

Question

Ho scritto un programma in C che calcola i valori Ackermann per 2 numeri interi non negativi inseriti dall'utente. Il programma controlla se gli interi sono non negativi e se lo sono calcola il loro valore in Ackermann e poi chiede nuovi input o exit. Il programma funziona bene in C e non ho alcun problema con esso. Qui è il mio codice:

int ackermann(int m, int n){ 
     if (m == 0) return n + 1; 
     if (n == 0) return ackermann(m - 1, 1); 
     return ackermann(m - 1, ackermann(m, n - 1)); 
} 

ma, di fatto, per le esigenze di una lezione universitaria usiamo una versione modificata del C (fondamentalmente la stessa, ma con alcune differenti regole di sintassi), che simula la sintassi e le regole di Linguaggio assembly MIPS. Più in particolare, utilizziamo i registri per manipolare tutti i dati tranne che per gli array e le strutture. Inoltre, non possiamo usare i cicli while, while o do-while e usiamo invece se sono disponibili le istruzioni e goto. Così ho scritto il seguente programma in questa lingua (come ho detto non è più di C con sintassi diversa). Il mio problema è che funziona solo per gli input utente (x, 0) e (0, y) (xey sono numeri non negativi). Non funziona per (4,1), (3,2) e generalmente tutti gli input che non hanno zero. Capisco che non può funzionare in modo efficiente per numeri molto grandi come (10,10) a causa della vasta pila di questi calcoli. Ma voglio farlo funzionare per alcuni input semplici come Ackermann (3,1) == 13. Per ulteriori informazioni sulla funzione di Ackermann vedi prego questo: http://en.wikipedia.org/wiki/Ackermann_function Ecco il mio codice:

//Registers --- The basic difference from C is that we use registers to manipulate data 
int R0=0,R1,R2,R3,R4,R5,R6,R7,R8,R9,R10,R11,R12,R13,R14,R15,R16,R17,R18,R19,R20,R21, 
R22,R23,R24,R25,R26,R27,R28,R29,R30,R31; 

int ackermann(int m, int n){ 

    R4 = m; 
    R5 = n; 

    if(R4 != 0) 
     goto outer_else; 
    R6 = R5 + 1; 
    return R6; 

    outer_else: 
     if(R5 != 0) 
      goto inner_else; 
     R7 = R4 - 1; 
     R6 = ackermann(R7, 1); 
     return R6; 

     inner_else: 
      R8 = R5 - 1; 
      R9 = ackermann(R4, R8); 
      R10 = R4 - 1; 
      R6 = ackermann(R10, R9); 
      return R6; 
} 

Answer 1

Credo che il problema è che quei valori di registro sono definiti come variabili globali e vengono aggiornati da una chiamata interna a ackermann(), mentre una chiamata esterna dipende da quei valori che non cambiano. Ad esempio, dare un'occhiata alla clausola inner_else nella versione di registro di ackermann(): chiama ackermann(R4, R8) e nella successiva istruzione dipende dal valore corrente di R4 ma la chiamata ricorsiva altera l'impostazione di R4 prima che raggiunga l'istruzione di assegnazione.

Due soluzioni comuni:

1. Definire i tuoi registri come variabili locali e lasciare che il compilatore tenere traccia di ogni chiamata funzione di stato per voi.

2. All'ingresso della funzione ackermann(), salvare manualmente lo stato di tutti i registri e ripristinarlo in uscita.

Anche se la soluzione 1 è più facile, ho il sospetto che il tuo insegnante potrebbe preferire la soluzione 2, perché illustra il tipo di tecnica utilizzata da un compilatore a che fare con la gestione attuale registro nel suo codice assembly generato.