Fibonacci Sequence and C++ template meta-programming

Milot

Feb 29, 2012 • 3 min read

As most of other fellow geeks, I am a big fan of science fiction movies and of course science in general. I watched Fringe (a SciFi TV show) very frequently and as it was progressing I saw lots of glyphs from real-world science and I encountered the above glyph a while ago in Case 0091, but as I was reading after it’s appearance, I saw that a fibonacci sequence was hidden in there and it gave me a nostalgia when I first encountered recursive functions and I did implementation of lots of mathematical problems and searching algorithm using them, ranging from fibonacci sequence to binary search trees and tree traversals and after several years have passed I encountered the following video on YouTube which still is a beauty in itself.

For those who don’t know what fibonacci sequence is watch this video. Furthermore, each element in fibonacci sequence is the sum of two preceding numbers and the sequence appears like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…

How can we achieve that in C++? We can do it in many ways, but here is a recursive function that calculates the fibonacci sequence of n:

int fibonacci(int n)
{
   if (n &lt;= 2)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

We break a big problem (calculating a fibonacci number) to be solved in smaller sub-problems by using recursion, for those who don’t understand recursion Google helps you understand recursion. It is very easy to implement a function that calculates fibonacci using recursion, and if we execute the following code:

int main()
{
   cout &lt;&lt; fibonacci(45) &lt;&lt; endl;
}

We get the following output 1134903170 while it took 8 seconds to execute, we have the following measurement:

 Days              : 0
 Hours             : 0
 Minutes           : 0
 Seconds           : 8
 Milliseconds      : 939
 Ticks             : 89390155
 TotalDays         : 0.000103460827546296
 TotalHours        : 0.00248305986111111
 TotalMinutes      : 0.148983591666667
 TotalSeconds      : 8.9390155
 TotalMilliseconds : 8939.0155

Of course that every function call is expensive and especially if we do recursion for large numbers, in our case above we have used only the number 45, but what happens if we pass 500?

In C++ we have a meta-programming technique called template meta-programming where the values are calculated on compile-time rather than run-time and we have the value already calculated, and this technique uses C++ templates in order to do so.

In the measurement below we can find the execution time of our fibonacci example using template meta-programming:

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 18
Ticks             : 185184
TotalDays         : 2.14333333333333E-07
TotalHours        : 5.144E-06
TotalMinutes      : 0.00030864
TotalSeconds      : 0.0185184
TotalMilliseconds : 18.5184

That’s it, it takes only 18 milliseconds, because the value is already calculated in compile-time and that is only the time it takes for the application to be executed.

To implement it in C++ is very straight forward and similar to creating template classes, below you would find the entire implementation and usage with comments.

// Calculate the value passed as T
template <int T>
struct Fibonacci
{
    enum { value = (Fibonacci<T - 1>::value + Fibonacci<T - 2>::value) };
};

// In the template meta-programming, we do not have conditionals, so instead
// we use struct-overloading like mechanism to set constraints, we do this for
// numbers 0, 1 and 2, just like our algorithm in the function above.
template <>
struct Fibonacci<0>
{
    enum { value = 1 };
};

template <>
struct Fibonacci<1>
{
    enum { value = 1 };
};

template <>
struct Fibonacci<2>
{
    enum { value = 1 };
};

// in the end, we get the value 
int main()
{
    int x = Fibonacci<45>::value;
    cout << x << endl;
}

Notice the value in the enum, it is just a variable, you can name it as you wish, but for the purpose of the post I named it value.

If we pass number 70 instead of 45, we get the following execution measurement:

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 19
Ticks             : 196283
TotalDays         : 2.27179398148148E-07
TotalHours        : 5.45230555555556E-06
TotalMinutes      : 0.000327138333333333
TotalSeconds      : 0.0196283
TotalMilliseconds : 19.6283

From this I learned a powerful and useful technique that C++ offers and I hope you might find it useful and powerful too. As an end, the fibonacci problem with run-time calculation, is not a real problem that template meta-programming is for, template meta-programming can help you solve problems like high performance numerical computing (Blitz), reflection, Dimensional Analysis, it may be used for generic CRC (Cyclic Redundant Codes) calculations because CRC because it uses a lookup table based on parameters, and those parameters can be given to a TMP in order to have calculations performed in compile time.

The main reason why I wrote this post is to give an example how template meta-programming was done on C++03 standard. In C++11 standard we have a compile-time mechanism called generalized constant expressions (or constexpr for short), for more on that in a later blog post.