Fibonacci Recursive and Non Recursive C++

If you can, the quickest way to calculate the Fibonacci numbers is to do it at compile time. This is a case of "My recursive method is quicker than yours...":

template<typename T, unsigned char n>
class fibonacci_number
{
    public:
        static const T value = fibonacci_number<T, n - 1>::value + fibonacci_number<T, n - 2>::value;
};

template<typename T>
class fibonacci_number<T, 1>
{
    public:
        static const T value = 1;
};

template<typename T>
class fibonacci_number<T, 0>
{
    public:
        static const T value = 0;
};

and you can use it with something like:

std::cout << fibonacci_number<__int64, 10>::value << std::endl;

As I said, this will only work if you know which element of the series you need at compile time. It also is pretty good at catching errors, unlike the original code which can't catch overflows.

Interestingly, the compiler doesn't take very long to work this out while the recursive technique the original poster outlined was incredibly slow. So how does the compiler do it? The short answer is that it only needs to evaluate each term once when it generates the type, while the original poster's does it some high order polynomial number of times.

Ideally what we'd like is something that can calculate different numbers at runtime with the same sort of speed that the compiler can generate them at compile time. Looking at a naive runtime recursive implementation of the series:

template<typename T>
class fibonacci_series
{
    public:
        T nth_element( unsigned char n )
        {
            if( n < 2 ) return n;
            return nth_element( n - 1 ) + nth_element( n - 2 );
        }
};

It's going to take a lot of work to make that any simpler code wise. However we can speed it up a lot by doing what the compiler does and only calculating each element in the series once. So let's split the calculation function up a bit:

template<typename T>
class fibonacci_series
{
    public:
        T nth_element( unsigned char n )
        {
            return calculate_nth_element( n );
        }

    private:
        T calculate_nth_element( unsigned char n )
        {
            if( n < 2 ) return n;
            return nth_element( n - 1 ) + nth_element( n - 2 );
        }
};

It looks like a bit of a con as all I'll done is add an extra level of indirection in the calculation. However, wherever there are extra levels of indirection, we can hook onto them and cache values that have already been calculated, hopefully without messing up the simplicity of the calculation.

To cache already calculated values, I'll use a map - other, more efficient means exist but a map's pretty good as it's got the interface I want AND there aren't that many Fibonacci numbers you can calculate on a 64 bit computer (about 90). Here's a first stab:

template<typename T>
class fibonacci_series
{
    public:
        T nth_element( unsigned char n )
        {
            cache_type::const_iterator iter = cache_.find( n );
            if( iter != cache_.end() )
            {
                return iter->second;
            }

            return cache_[n] = calculate_nth_element( n );
        }

    private:
        T calculate_nth_element( unsigned char n )
        {
            if( n < 2 ) return n;
            return nth_element( n - 1 ) + nth_element( n - 2 );
        }

        typedef std::map<unsigned char, T> cache_type;
        cache_type cache_;
};

Basically when a number is calculated, it gets slung in the map and used from there when it's wanted again. Hurrah! We can also remove the conditional from the calculation function by prepopulating the map:

template<typename T>
class fibonacci_series
{
    public:
        fibonacci_series()
        {
            cache_[ 0 ] = 0;
            cache_[ 1 ] = 1;
        }

        T nth_element( unsigned char n )
        {
            cache_type::const_iterator iter = cache_.find( n );
            if( iter != cache_.end() )
            {
                return iter->second;
            }

            return cache_[n] = calculate_nth_element( n );
        }

    private:
        T calculate_nth_element( unsigned char n )
        {
            return nth_element( n - 1 ) + nth_element( n - 2 );
        }

        typedef std::map<unsigned char, T> cache_type;
        cache_type cache_;
};

I like this solution for a couple of reason: Firstly calculate_nth_element IS the statement of a Fibonacci series. Most mathematicians seeing that expression would understand it. Secondly the caching is split off from the calculation code and is almost at the point you could make it completely general for any series.

It also beats the pants off a naive iterative solution on my system for a large number of uses. You can't tell a lot of difference if you just calculate each number from 0th to 90th as algorithmically they are the same solution. If you want an extra edge of performance you could use an iterative calculate_nth_element with the caching code unchanged:

template<typename T>
class fibonacci_series
{
    public:
        fibonacci_series()
        {
            cache_[ 0 ] = 0;
            cache_[ 1 ] = 1;
        }

        T nth_element( unsigned char n )
        {
            cache_type::const_iterator iter = cache_.find( n );
            if( iter != cache_.end() )
            {
                return iter->second;
            }

            return cache_[n] = calculate_nth_element( n );
        }

    private:
        T calculate_nth_element( unsigned char n )
        {
            n -= 2;
            int first = 1, second = 1;
            while( n-- )
            {
                int third = first + second;
                first = second;
                second = third;
            }

            return second;
        }

        typedef std::map<unsigned char, T> cache_type;
        cache_type cache_;
};

This is better but you have to calculate each term once to get any speed up. There are plenty of improvements you can do here - instead of the variable third in calculate_nth_element you could read/write directly from the cache, but I've probably bored you enough.

Incidentally when I was developing the second class, I used the template metaprogramming version to unit test the second.

Thanks for reading,

Ash