Click here to Skip to main content
Click here to Skip to main content
Alternative Tip/Trick

Tagged as

Fibonacci Recursive and Non Recursive C++

, 20 Sep 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
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...":templateclass fibonacci_number{ public: static const T value = fibonacci_number<T, n -...
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Aescleal
Software Developer (Senior)
United Kingdom United Kingdom
I've been programming since 1985 - starting with Fortran 77, then moving onto assembler, C and C++ in about 1991. I also know enough Java and Python to read code but you probably wouldn't want me writing it.
 
I've worked in a wide variety of application areas - defense, banking, games and security with the longest stints being in security. I also seem to end up programming devices far too often. This time I'm programming terahertz band body scanners.
Follow on   Google+

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141223.1 | Last Updated 20 Sep 2010
Article Copyright 2010 by Aescleal
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid