Fibonacci Sequence and C++ template meta-programming

As most of other fellow geeks, I am a big fan of science fiction movies and of course science in general. I watch 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 <= 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 << fibonacci(45) << 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.

Virtual Functions in C

Recently I got asked a question how I would implement virtual functions in C?

At first I had no idea because C is not an object oriented programming language and there is no such thing as inheritance, but having some experience with C and knowing how virtual functions work I was thinking that there must be a way to mimic the virtual function implementation by using C structs, then I started getting my hands dirty.

For those who are wondering what virtual functions are here is a short description: A virtual function is a function that can be overridden on another inheriting class in order to have a different implementation. Virtual functions use a virtual method table mechanism (or vtable for short) to support function binding on run-time, furthermore virtual table is a static array that has an entry for each virtual function and each entry is a function pointer that points to the most-derived function accessible from that class. How the most-derived function would be determined is that on run-time method’s address is fetched from the object dispatch table.

To learn more do a Google search.

With that said, let’s have a simple C++ implementation of virtual functions:

class ClassA
{
public:
    ClassA() {data = 10;}
    virtual void set()
    {
        std::cout << "ClassA is increasing" << std::endl;
        data++;
    }
    int get()
    {
        set();
        return data;
    }

protected:
    int data;

};

class ClassB : public ClassA
{
public:
    void set()
    {
        std::cout << "ClassB is decreasing" << std::endl;
        data--;
    }
};

What was done in the code snippet above is that we have a class named ClassA where it has two methods, get() and set(); method named get() is marked as virtual function using the C++ virtual keyword and then it was derived on ClassB and its implementation has changed. Integer data on ClassA is marked as protected in order to have access to it on the derived class.

If we initialize and call the corresponding classes and methods in a main function like the snippet below:

int main()
{
    ClassA classA;
    ClassB classB;

    std::cout << "ClassA value: " << classA.get() << std::endl;
    std::cout << "ClassB value: " << classB.get() << std::endl;

    return 0;
}

We get the following output:

ClassA is increasing
ClassA value: 11
ClassB is decreasing
ClassB value: 9

Now we jump to the C implementation of virtual function concept. Knowing that virtual functions are represented as function pointers in vtable and vtable is a static array, we need to create a struct that mimics the ClassA, a vtable for our ClassA that has function pointers and the ClassA function implementation, and those are represented in code below (read code comments also):

// forward declaration of our struct before it's definition
struct ClassA;

// The actual function table that holds function pointers.
typedef struct {
    void (*ClassA)(struct ClassA*); // the "constructor"
    void (*set)(struct ClassA*); // set function
    int (*get)(struct ClassA*); // get function
} ClassA_functiontable;

typedef struct ClassA {
    int data;
    ClassA_functiontable *vtable; // ClassA virtual method table
} ClassA;

// ClassA's function prototypes (forward declarations)
void ClassA_constructor(ClassA *this); 
void ClassA_set(ClassA *this);
int ClassA_get(ClassA *this);

// Static array of the function table struct that contains ClassA's functions. 
ClassA_functiontable ClassA_vtable = {ClassA_constructor, 
                                  ClassA_set,
                                  ClassA_get };

// Implementation of functions and the constructor.                               
void ClassA_constructor(ClassA *this) {
    this->vtable = &ClassA_vtable; 
    this->data = 10;
}

void ClassA_set(ClassA *this) {
    printf("ClassA is increasing\n");
    this->data++;
}

int ClassA_get(ClassA *this) {
    this->vtable->set(this);
    return this->data;
}

In C we don’t have the “this” pointer that points to itself, I have named the parameter as “this” to mimic it’s use in C++ (and also this is similar to what C++ is doing under the hood).

As we have seen in the above code snippet, implementation of ClassA_get() function on ClassA calls the set() function on our virtual method table struct, let’s see how the implementation is being done when introducing another class:

// forward declaration of our struct before it's definition
struct ClassB;

// Same as above, the actual function table that holds function pointers.
typedef struct {
    void (*ClassB)(struct ClassB*);
    void (*set)(struct ClassB*);
    void (*get)(struct ClassA*);
} ClassB_functiontable;

typedef struct ClassB {
    ClassA inherited_class;
} ClassB;

void ClassB_constructor(ClassB *this);
void ClassB_set(ClassB *this);
int ClassB_get(ClassB *this);

ClassB_functiontable ClassB_vtable = {ClassB_constructor, ClassB_set, ClassB_get};

void ClassB_constructor(ClassB *this) {
// A type cast from ClassB to ClassA pointer is needed
    ClassA_constructor((ClassA*)this);

// Type casting should be done for the virtual table struct as well
    this->inherited_class.vtable = (ClassA_functiontable*)&ClassB_vtable;
}

void ClassB_set(ClassB *this) {
    printf("ClassB decreasing\n");
    this->inherited_class.data--;
}

int ClassB_get(ClassB *this) {
    this->inherited_class.vtable->set((ClassA*)this);
    return this->inherited_class.data;
}

As we see here we call same set() function from ClassB’s implementation using the vtable that points to the set() function on ClassA_functiontable (vtable) struct and we use the same data integer via “inherited” class, ClassA.

This is our main function in C:

int main() {
    ClassA classA;
    ClassB classB;

    ClassA_constructor(&classA);
    ClassB_constructor(&classB);
    printf("ClassA value: %d\n", classA.vtable->get(&classA));

   // We need to access get() via the inherited "parent" class 
   // class which in C it's shown in verbose manner as the call below.
    printf("ClassB value: %d\n", 
               classB.inherited_class.vtable->get((struct ClassA*)&classB));
}

This is the console output:

ClassA is increasing
ClassA value: 11
ClassB decreasing
ClassB value: 9

Of course this trick does not appear as natural as in C++ or another object oriented programming language and I have never had to implement similar approach when I wrote C programs in the past, but it still helps understand a possible under the hood implementation of a virtual function feature, and of course this is how I understood it while doing a simple research on the subject.