Programming Ackerman's function

[wishbone34]

Ok, here is my code, which works fine, for implementing ackerman's function.
The question I have is, since the function's value increases so quickly, the numbers become so large so fast that the program just crashes if anything after A(3,4) is entered. I assume this is because the variables are only able to hold into the two billion range and the output would be much much higher, so the program crashes when the output would be out of the variable's range. Is there anyway around this? I want to be able to get an output for A(5,5). Thanks!

#include "stdafx.h"
#include <iostream>
using namespace std;

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

int _tmain(int argc, _TCHAR* argv[])
{
	


    int m, n;

    cout << "Enter m:" << endl;
    cin >> m;
    cout << "Enter n:" << endl;
    cin >> n;
    cout << "A(" << m << "," << n << ") = " << A(m, n) << endl;


	return 0;
}

[sicarie]

You can try using longs or unsigned ints, if you know the value is going to be positive... How high are you wanting this to go?

[Banfa]

The problem is not the size of the numbers, long before the numbers get too big to handle you are getting a stack overflow (somewhere between a call depth of 4000 and 4500 on my version of your code modified to count call depth).

That is you have made some many calls in a row without returning from any of them that the stack can no longer grow to meet the requirements of your program.

Off the top of my head I can not think of a way round this.

[Banfa]

OK this is quite an interesting function.

I thought it may be possible to improve things by recording Ackerman values as they were generated so that they may be used later in the calculation of further Ackerman numbers.

I did this use a map to record the result of an Ackerman number A(m,n). This does significantly reduce the call depth. I had noticed that previous the call depth seemed to be something like result + m - 1. I am now getting call depths significantly below the result. For instance I can now calculate A(3,10) = 8189 only going to a call depth of 2052 and involving calculating 20481 separate Ackerman numbers. This would not have been possible before because the required call depth would have been in excess of 8189 (8191 by my calculation).

Something else I noticed, I decided to record how often each Ackerman number was reused in the calculation. It turns out that

a. not all the Ackerman numbers are reused
b. Numbers that are reused appear to be only resused once.

I assume that b is because each time you reuse a number you create another number that will be reused in its place next time.

However for all this it does not solve your problem. The result (and call depth) increase much more dramatically with increasing m than increasing n. Even using this method the only Ackerman number that can be calculated with m > 3 is A(4,0) === A(3,1).

[JosAH]

As Banfa already mentioned it's the stack size that is the show stopper here.
You can use an explicit stack (a vector<int> comes to mind if you're using C++)
Here's a bit of pseudo code that does the job:

stack.push(m);
stack.push(n);
while (stack.size() > 1) {
   n= stack.pop();
   m= stack.pop();
   if (m == 0) stack.push(n+1);
   else if (n == 0) {
      statck.push(m-1); stach,push(1);
   }
   else {
      stack.push(m-1); stack.push(m); stack.push(n-1);
   }
}
print(stack.pop());

The behaviour of the stack is fascinating (you can see that if you print out the
entire stack at each iteration). It's a sawtooth type of movement which resembles
fractal characteristics .

kind regards,

Jos

[Skittlesssss]

digging deep for this.. 07 wow. I like what JosAH did with the stack.. But i want to take this farther.. Anyone know of a way to implement this so that i cant print out numbers into the (5,x) range?

[Banfa]

Try JosAH method using vectors and without using recursion. Holding the data required should be so much of a problem if you avoid the stack overhead of all those recursive calls.

Another alternative would be to again write a non-recursive algorithm and also store the output data in a file rather than in memory. In this case I imagine you could calculate much bigger values because memory and stack usage would be quite low.