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