Every programming language enthusiast has written programs to compute the Fibonacci numbers in every programming language. That's easy, and gets boring pretty soon.

But C++ enthusiasts can go one better. That's because C++ conforms to the slogan "buy one C++ compiler, get another interpreted language free!". So C++ can compute Fibonacci numbers at compile time!!!1!

Here's how to do it. Note that the syntax of the compile time language (aka C++ templates) is nothing like what you know of C++. This is absolutely normal in C++; every C++ program looks almost exactly nothing like any other C++ program.

template<int N> struct fib {
  static const int result = fib<N-1>::result + fib<N-2>::result;
};

struct fib<0> {
  static const int result = 0;
};

struct fib<1> {
  static const int result = 1;
};

#include <iostream>
int main(int ac, char *av[])
{
  std::cout << "Fib(10) = " << fib<10>::result << std::endl;
  return 0;
}
C++ advocates will have no problems explaining why this program has linear compilation time in N, rather than the expected exponential compilation time due to the algorithm used. Interestingly, a vastly more complicated struct with logarithmic compilation time (see Compute Fibonacci numbers FAST! for the algorithm, albeit in readable pseudocode rather than template meta-programming nonsense like the above) takes much longer to compile (presumably due to increased complexity).

Warning

You may need to increase your compiler's template depth to compile this code! The gcc incantation is -ftemplate-depth-33 or somesuch.

First, a version of the code that will compile on a modern g++:

#include <iostream>
template<int N> struct fib {
  static const int result = fib<N-1>::result + fib<N-2>::result;
};

template<> struct fib<0> {
  static const int result = 0;
};

template<> struct fib<1> {
  static const int result = 1;
};

int main(int ac, char *av[])
{
  std::cout << "Fib(10) = " << fib<10>::result << std::endl;
  return 0;
}

It might be worth exploring why exactly the above program is linear in compile time rather than exponential. After all, if the computation is being done at compile time, and the run-time of the algorithm is expected to be exponential, then compiling the program should be exponential, right? Let's take a look.

First, let's consider what fib(n) depends on, in this algorithm. Obviously, fib(10) (to continue with the example above) depends on fib(9) and fib(8). But fib(9) depends on fib(8) as well! (It also depends on fib(7)). Obviously, there's some repeated work here; in fact, the repeated work is the source of the expected exponential run-time. If, instead, we cached the value of fib for each n after the first time we computed it, we would only need to do n computations for fib(n), giving us a linear run-time (this type of algorithm is known as dynamic programming).

Now, let's examine what your C++ compiler does when faced with the above code. Firstly, fib is a struct (i.e., a type) parametrized over an integer N. Just like templates using type parameters, fib is code for which a certain detail is left open until the code is used; the only difference is that detail is a value instead of a type. When using such a template, you specify the value explicitly, and the resulting code gets instantiated. So in main(), when you access fib<10>::result, fib gets instantiated with the value 10. However, to do so, because of the way fib is defined, fib<9> and fib<8> must also be instantiated. Recall that fib<9> also needs fib<8>; but at this point, fib<8> has already been instantiated, so the compiler doesn't need to do any extra work, and just emits code to read fib<8>::result. This is exactly like caching the value of fib(n), like we discussed above! And thus compilation time is linear in n.

One final C++ detail that's worth exploring: how does the recursion stop? In a normal recursive function fib(n), you'd have some sort of conditional at the top that exited the recursion when presented with a base case. It turns out C++ templates have a little feature called partial specialization. The idea, going back to type templates, is that maybe you want your templated class or function to do something different for a particular type than the normal case. In the case of fib, we have it specialized for the value 0 and 1, for which result is not defined recursively, but rather initialized with a constant. Thus, when the compiler reaches fib<2> and has to access fib<1>::result and fib<0>::result, it just outputs code to access the constants we wrote in those specializations of fib. (ML hackers will notice that this looks a awful lot like pattern matching arguments).

Log in or register to write something here or to contact authors.