Come posso evitare che la funzione Ackerman trabocchi dallo stack?

Question

C'è un modo per mantenere la mia funzione Ackerman dalla creazione di una pila sul flusso è lo fa per numeri relativamente piccoli, vale a dire (4,2). Questo è l'errore

{Impossibile valutare l'espressione perché il thread corrente è in una pila stato di troppo pieno.}

private void Button1Click(object sender, EventArgs e) 
     { 
      var t = Ackermann(4,2); 
      label1.Text += string.Format(": {0}", t); 
      label1.Visible = true; 
     } 

     int Ackermann(uint m, uint n) 
     { 
      if (m == 0) 
       return (int) (n+1); 
      if (m > 0 && n == 0) 
       return Ackermann(m - 1, 1); 
      if (m > 0 && n > 0) 
       return Ackermann(m - 1, (uint)Ackermann(m, n - 1)); 
      else 
      { 
       return -1; 
      } 
     } 

Answer 1

Il modo migliore per evitare StackOverflowException è non utilizzare lo stack.

Eliminiamo il caso negativo, poiché è privo di significato quando chiamiamo con uint. In alternativa, ciò che segue qui funziona anche se facciamo il test negativo la prima cosa che nel metodo, prima che le altre possibilità sono considerati:

In primo luogo, stiamo andando ad avere bisogno di una barca più grande:

public static BigInteger Ackermann(BigInteger m, BigInteger n) 
    { 
     if (m == 0) 
      return n+1; 
     if (n == 0) 
      return Ackermann(m - 1, 1); 
     else 
      return Ackermann(m - 1, Ackermann(m, n - 1)); 
    } 

Ora il successo è almeno matematicamente possibile. Ora, il caso n == 0 è un richiamo di coda abbastanza semplice. Eliminiamolo a mano. Useremo goto perché è temporanea, in modo che non si deve preoccupare velociraptor o Dijkstra:

public static BigInteger Ackermann(BigInteger m, BigInteger n) 
    { 
    restart: 
     if (m == 0) 
      return n+1; 
     if (n == 0) 
     { 
      m--; 
      n = 1; 
      goto restart; 
     } 
     else 
      return Ackermann(m - 1, Ackermann(m, n - 1)); 
    } 

Questo sarà già prendere un po 'di più per far saltare lo stack, ma saltare in aria, lo farà. Guardando questo modulo però, notare che m non viene mai impostato dal ritorno di una chiamata ricorsiva, mentre a volte lo è n.

Estendendo questo, possiamo trasformare questo in una forma iterativa, mentre solo avere a che fare con il monitoraggio valori precedenti di m, e dove ci piacerebbe tornare in forma ricorsiva, abbiamo assegnare al n il nostro modulo iterativo. Una volta che siamo a corto di m s in attesa di essere affrontato, torniamo il valore corrente di n:

public static BigInteger Ackermann(BigInteger m, BigInteger n) 
    { 
     Stack<BigInteger> stack = new Stack<BigInteger>(); 
     stack.Push(m); 
     while(stack.Count != 0) 
     { 
      m = stack.Pop(); 
      if(m == 0) 
       n = n + 1; 
      else if(n == 0) 
      { 
       stack.Push(m - 1); 
       n = 1; 
      } 
      else 
      { 
       stack.Push(m - 1); 
       stack.Push(m); 
       --n; 
      } 
     } 
     return n; 
    } 

A questo punto, abbiamo risposto alla domanda del PO. Questo richiederà molto tempo per essere eseguito, ma ritornerà con i valori provati (m = 4, n = 2). Non getterà mai uno StackOverflowException, sebbene finirà per esaurire la memoria al di sopra di determinati valori di m e n.

Come ulteriore ottimizzazione, possiamo saltare aggiungendo un valore alla pila, solo per farla subito dopo:

public static BigInteger Ackermann(BigInteger m, BigInteger n) 
    { 
     Stack<BigInteger> stack = new Stack<BigInteger>(); 
     stack.Push(m); 
     while(stack.Count != 0) 
     { 
      m = stack.Pop(); 
     skipStack: 
      if(m == 0) 
       n = n + 1; 
      else if(n == 0) 
      { 
       --m; 
       n = 1; 
       goto skipStack; 
      } 
      else 
      { 
       stack.Push(m - 1); 
       --n; 
       goto skipStack; 
      } 
     } 
     return n; 
    } 

Questo non ci aiuta con una pila né significato con il mucchio, ma dato il numero di loop questa cosa farà con grandi valori, ogni cosa che possiamo eliminare vale la pena.

eliminazione goto mantenendo che l'ottimizzazione è lasciata come esercizio per il lettore :)

Per inciso, ho avuto troppo impazienti nel testare questo, così ho fatto una forma di truffa che utilizza le proprietà note della funzione Ackerman quando m è inferiore a 3:

public static BigInteger Ackermann(BigInteger m, BigInteger n) 
    { 
     Stack<BigInteger> stack = new Stack<BigInteger>(); 
     stack.Push(m); 
     while(stack.Count != 0) 
     { 
      m = stack.Pop(); 
     skipStack: 
      if(m == 0) 
       n = n + 1; 
      else if(m == 1) 
       n = n + 2; 
      else if(m == 2) 
       n = n * 2 + 3; 
      else if(n == 0) 
      { 
       --m; 
       n = 1; 
       goto skipStack; 
      } 
      else 
      { 
       stack.Push(m - 1); 
       --n; 
       goto skipStack; 
      } 
     } 
     return n; 
    } 

Con questa versione, posso ottenere un risultato di true per Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 dopo poco più di un secondo (Mono, accumulo di rilascio, in esecuzione su un core i7). Dato che la versione non-cheat è coerente nel restituire il risultato corretto per tali valori di m, prendo questo come prova ragionevole della correttezza della versione precedente, ma lascerò correre e vedere.

Modifica: Naturalmente, non mi aspetto davvero che la versione precedente ritorni in un qualsiasi periodo di tempo ragionevole, ma ho pensato di lasciarla comunque in esecuzione e di vedere come è andata la sua memoria. Dopo 6 ore si trova bene sotto 40MiB. Sono abbastanza felice che, sebbene chiaramente impraticabile, sarebbe effettivamente tornato se gli fosse dato abbastanza tempo su una macchina reale.

Modifica: Apparentemente si sostiene che lo Stack<T> che colpisce il limite interno di 2 ¹ elementi conta come una sorta di "overflow dello stack". Siamo in grado di fare con questo anche se dobbiamo:

public class OverflowlessStack <T> 
{ 
    internal sealed class SinglyLinkedNode 
    { 
     //Larger the better, but we want to be low enough 
     //to demonstrate the case where we overflow a node 
     //and hence create another. 
     private const int ArraySize = 2048; 
     T [] _array; 
     int _size; 
     public SinglyLinkedNode Next; 
     public SinglyLinkedNode() 
     { 
      _array = new T[ArraySize]; 
     } 
     public bool IsEmpty{ get{return _size == 0;} } 
     public SinglyLinkedNode Push(T item) 
     { 
      if(_size == ArraySize - 1) 
      { 
       SinglyLinkedNode n = new SinglyLinkedNode(); 
       n.Next = this; 
       n.Push(item); 
       return n; 
      } 
      _array [_size++] = item; 
      return this; 
     } 
     public T Pop() 
     { 
      return _array[--_size]; 
     } 
    } 
    private SinglyLinkedNode _head = new SinglyLinkedNode(); 

    public T Pop() 
    { 
     T ret = _head.Pop(); 
     if(_head.IsEmpty && _head.Next != null) 
      _head = _head.Next; 
     return ret; 
    } 
    public void Push (T item) 
    { 
     _head = _head.Push(item); 
    } 
    public bool IsEmpty 
    { 
     get { return _head.Next == null && _head.IsEmpty; } 
    } 
} 
public static BigInteger Ackermann(BigInteger m, BigInteger n) 
{ 
    var stack = new OverflowlessStack<BigInteger>(); 
    stack.Push(m); 
    while(!stack.IsEmpty) 
    { 
     m = stack.Pop(); 
    skipStack: 
     if(m == 0) 
      n = n + 1; 
     else if(m == 1) 
      n = n + 2; 
     else if(m == 2) 
      n = n * 2 + 3; 
     else if(n == 0) 
     { 
      --m; 
      n = 1; 
      goto skipStack; 
     } 
     else 
     { 
      stack.Push(m - 1); 
      --n; 
      goto skipStack; 
     } 
    } 
    return n; 
} 

Anche in questo caso, chiamando Ackermann(4, 2) rendimenti:

Qual è il risultato corretto. La struttura dello stack utilizzata non verrà mai lanciata, quindi l'unico limite rimanente è l'heap (e ovviamente, con input abbastanza grandi dovrai usare "universe lifetime" come unità di misura ...).

Poiché il modo in cui viene utilizzato è analogo al nastro di una macchina di Turing, ci viene ricordata la tesi che qualsiasi funzione calcolabile può essere calcolata su una macchina di Turing di dimensioni sufficienti.

Answer 2

Usa Memoizzazione. Qualcosa di simile:

private static Dictionary<int, int> a = new Dictionary<int, int>(); 

private static int Pack(int m, int n) { 
return m * 1000 + n; 
} 

private static int Ackermann(int m, int n) { 
    int x; 
    if (!a.TryGetValue(Pack(m, n), out x)) { 
    if (m == 0) { 
     x = n + 1; 
    } else if (m > 0 && n == 0) { 
     x = Ackermann(m - 1, 1); 
    } else if (m > 0 && n > 0) { 
     x = Ackermann(m - 1, Ackermann(m, n - 1)); 
    } else { 
     x = -1; 
    } 
    a[Pack(m, n)] = x; 
    } 
    return x; 
} 

Tuttavia, questo esempio mostra solo il concetto, sarà ancora non dare il risultato corretto per Ackermann (4, 2), come int è troppo piccolo per contenere il risultato. Avresti bisogno di un numero intero con 65536 bit anziché 32 per quello.