Ackerman関数がスタックのオーバーフローを防ぐ方法を教えてください。

Question

私のAckerman関数が比較的小さい数、すなわち（4,2）のためにそれを行うかどうかを超えてスタックを作成する方法はありますか？これは、エラー

{現在のスレッドがスタック オーバーフロー状態であるので、式を評価することはできません。}

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

StackOverflowExceptionを避ける最善の方法は、スタックを使用しないことです。

uintと呼ぶと意味がないので、否定的なケースを取り除きましょう。

まず、我々は大きな船が必要になるだろう：

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

また、どのようなここでは以下のことも、私たちが陰性の検査方法では非常に最初のものを作る場合は他の可能性が考慮される前に、動作します

成功は少なくとも数学的に可能です。さて、n == 0のケースは、シンプルなテールコールです。それを手で取り除きましょう。これは、すでにスタックを爆破するために少し時間がかかります

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

が、それを吹き飛ばす、それは以下となります。私たちは、それは一時的なので、私たちが持っていないので、ヴェロキラプトルまたはダイクストラ心配するgotoを使用します。しかし、このフォームを見ると、mは再帰呼び出しの戻り値によって設定されないことに注意してください。一方、nは時々です。

これを拡張すると、以前の値mのトラッキングに対処するだけで、繰り返しフォームにすることができます。繰り返しフォームで返す場合は、反復フォームでnに割り当てます。我々が対処されるのを待っているm Sがなくなったら、私たちは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; 
    } 

を、私たちはOPの質問に答えています。実行には時間がかかりますが、試行された値（m = 4、n = 2）とともに戻ります。 StackOverflowExceptionを投げることはありませんが、特定の値の上にあるメモリが不足すると、mと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(); 
     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; 
    } 

：

さらに最適化するように、我々は唯一の直後にそれをポップし、スタックに付加価値をスキップすることができますこのことは大きな価値を伴います。私たちが剃ることができるすべてのビットは、その価値があります。読者の演習として残して:)ちなみに

その最適化を保ち、私はこれをテストするには、あまりにもせっかちだので、私はときメートルアッカーマン関数の既知の特性を使用して不正行為の形をした一方でgotoを排除

、私は（コアi7プロセッサー上で実行されている、モノ、リリースビルド）は、第2の余り後Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3ためtrueの結果を得ることができます。このバージョンでは

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

：3未満です。ノンキレートバージョンがmのような値に対して正しい結果を返すことを考えれば、私はこれを前のバージョンの正当性の合理的な証拠とみなしますが、実行しておきます。

編集もちろん、私は前のバージョンが賢明な時間枠で戻ってくるとは思っていませんが、とにかく前回のバージョンを実行したままにしておき、メモリの使い方を見ていきたいと思いました。 6時間後、それは40MiB以下でうまく座っています。明らかに実用的ではありませんが、実際のマシンで十分な時間が与えられれば本当に戻ります。

編集：明らかに、Stack<T>の内部制限が2³¹のアイテムに当たっていることは、一種の「スタックオーバーフロー」としてカウントされているようです。再び

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

Ackermann(4, 2)リターンを呼び出し、：：私たちがしなければならない場合我々はまた、それに対処することができ、正しい結果である

を。使用されているスタック構造は決して投げられませんので、残っている唯一の限界はヒープです（そしてもちろん、測定の単位として "宇宙生涯"を使用するのに十分な大きさの入力があります）。

チューリングマシンのテープに似ているので、計算可能な関数は十分なサイズのチューリングマシンで計算できるという論文が思い出されます。

Answer 2

使用メモ化です。以下のようなものは：

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

しかし、この例では、唯一の概念を示し、それはまだアッカーマン（4、2）、intがあまりにも小さいので、結果を保持するための正しい結果が得られません。そのためには32ビットではなく65536ビットの整数が必要です。