Getting template metaprogramming compile-time constants at runtime

Question

Background

Consider the following:

template <unsigned N> struct Fibonacci {     enum     {         value = Fibonacci<N-1>::value + Fibonacci<N-2>::value     }; };  template <> struct Fibonacci<1> {     enum     {         value = 1     }; };  template <> struct Fibonacci<0> {     enum     {         value = 0     }; }; 

This is a common example and we can get the value of a Fibonacci number as a compile-time constant:

int main(void) {     std::cout << "Fibonacci(15) = ";     std::cout << Fibonacci<15>::value;     std::cout << std::endl; } 

But you obviously cannot get the value at runtime:

int main(void) {     std::srand(static_cast<unsigned>(std::time(0)));      // ensure the table exists up to a certain size     // (even though the rest of the code won't work)     static const unsigned fibbMax = 20;     Fibonacci<fibbMax>::value;      // get index into sequence     unsigned fibb = std::rand() % fibbMax;      std::cout << "Fibonacci(" << fibb << ") = ";     std::cout << Fibonacci<fibb>::value;     std::cout << std::endl; } 

Because fibb is not a compile-time constant.

Question

So my question is:

What is the best way to peek into this table at run-time? The most obvious solution (and "solution" should be taken lightly), is to have a large switch statement:

unsigned fibonacci(unsigned index) {     switch (index)     {     case 0:         return Fibonacci<0>::value;     case 1:         return Fibonacci<1>::value;     case 2:         return Fibonacci<2>::value;     .     .     .     case 20:         return Fibonacci<20>::value;     default:         return fibonacci(index - 1) + fibonacci(index - 2);     } }  int main(void) {     std::srand(static_cast<unsigned>(std::time(0)));      static const unsigned fibbMax = 20;          // get index into sequence     unsigned fibb = std::rand() % fibbMax;      std::cout << "Fibonacci(" << fibb << ") = ";     std::cout << fibonacci(fibb);     std::cout << std::endl; } 

But now the size of the table is very hard coded and it wouldn't be easy to expand it to say, 40.

The only one I came up with that has a similiar method of query is this:

template <int TableSize = 40> class FibonacciTable { public:     enum     {         max = TableSize     };      static unsigned get(unsigned index)     {         if (index == TableSize)         {             return Fibonacci<TableSize>::value;         }         else         {             // too far, pass downwards             return FibonacciTable<TableSize - 1>::get(index);         }     } };  template <> class FibonacciTable<0> { public:     enum     {         max = 0     };      static unsigned get(unsigned)     {         // doesn't matter, no where else to go.         // must be 0, or the original value was         // not in table         return 0;     } };  int main(void) {     std::srand(static_cast<unsigned>(std::time(0)));      // get index into sequence     unsigned fibb = std::rand() % FibonacciTable<>::max;      std::cout << "Fibonacci(" << fibb << ") = ";     std::cout << FibonacciTable<>::get(fibb);     std::cout << std::endl; } 

Which seems to work great. The only two problems I see are:

• Potentially large call stack, since calculating Fibonacci<2> requires we go through TableMax all the way to 2, and:

• If the value is outside of the table, it returns zero as opposed to calculating it.

So is there something I am missing? It seems there should be a better way to pick out these values at runtime.

A template metaprogramming version of a switch statement perhaps, that generates a switch statement up to a certain number?

Thanks in advance.

Answer 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).

Answer 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;             }     } }