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

and 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

Update: This post was translated in Russian by Valery

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.
							

Qt Developer Days 2011 and the creation of Boxee Remote for N9

Each year trolls and Qt developers are gathered at Qt Developer Days conference whether it be on Munich or San Francisco, this year was no different, lots of trolls and Qt developers were attending Munich event and then later San Francisco event. For me personally this year was a little bit different because I was also a speaker for Qt in Use track presenting Poken with a colleague of mine from Poken.

My colleague and I presenting on Qt in Use track

The conference was perfect as usual, this year were lots of Qt Ambassadors there, last year we were very small group of Qt Ambassadors to attend Qt Developer Days and we all got a shiny new Nokia N8, this year they changed the way how they would distribute some devices (this year Nokia N9 was a hit), each one of us had a dot on our badge, the dots were either blue or red and then on keynote they created a QML application with two balls (with corresponding colors) that were spinning on screen and whenever space key was pressed a ball was focused on screen, those people with that color on their badge, got a shiny new N9, during keynote speech Marco Agenti ran the game and blue dots got a Nokia N9, I was lucky to have a blue dot on my badge.

My shiny new cyan Nokia N9

On July I received a Nokia N950 and I loved it, so I wrote a cool application for it, but at that time it was the very early prototype and on Qt Developer Days I got inspired by the people and energy there, so I decided to improve it more and publish it to Ovi.

I couldn’t wait to get my hands dirty with the N9′s NFC capabilities so I continued my work on Boxee Remote and added more features to it. Today I am proud announce that Boxee for N9 is now available on Ovi, free of charge; Besides normal navigation control, searching on Boxee, play/pause/stop, I have used NFC capabilities of Nokia N9 so you can now write the IP address of the computer where Boxee is running to an NFC tag and you can connect to Boxee by just touching the tag, personally I have an NFC tag on the back of my TV’s remote control.

You can look at getting started images of capabilities on the Boxee for N9 reserved page here.

Dennis Ritchie: 1941 – 2011

Twitter started buzzing around about the death of Dennis Ritchie, then I ended up in this page which saddened me very much to hear that the creator of C and a key developer of UNIX  has passed away.

I remember when I started using Linux when I was 15 as a Unix-like operating system, then slowly started learning C by reading the source code of various C programs at that time (including Linux kernel) and since then I was writing on several C-like programming languages (including C). Nowadays I use Mac OS X and write C++ which are two things that without Dennis’s work, I wouldn’t be able to use today.

His work became my way of life. RIP Dennis Ritchie.

Meet me at Qt Developer Days 2011

I will be attending Qt Developer Days 2011 in Munich on 24 – 26 October, but this year besides just visiting and enjoying technical talks with other Qt developers, my colleague (Razvan) and I will share the stage together on Qt in Use track to speak about how we implemented pokenMOBILE for Symbian and pokenMOBILE for MeeGo.

Feel free to stop me for a chat during the conference. How do I look? Go to my Qt Developer Network profile I have a cool picture of myself there.

If you haven’t decided yet to attend the Qt Developer Days 2011, watch the video below and think again

My first experience with Nokia N950

When I first saw the Harmattan-based Nokia N9, I was impressed and I wanted one right away and I couldn’t stand waiting to have their brand new concept at hand, the new concept is very powerful and very known to the end-users, swiping; It is a default behavior for humans and we do swiping a lot throughout our lives; I was simply thrilled, and to increase the impatience to have one, Nokia N9 was announced as the Qt phone and I happen to be a Qt developer at heart and of course I saw immediately the need for one (even though I have a lot of smartphones (I mean it) and a tablet).

Immediately after the announcement nice people at Nokia decided to send some Nokia N950 to their beloved Qt Ambassadors, and for me being a Qt developer at heart, I was enrolled in the Qt Ambassador Program in the very first batch of the people who were accepted, June 2010.

After being accepted by Qt Ambassador Program to receive a Nokia N950 and after I am a guy who is impressed to control things remotely, I could not wait to have it and suddenly my shiny Nokia N950 arrived yesterday I’ve used it as a phone and the device itself is very inspiring that today I created a version of XBMC Remote Controller for N950 using QML and C++ in less than 30 minutes!

And as the platform itself is using swipe as their main gesture, I have used only swipe gestures to allow users to navigate through the Boxee, this is very useful because usually the users don’t look at the phone and their TV at the same time, so with swiping is very easy to navigate through XBMC players. There is more work to do on this, I have plenty of plans to make this as good as possible in the near future.

There is also a feature based on proximity sensor, if the user will get an incoming call, no need to do anything else besides answering the phone, the video will pause itself automatically when you place the phone in your ear

Yes it was 30 minutes that took me on getting to know the Qt Components for Harmattan, learn how to use gestures (using GestureArea element) on QML and integrate C++ portion of the code with the QML in the UI. And this all happened after spending one day and a half with N950 and you could see how inspiring the phone is

Enough with words, take a look at the video below, and let me know what do you think:

Hello world!

It has been a long time since my last blog post, and I have changed blogs since first time I started blogging, twice, this is the third time I created a blog which I am hoping to keep it updated regularly.

A lot has changed since last time I wrote on a blog. Last year I became a Qt Ambassador which is very nice to be one, especially when it comes to goodies from wonderful folks at Nokia, currently I am waiting for a cool Nokia N950 to arrive at my door step.

Last year I also went to Qt developer days and besides having lots of fun, I also took both Qt Advanced Exams and I passed both of them and gained the title of Nokia Certified Qt Specialist, after that I joined a cool software engineering team at Poken (www.poken.com) to create a wonderful next generation of NFC application for Symbian in order to fill the gap between offline and online worlds, and we did it, it went mainstream and you can watch the video here if you are still wondering what Poken is and haven’t seen he video yet:

Usually this blog will be filled with technical stuff from three main ecosystems, including Qt, Android and iOS, for all these platforms I write code, I am using Qt for a long time now. For more than one year and a half I a writing Android apps and recently started writing iOS apps using CocoaTouch and Objective-C.

I started this first blog post with some personal thoughts, next time here will be more code. I promise