Calculating larger values of the ackermann function

Question

I have some code:

int CalculateAckermann(int x, int y)
{
    if(!x)
    {
        return y++;
    }
    if(!y)
    {
        return CalculateAckermann(x--,1);
    }
    else
    {
        return CalculateAckermann(x--, CalculateAckermann(x, y--));
    }
}

Designed to calculate the ackermann function. Above a fairly low number of x and y the application causes a stack overflow because it recurses too deeply and results in pretty big numbers. How would I go about slowly calculating a solution?

Answer 1

As a note if you wish to just used the closed form, then the algorithms for m<4 are straightforward. If you wish to extend to tetration, then I suggest you write a fastpower algorithm probably using the binary method and then with that method you can write a tetration function. Which would look something like:

int Tetration(int number, int tetrate)
{
    long int product=1;
    if(tetrate==0)
        return product;
    product=number;
    while(tetrate>1)
    {
        product=FastPower(number,product);
        tetrate--;
    }
    return product;
}

Then you can cover cases up to n==4 and after that use the recursive definition and values of A(5,n) overflow at a ridiculous rate, so it's really of no concern. Although your teacher probably won't be satisfied with an algorithm such as this, but it will run much faster. In one of my discrete classes when I asked to write an algorithm to compute the fibonacci numbers and then find its O(n), I wrote the closed form and then wrote O(1) and got full credit, some professors appreciate clever answers.

What is important to note about the Ackerman function is it essentially defines the heirachy of additive functions on the integers, A(1,n) is addition , A(2,n) is multiplication, A(3,n) is exponentiation, A(4,n) is tetration and after 5 the functions grow too fast to be applicable to very much.

Another way to look at addition, multiplication, etc is:

Φ0 (x, y ) = y + 1
Φ1 (x, y ) = +(x, y )
Φ2 (x, y ) = ×(x, y )
Φ3 (x, y ) = ↑ (x, y )
Φ4 (x, y ) = ↑↑ (x, y )
           = Φ4 (x, 0) = 1 if y = 0
           = Φ4 (x, y + 1) = Φ3 (x, Φ4 (x, y )) for y > 0

(Uses prefix notation ie +(x,y)=x+y, (x,y)=xy.

Answer 2

IIRC, one interesting property of the Ackermann function is that the maximum stack depth needed to evaluate it (in levels of calls) is the same as the answer to the function. This means that there will be severe limits on the actual calculation that can be done, imposed by the limits of the virtual memory of your hardware. It is not sufficient to have a multi-precision arithmetic package; you rapidly need more bits to store the logarithms of the logarithms of the numbers than there are sub-atomic particles in the universe.

Again, IIRC, you can derive relatively simply closed formulae for A(1, N), A(2, N), and A(3, N), along the lines of the following (I seem to remember 3 figuring in the answer, but the details are probably incorrect):

• A(1, N) = 3 + N
• A(2, N) = 3 * N
• A(3, N) = 3 ^ N

The formula for A(4, N) involves some hand-waving and stacking the exponents N-deep. The formula for A(5, N) then involves stacking the formulae for A(4, N)...it gets pretty darn weird and expensive very quickly.

As the formulae get more complex, the computation grows completely unmanageable.

---

The Wikipedia article on the Ackermann function includes a section 'Table of Values'. My memory is rusty (but it was 20 years ago I last looked at this in any detail), and it gives the closed formulae:

• A(0, N) = N + 1
• A(1, N) = 2 + (N + 3) - 3
• A(2, N) = 2 * (N + 3) - 3
• A(3, N) = 2 ^ (N + 3) - 3

And A(4, N) = 2 ^ 2 ^ 2 ^ ... - 3 (where that is 2 raised to the power of 2, N + 3 times).

Answer 3

(Feels like a homework question, but I'll answer it anyway...)

Read up some more on the Ackermann function. For exmaple, the WikiPedia article says

"Its value grows rapidly, even for small inputs. For example A(4,2) is an integer of 19,729 decimal digits".

I suspect that your 32-bit (or 64-bit, depending on your architecture) integers are overflowing and you're getting into infinite loops because of those issues. Simple printf-style debugging would show the integer overflows. If you want to actually compute the Ackermann function, you'll need to use an infinite precision bignum library, like GNU MP.

Also, read up on Tail Recursion, and how to optimize it out.

Answer 4

You need to pre-decrement, not post-decrement, or you are just passing the same values of x and y to the function at every point. You may want to also build in some safeties to make sure that you don't have negative parameters as the Ackerman function is not defined if x or y is negative.

int CalculateAckermann(int x, int y)
{
    if (x < 0 || y < 0)
    {
        abort();
    }

    if(x == 0)
    {
        return y+1;
    }
    if(y == 0)
    {
        return CalculateAckermann( x-1,1);
    }
    else
    {
        return CalculateAckermann(x-1, CalculateAckermann(x, y-1));
    }
}