Fun With Numbers

I have been fooling around with a program to compute the Ackermann function. I say fooling because I haven't really put any serious analysis into it. I have just been trying different things to see what happens.

One thing I did was install the GMP library on my Linux box. I changed my program to use the functions provided by this library instead of just performing regular arithmetic. Being as the results of the Ackermann function can run into thousands of digits, I was going to need something. I thought about writing one myself, and that might have been fun, but let's try and focus, shall we?

I am beginning to think that a simple minded implementation of Ackermann is not going to work. I may be wrong, but I suspect that there might not be enough virtual memory on the planet to accommodate a simple minded solution.

Say the answer (to a particular evaluation) runs to 10,000 digits. Two to the 10th power (2^10) is 1024, or roughly one thousand, or three decimal digits. 10,000 digits is roughly 1000^3333, or 2^33330. A trillion is roughly 2^40. So say we can get by with 16 bytes (2^4) of stack space for each call. So if the depth of our recursion is proportional to the number of digits in the answer, then we will need 2^33334 bytes of stack. A terabyte is 2^40. 2^33334 / 2^40 = 2^33,294.

Notice that neither the number of bytes of stack per call nor the number of bytes in a terrabyte make any real impact on the original number.

Of course it may be that the amount of stack space required is NOT proportional to the size of the result, in which case it might be possible to arrive at a solution.

But then there is the time involved. Even at the fastest clock speed incrementing a number from zero till it has 10,000 digits is going to take a long time. Strikes me now that the amount of time required is going to be similar to the amount of space we computed above. In other words, we won't have an answer before our Sun burns out, or goes Nova.

So how do we compute the value of the Ackermann function? Someone was put together a simple mathematical expression that purports to compute the value of the Ackermann function. So one fairly simple test I could do would be to implement that expression and see it if delivers the same result as reported elsewhere.

But how do know if that is the correct answer? That is going to require analysis of the original definition to see it does in fact correspond to the expression in question. That is going to require thinking.

Of course the real question, is why am I even fooling with this? Same reason I do the Jumble (most) every morning: I need a little mental exercise everyday. Keeps me from getting bored. Also I am acquiring L33T Linux skills by mucking about with GMP and Eclipse.