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.

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? — Tim Seguine, Dec 05 '13 at 21:35
I think the other issue here is why did you ask this question twice today? once for java and once for scheme? http://stackoverflow.com/questions/20393589/can-this-function-be-simplified-made-more-fast On the other question, you got basically the same answers. — Tim Seguine, Dec 05 '13 at 22:42
See also [Theoretically can the Ackermann function be optimized?](https://stackoverflow.com/q/76559257/12597) — Ian Boyd, Jul 04 '23 at 10:57

score 3 · Accepted Answer · answered Dec 05 '13 at 21:45

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

score 2 · Answer 2 · answered Dec 05 '13 at 21:20

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.

score 1 · Answer 3 · answered Dec 05 '13 at 21:33

1

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

answered Dec 05 '13 at 21:33

Peter Walser

15,208
4
51
78

Can the standard Ackermann be optimized?

3 Answers3

Linked