Jak mogę zapobiec przepełnieniu stosu funkcji mojego Ackermana?

Question

Czy istnieje sposób na zachowanie funkcji Ackermana w tworzeniu stosu przepływającego przez względnie małe liczby, tj. (4,2). Jest to błąd

{Nie można ocenić ekspresję ponieważ bieżący wątek jest w stanie przepełnienia stosu .}

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

Najlepszym sposobem, aby uniknąć StackOverflowException, jest nieużywanie stosu.

Pozbądźmy się negatywnego przypadku, ponieważ nie ma znaczenia, gdy zadzwonimy pod numer uint. Alternatywnie, co następuje tu będą również działać, jeśli robimy Negatywny wynik testu Pierwszą rzeczą w sposobie, zanim inne możliwości są uważane:

Po pierwsze, będziemy potrzebować większej łodzi:

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

Teraz sukces jest możliwy co najmniej matematycznie. Teraz sprawa n == 0 jest dość prosta. Wyeliminujmy to ręcznie. Użyjemy goto ponieważ jest tymczasowy, więc nie trzeba się martwić o Velociraptory lub 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)); 
    } 

Będzie to już trochę dłużej dmuchać stos, ale uderzenie go, to będzie. Patrząc jednak na ten formularz, należy pamiętać, że m nigdy nie jest ustawiony przez zwrot połączenia rekursywnego, podczas gdy czasami jest n.

Poszerzmy to, możemy przekształcić to w formę iteracyjną, a mając do czynienia tylko ze śledzeniem poprzednich wartości m i gdzie chcemy powrócić w formie rekurencyjnej, przypisujemy do n w naszym formularzu iteracyjnym. Kiedy zabraknie m czeka się zająć, wracamy bieżącą wartość 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; 
    } 

W tym momencie, mamy odpowiedzi na pytanie OP. To potrwa długo, ale powróci z wypróbowanymi wartościami (m = 4, n = 2). To nigdy nie wyrzuci StackOverflowException, ale skończy się na wyczerpaniu pamięci powyżej pewnych wartości m i n.

W dalszej optymalizacji, możemy pominąć dodanie wartości do stosu, tylko pop go natychmiast po:

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

To nie pomaga nam stosie ani sensownie ze sterty, ale biorąc pod uwagę liczbę pętli, co zrobi z dużymi wartościami, wszystko, co możemy zgolić, jest tego warte.

Wyeliminowanie goto utrzymując, że optymalizacja pozostawiamy jako ćwiczenie dla czytelnika :)

Nawiasem mówiąc, mam zbyt niecierpliwy w testowaniu tego, więc zrobiłem formę oszukiwania który wykorzystuje znane własności funkcji Ackermana gdy m jest mniejszy niż 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; 
    } 

w tej wersji, mogę uzyskać wynik true dla Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 po nieco ponad sekundy (mono, kompilacji Release, działa na Core i7). Biorąc pod uwagę, że wersja nieuczująca jest konsekwentna w zwracaniu poprawnego wyniku dla takich wartości m, przyjmuję to jako uzasadniony dowód poprawności poprzedniej wersji, ale zostawię ją uruchomioną i zobaczę.

Edycja: Oczywiście nie oczekuję powrotu poprzedniej wersji w rozsądnych ramach czasowych, ale pomyślałem, że i tak zostanę uruchomiony i zobaczę, jak działa pamięć. Po 6 godzinach siedzi ładnie poniżej 40MB. Jestem całkiem zadowolony, że chociaż jest to wyraźnie niepraktyczne, to rzeczywiście powróciłby, gdyby miał dość czasu na prawdziwej maszynie.

Edycja: Podobno twierdzi się, że Stack<T>, osiągając swój wewnętrzny limit 2³¹ elementów, jest także pewnego rodzaju "przepełnieniem stosu". możemy mieć do czynienia z tym również jeśli musimy:

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

Znowu dzwoni Ackermann(4, 2) powroty:

który jest poprawny wynik. Stosowana struktura stosu nigdy nie wyrzuci, więc jedynym ograniczeniem pozostałym jest stos (i oczywiście czas, przy wystarczająco dużych wejściach będziesz musiał użyć "czasu życia wszechświata" jako jednostki miary ...).

Ponieważ sposób, w jaki jest używany jest analogiczny do taśmy maszyny Turinga, przypomina nam się teza, że ​​dowolna obliczalna funkcja może być obliczona na maszynie Turinga o wystarczającej wielkości.

Answer 2

Zastosowanie memoization. Coś jak:

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

Jednak ten przykład pokazuje tylko pojęcia, że ​​będzie nadal nie daje poprawny wynik dla Ackermann (4, 2), jako int jest zbyt mały, aby pomieścić wynik. Będziesz potrzebował liczby całkowitej z 65536 bitów zamiast 32 dla tego.