Tag Archives: Fibonacci Numbers

Functors in C++

A functor in C++ is something that can be called like a function – a function pointer or object of a class with an overloaded operator(). It is the second type that is most commonly being referred to when people talk about functors.

The advantages of having an object of a class with an overloaded operator() over a function pointer are:

  1. The object can maintain state between calls
  2. Calling the overloaded operator() can be more efficient than dereferencing a function pointer

Maintaining state

A class with an overloaded operator() can have member variables, and these allow it to maintain state through function calls. For example, a functor to calculate the Fibonacci numbers could maintain a cache of the ones seen so far to avoid recalculating them.

#include <vector>
#include <iostream>

class Fibonacci
{
public:
    Fibonacci()
    {
        results_.push_back(0);
        results_.push_back(1);
    }
    unsigned int operator()(unsigned int n)
    {
        while (results_.size() < n + 1) {
            results_.push_back(results_[results_.size() - 2] + results_[results_.size() - 1]);
        }
        return results_[n];
    }
private:
    std::vector<unsigned int> results_;
};

int main()
{
    Fibonacci fib;
    for (unsigned int n = 0; n < 10; n++) {
        std::cout << fib(n) << "\n";
    }
}

Efficiency

Functors are commonly used with standard library algorithms like std::for_each() and std::transform(), as in the example below, which fills a vector with the first 100 Fibonaci numbers:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    Fibonacci fib;
    std::vector<unsigned int> results(100);
    std::iota(results.begin(), results.end(), 0);
    std::transform(results.begin(), results.end(), results.begin(), fib);
    std::copy(results.begin(), results.end(),
         std::ostream_iterator<unsigned int>(std::cout, " "));
}

When an ordinary function pointer is passed to one of these algorithms, it’s difficult for the compiler to optimise the function call because a function pointer is a variable and so could change to point to a different function. When the pointer is to a virtual member function there is an extra level of indirection to get to the version in the actual class. With an overloaded operator() however, there is no indirection and the function to be called is fixed, so the compiler can optimise the call by inlining the function’s code at the call site. This can make the call much more efficient.

Fibonacci numbers in C

The recurrence formula for the \(n\)th Fibonacci number is:

\(
F_{n} = \begin{cases} F_{n – 1} + F_{n – 2} & \textrm{if}\;n > 1\\ 1 &\textrm{if}\;n = 1\\ 0 &\textrm{if}\;n = 0.\end{cases}
\)

A naive recursive implementation of this would be:

unsigned int fib(unsigned int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1) + fib(n - 2);
}

But this runs in exponential time because it keeps recalculating the same results in the recursion.

If we add some instrumentation, we can see what it’s doing:

struct calltree {
    unsigned int value;
    struct calltree *left;
    struct calltree *right;
};
typedef struct calltree calltree;

typedef void (*calltreefn)(unsigned int, unsigned int, void *);

calltree *calltree_create(unsigned int value)
{
    calltree *tree = malloc(sizeof(calltree));
    if (tree) {
        tree->value = value;
        tree->left = NULL;
        tree->right = NULL;
    }
    return tree;
}

void calltree_delete(calltree *tree)
{
    if (tree != NULL) {
        calltree_delete(tree->left);
        calltree_delete(tree->right);
        free(tree);
    }
}

void calltree_for_each(const calltree *tree, unsigned int level, calltreefn fun, void *data)
{
    if (tree != NULL) {
        fun(level, tree->value, data);
        calltree_for_each(tree->left, level + 1, fun, data);
        calltree_for_each(tree->right, level + 1, fun, data);
    }
}

unsigned int fib(unsigned int n, calltree **tree)
{
    *tree = calltree_create(n);
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 1, &((*tree)->left)) + fib(n - 2, &((*tree)->right));
}

Here is an example program to calculate \(F_{7}\):

void print_call_text(unsigned int level, unsigned int value, void *data)
{
    unsigned int i;
    for (i = 0; i < level; i++) {
        putchar(' ');
    }
    printf("fib(%d)\n", value);
}

int main(void)
{
    calltree *tree;
    fib(7, &tree);
    calltree_for_each(tree, 0, print_call_text, NULL);
    calltree_delete(tree);
    printf("%u\n", result);
	return 0;
}

The call tree produced:

fib(7)
 fib(6)
  fib(5)
   fib(4)
    fib(3)
     fib(2)
      fib(1)
      fib(0)
     fib(1)
    fib(2)
     fib(1)
     fib(0)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
  fib(4)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
   fib(2)
    fib(1)
    fib(0)
 fib(5)
  fib(4)
   fib(3)
    fib(2)
     fib(1)
     fib(0)
    fib(1)
   fib(2)
    fib(1)
    fib(0)
  fib(3)
   fib(2)
    fib(1)
    fib(0)
   fib(1)

We can get rid of all of these recursive calls by caching the results instead:

unsigned int fib(unsigned int n)
{
    unsigned int *numbers;
    unsigned int i;
    unsigned int result;
    if (n == 0) return 0;
    numbers = malloc((n + 1) * sizeof(int));
    if (numbers == NULL) {
        return 0;
    }
    numbers[0] = 0;
    numbers[1] = 1;
    for (i = 2; i <= n; i++) {
        numbers[i] = numbers[i - 2] + numbers[i - 1];
    }
    result = numbers[n];
    free(numbers); 
    return result;
}

If we were going to calculate a lot of Fibonacci numbers we could store the cache between calls rather than creating it anew each time.