I decided to implement the Ackermann function in Java using the BigInteger class. Mainly I wanted to see something generating really big numbers, to see how the class scales. Ackermann seemed to be a good place to start, because this recursive function grows really fast.
My second goal was to see exactly how slow Ackermann would really be with bigger numbers. I admit that I was intrigued by the supposedly scarry xkcd number which can be obtained by calling Ackermann with Graham’s Number as both parameters.
Here is the code:
public static BigInteger ackerman(BigInteger m, BigInteger n)
{
BigInteger r = null;
if(m.compareTo(BigInteger.ZERO) == 0)
r = n.add(BigInteger.ONE);
else if(m.compareTo(BigInteger.ZERO)>0 && n.compareTo(BigInteger.ZERO)==0)
r = ackerman(m.subtract(BigInteger.ONE), BigInteger.ONE);
else if(m.compareTo(BigInteger.ZERO)>0 && n.compareTo(BigInteger.ZERO)>0)
r = ackerman(m.subtract(BigInteger.ONE), ackerman(m, n.subtract(BigInteger.ONE)));
return r;
}
I did couple of test runs and it gave me the same results as the ones shown in Wikipedia article. It seems that the second parameter of the function really doesn’t impact the performance that much. I ran ackerman(1, 10000) and it finished in 1314 milliseconds. Running it with 100,000 gave me a stack overflow error. What I see happening there is many, many recursive calls one after another. We are dealing with pretty big numbers here so no wonder that it craps out.
This tells me that, just as I expected Ackermann can’t be effectively implemented just BigInteger because our memory is limited. So we have to be clever here, and write stuff out to disk before taking each recursive branch – this will of course be slower, but the practical limit then is holding two BigIntegers in memory.
Interestingly enough, the first Ackermann attribute is the one that affects performance. I ran ackermann(4, 1) and it was chuging along for around 3 hours before I killed it. Please check the code and tell me if this is an infinite loop, or is this functionreally that slow? I’m not sure at this point. But if it is this slow, then the xkcd number is really, really scarry. :P
Now… Would it be possible to paralellize the Ackerman function? I’m not sure – because of the recursive nature this might be tricky. I will have to ponder this for a bit.
[tags]ackermann, ackermann function, graham’s number, java, recursion, recursive[/tags]
if you try to work the function out on paper the value “m” variable is so much more important than the value of “n” variable that A(4,1) is not that different from A(4,2) at all! a huge number of “n”‘s must be needed to equal just one “m”
Yup, that’s what it seems like. Thanks.
My first thought would be to do it in bc,
define ack(m, n) { if (m == 0) { return (n + 1) } if (n == 0) { return (ack (m - 1, 1)) } return (ack (m - 1, ack (m, n - 1))) }