Can the standard Ackermann be optimized?

Question

The standard Ackermann formula as written in Java:

public static int ack(int x, int y) {

        if (x == 0) {
            return y + 1;
        } else if (y == 0) {
            return ack(x-1, 1); 
        } else {
            // perforce (x > 0) && (y > 0)
            return ack(x-1, ack(x,y-1));
        }
    }

I've been wondering - is there a faster version to implement this? I'm thinking maybe there is by using an accumulator or a loop.

Answer 1

Yes, for example by "cheating". If m is 5 or higher, none of the results can be represented by an int. For m = 4, only the n < 2 cases can be represented. For m < 4, there are simple closed formula's based on n.

Everything else would overflow anyway, so let's pretend those cases don't even happen (or you could throw an error or whatever).

Not tested:

int Ackerman(int m, int n) {
    switch (m) {
    case 0:
        return n + 1;
    case 1:
        return n + 2;
    case 2:
        return n * 2 + 3;
    case 3:
        return (int)((1L << (n + 3)) - 3);
    case 4:
        return n == 0 ? 13 : 65533;
    }
}

Answer 2

I can tell you one thing... int will not suffice for very many values of x and y

If you're going to be calling the function repetitively, you can create a int[][] array to store various values so you can look them up the second+ time around and only need to compute it once. But as for speeding up a single execution... not sure.

Answer 3

This variation is faster:

public static int ack(int x, int y) {
    while (x != 0) {
        y = y == 0 ? 1 : ack(x, y - 1);
        x--;
    }
    return y + 1;
}