Bad ways of evaluating Ackermann’s function

Ackermann’s function is a very rapidly growing function defined as follows:

A(m,n)=A(m-1,A(m,n-1))~~~~A(0,n)=n+1~~~~A(m,0)=A(m-1,1)

There are articles on the web about clever ways of evaluating Ackermann’s function, but I was interested in investigating the most stupid possible way of doing it. After a bit of thinking I concluded that template meta-programming in C++ must be the worst possible way of doing it.

C++ is a funny creature. It is the only programming language I know of where features are not only designed, they are also discovered. Template meta-programming (TMP) is one these. C++ introduced the concept of using templates to make code reuse possible with none of the performance overheads involved in using polymorphism and virtual functions. The added cost is in a certain sense hidden in more time consuming compilation procedure.

It occurred to me that it might be fun to try and compile to use this feature of C++ to use the compiler to compute large values of the Ackermann function.


#include <iostream>

using namespace std;

template < int M, int N > class Ackermann {
public:
static int const result = Ackermann< M-1 , Ackermann< M, N-1 >::result >::result ;
};

template < int M > class Ackermann <M, 0>{
public:
static int const result = Ackermann<M-1, 1>::result;
};

template <int N> class Ackermann <0,N> {
public:
static int const result = N+1;
};

int main( int argc, char * argv[]){
cout << Ackermann<4,2>::result <<endl;
}

If this compiled, it would be an extremely fast way of computing the Ackermann function. Unfortunately, even though syntactically correct, the level of recursion necessary for the compiler to precompute this function either causes the compiler to fail or the computer to crash…

Advertisements

About jakirkpatrick

I am a researcher in solar energy at the University of Oxford. I am interested in mathematics, programming and trying to understand why things work. I also like the great outdoors and riding my bike.
This entry was posted in programming. Bookmark the permalink.

4 Responses to Bad ways of evaluating Ackermann’s function

  1. Szaki says:

    You might want to try this in Prolog instead of C++. It would run correctly, although extremely slowly and with an insane memory consumption.

    • I wonder whether the key to getting these uber-recursive functions to actually run properly would be to use some with proper tail call optimization? I am not sure how good the gnu c++ compiler is…

      • Szaki says:

        Well, things which are efficient in Prolog are usually “tail-recursive” (meaning the recursion is the last statement in the recursive function) and I know that tail-recursive vs. not tail-recursive versions of the same thing can differ dramatically in their performance. => In Prolog, this optimisation you’re looking for does exist. I have a vague recollection of something similar in C++ as well, but if you really want to get this kinda thing run well in a procedural language, I think assembly would be the way to go.

  2. This has to be the funniest blog I’ve read in a while James, if only because I can actually imagine you leaping up and down with excitement while typing it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s