Getting template metaprogramming compile-time constants at runtime

Solution 1:

template <unsigned long N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<N-1>::add_values(v);
        v.push_back(value);
    }
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
    static void add_values(vector<unsigned long>& v)
    {
        v.push_back(value);
    }

};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<0>::add_values(v);
        v.push_back(value);
    }
};



int main()
{
    vector<unsigned long> fibonacci_seq;
    Fibonacci<45>::add_values(fibonacci_seq);
    for (int i = 0; i <= 45; ++i)
        cout << "F" << i << " is " << fibonacci_seq[i] << '\n';
}

After much thought into the problem, I came up with this solution. Of course, you still have to add the values to a container at run-time, but (importantly) they are not computed at run-time.

As a side note, it's important not to define Fibonacci<1> above Fibonacci<0>, or your compiler will get very confused when it resolves the call to Fibonacci<0>::add_values, since Fibonacci<0>'s template specialization has not been specified.

Of course, TMP has its limitations: You need a precomputed maximum, and getting the values at run-time requires recursion (since templates are defined recursively).

Solution 2:

I know this question is old, but it intrigued me and I had to have a go at doing without a dynamic container filled at runtime:

#ifndef _FIBONACCI_HPP
#define _FIBONACCI_HPP


template <unsigned long N>
struct Fibonacci
{
    static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;

    static unsigned long long get_value(unsigned long n)
    {
        switch (n) {
            case N:
                return value;
            default:
                return n < N    ? Fibonacci<N-1>::get_value(n)
                                : get_value(n-2) + get_value(n-1);
        }
    }
};

template <>
struct Fibonacci<0>
{
    static const unsigned long long value = 0;

    static unsigned long long get_value(unsigned long n)
    {
        return value;
    }
};

template <>
struct Fibonacci<1>
{
    static const unsigned long long value = 1;

    static unsigned long get_value(unsigned long n)
    {
        return value;
    }
};

#endif

This seems to work, and when compiled with optimizations (not sure if you were going to allow that), the call stack does not get to deep - there is normal runtime recursion on the stack of course for values (arguments) n > N, where N is the TableSize used in the template instantiation. However, once you go below the TableSize the generated code substitutes a constant computed at compile time, or at worst a value "computed" by dropping through a jump table (compiled in gcc with -c -g -Wa,-adhlns=main.s and checked the listing), the same as I reckon your explicit switch statement would result in.

When used like this:

int main()
{
    std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n';
    std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n';
}

There is no call to a computation at all in the first case (value computed at compile time), and in the second case the call stack depth is at worst:

fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41)  Line 18 + 0xe bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45)  Line 18 + 0xe bytes    C++
fibtest.exe!main()  Line 9 + 0x7 bytes    C++
fibtest.exe!__tmainCRTStartup()  Line 597 + 0x17 bytes    C

I.e. it recurses until it finds a value in the "Table". (verified by stepping through Disassembly in the debugger line by line, also by replacing the test ints by a random number <= 45)

The recursive part could also be replaced by the linear iterative solution:

static unsigned long long get_value(unsigned long n)
{
    switch (n) {
        case N:
            return value;    
        default:
            if (n < N) {
                return Fibonacci<N-1>::get_value(n);
            } else {
                // n > N
                unsigned long long i = Fibonacci<N-1>::value, j = value, t;
                for (unsigned long k = N; k < n; k++) {
                    t = i + j;
                    i = j;
                    j = t;
                }
                return j;
            }
    }
}

Solution 3:

If you have C++ compiler which supports variadic templates (C++0x standard ) you can save fibonacii sequence in a tuple at the compile time. At runtime you can access any element from that tuple by indexing.

#include <tuple>   
#include <iostream>

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

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

template<>
struct Fib<0>
{
    enum { value = 0 };
};

// ----------------------
template<int N, typename Tuple, typename ... Types>
struct make_fibtuple_impl;

template<int N, typename ... Types>
struct make_fibtuple_impl<N, std::tuple<Types...> >
{
    typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type;
};

template<typename ... Types>
struct make_fibtuple_impl<0, std::tuple<Types...> >
{
    typedef std::tuple<Fib<0>, Types... > type;
};

template<int N>
struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> >
{};

int main()
{
   auto tup = typename make_fibtuple<25>::type();
   std::cout << std::get<20>(tup).value;  
   std::cout << std::endl; 

   return 0;
}

Solution 4:

With C++11: you may create a std::array and a simple getter: https://ideone.com/F0b4D3

namespace detail
{

template <std::size_t N>
struct Fibo :
    std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value>
{
    static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value,
                  "overflow");
};

template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {};
template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {};

template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>(
        std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n];
}

template <std::size_t N>
constexpr std::size_t fibo(std::size_t n)
{
    return n < N ?
        fibo(n, make_index_sequence<N>()) :
        throw std::runtime_error("out of bound");
}
} // namespace detail

constexpr std::size_t fibo(std::size_t n)
{
    // 48u is the highest
    return detail::fibo<48u>(n);
}

In C++14, you can simplify some function:

template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    constexpr std::array<std::size_t, sizeof...(Is)> fibos{{Fibo<Is>::value...}};
    return fibos[n];
}