C++ : Meta Programming : Fibonacci and Phi

In this blog I explore the relationship between the Fibonacci sequence and the Golden Ratio Phi. I write a meta program to calculate the Fibonacci sequence at compile time and use the last two elements in the sequence to calculate Phi.


Fibonacci Sequence:

 1 1 2 3 5 8 13 21 34 ...

  N    N   + N
   i =  i-1   i-2
   

The following expression tends towards Phi as i increases:

 N  /  N
  i     i-1

Another definition of Phi:

Phi * Phi = Phi + 1

Which rearranged proves that Phi is 1 + it's reciprocal, hinting at a much simpler algorithm to calculate it than the one we have here based on this equation:

Phi = 1 + 1/Phi

This could be expressed as a recursive function and we can start with any number, except 0 or -1, to tend towards Phi, 1 will do though.

The following link explores the interesting mathematical properties of Phi


http://www.mcs.surrey.ac.uk/Personal/R.Knott/
Fibonacci/phi.html#simpledef


Now time for some code, here's a runtime recursive function that calculates the last two numbers in the Fibonacci sequence for any given index in the sequence i:

#define DO_OUTPUT

typedef unsigned long long ulong;
typedef std::pair<ulong, ulong> tuple;

// Fibonacci
// Run-time Recursive Function
void GetFibonacciTupleImpl(unsigned int i, tuple &result)
{
    if(i>0)
    {       
        result.second += result.first;
        result.first = result.second - result.first;
#ifdef DO_OUTPUT
        std::cerr << result.second << " ";
#endif                                
        if(result.second>result.first) // wrapping guard
            GetFibonacciTupleImpl(i-1, result);
        else  // store recursive level
           result.first = result.second = i;
        
    }
}

void GetFibonacciTuple(unsigned int i, tuple &result)
{
    result.first = 1;
    result.second = 1;
#ifdef DO_OUTPUT
    std::cerr << "1 1 ";
#endif
    GetFibonacciTupleImpl(i, result);
#ifdef DO_OUTPUT
    if(result.first==result.second && result.second>1)
        std::cerr << "\nwrapping occured at i=" 
                  << (i-result.first+2) << "\n";
#endif
}

Here's a meta-programming solution for the exact same thing, only all calculated at compile-time!

template<int I>
struct Fibonacci
{
    enum { value = Fibonacci<I-1>::value +
                   Fibonacci<I-2>::value };
};

template<>
struct Fibonacci<1>
{
    enum { value = 1 };
};


template<>
struct Fibonacci<0>
{
    enum { value = 1 };
};

template<int I, typename T>
struct FibonacciTuple
{
    enum {
        first = Fibonacci<I-1>::value,
        second= Fibonacci<I>::value
    };
    
    // run time part as not integral ...
    static const T getRatio()
    {
         return (T)second / (T)first;
    }
};

Now this only works up to a point. If you try to compile Golden::FibonacciTuple<47,double>::getRatio() under g++ 3.4.4 you get a compiler error: Integer Overflow in Expression. Also the results are only correct up to Golden::FibonacciTuple<45,double>::getRatio(). Initially I surmised this was due to some compiler recursion-stack related problem but after I'd actaully read the compiler output! I realised the error occured on the line where the enum value is evaluated (using the + operator). If it were a compiler stack-depth problem then something like this migth have alleviated the problem:

template<ulong I>
struct Fibonacci
{
   ...
};

but the error lies with the face that it looks like the compiler uses a signed integer to store enum values. Why signed? Well the runtime version uses an unsigned int to store the Fibonacci sequence value and it breaks down after 90 recursions! (i.e. twice as many).

Of course this is only a bit of fun and isn't the most efficient way of calculating Phi. Initially I thought perhaps I could write a way of statically storing the value of Phi in a program without defining it as a literal value, i.e.

static const float Phi = 1.618....;

However, firstly there's the enum problem and secondly (and this is a related problem) we can only use integral values at compile-time. This is illustrated by the following meta program:

// Cannot get Phi using the reciprocal method
// since only integral numbers are used in enums!

template<int I>
struct Phi
{
    enum { value = 1 + 1/Phi<I-1>::value };
};

template<>
struct Phi<0>
{
    enum { value = 1 };
};

This is a flawed implementation of the reciprocal method of calculating Phi as mentioned above. This obviously requires less work than the Fibonacci method but isn't quite as interesting from a mathematical point of view.

In conclusion then, as well as exploring the fascinating relationship between the Fibonacci Sequence and Phi, we've found out about some limitations of what we can and can't do a compile-time and managed to deduce the g++ 3.4.4 uses an int to store an enum values!