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.

Jenijenica

I might ask what is the point? The only real non theoretical use I have ever heard of for the Ackermann function is as an upper bound for an algorithm runtime. Does it really matter if a toy implementation is fast? – Artemis

I think the other issue here is why did you ask this question twice today? once for java and once for scheme? #20394089 On the other question, you got basically the same answers. – Artemis

See also Theoretically can the Ackermann function be optimized? – Haymo

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

Combo

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.

Disquiet

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

Noachian