Geek asks and answers

How can I prevent overflow of the Ackerman function from the stack?

Is there a way to keep the Ackerman function from creating a stack over the stream, does this for relatively small numbers, i.e. (4.2). This is mistake

{The expression cannot be evaluated because the current thread is in the stack overflow state.}

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;
            }
        }
+5
source share
2 answers

The best way to avoid StackOverflowExceptionis to not use the stack.

Let me get rid of the negative case, because it makes no sense when we call with help uint. Alternatively, the following will also work here if we make the negative test the very first in this method before considering other options:

-, :

    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 - . . goto, , 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));
    }

, , , . , , m , - n.

, , m, , n . 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();
            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;
    }

. , (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, :)

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

true Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 (Mono, Release build, Core i7). , m, , .

Edit: , , , , , , . 6 40 . , , , , .

Edit: -, , 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) :

enter image description here

. , ( , , , " " ...).

, , , , .

+22

memoization. - :

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

, Ackermann (4, 2), int , . 65536 32.

+1

More articles:


All Articles