Template metaprogramming calculations

[Hobson]

Hello,

Recently I am trying to learn something new, and I found out that compilation time calculations would be very useful for me quite often. So, I grabbed my copy of google, looked up some sites, and came with this example:

#include <iostream>

template <int 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};
};


int fibonacci(int which) {

	//WHAT GOES HERE?
}

int main() {
	std::cout << "15th Fibonacci number is "<< Fibonacci<15>::value << '\n';

	int which;
	std::cout << "Which Fibonacci number you want to calculate? ";
	std::cin >> which;

	std::cout << which << ". Fibonacci number is " << fibonacci(which) << '\n';
}

Simple as it is, I seem to miss something basic. The thing is, I just do not get how all these precalculated values can help me at runtime. I do not know how to "map" variable value to precalculated template class.
What I do not know yet? What am I doing wrong? Are my expectations that I can somehow "bind" runtime values with ones calculated by metaprogram wrong?

Cheers,
Maciek

[Lindley]

Hmm. I wonder if the compiler is smart enough to optimize that down to (essentially) the dynamic programming algorithm for Fib numbers, or if it'll go for the full exponential-time recursion.....

The thing about template programming as I understand it is that it will give you any constant value *in the code* that you ask for. It won't give you things you can loop over at runtime unless you declare them in an array at compile-time, for instance.

[treuss]

I haven't really read or done much in that direction, so the below are just some thought on my own. If you define the fibonacci function like below, it should perform significantly faster than a traditional implemenation, due to the fact that some "breakpoints" are compile-time computed.

long fibonacci(int which) {
    if (which == 0) return 0;
    if (which == 1) return 1;
    if (which == 10) return Fibonacci<10>::value;
    if (which == 20) return Fibonacci<20>::value;
    if (which == 30) return Fibonacci<30>::value;
    if (which == 40) return Fibonacci<40>::value;
    // if (which == 100) return Fibonacci<100>::value; /* uncomment for some interessting compiler errors */

    return fibonacci(which-1) + fibonacci(which-2);
}

I might be wrong, but I don't think there is a way to really map runtime values to template parameters, as the compiler can impossibly know if a template for any runtime value has in fact been instantiated. E.g. for your example, only templates for values 0-15 have been instantiated and thus only those values have been compile-time calculated.

[Hobson]

I was thinking a little, and I came with following solution:

//Edited a bit from original version to make compilers more happy
//because not all are as forgiving as VS 2008 is :)
//Still, comeau complains about cout << unsigned long long

#include <iostream>

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

	static unsigned long long get(int n) {
		if(n == N)
			return value;
		else
			return Fibonacci<N-1>::get(n);
	}
};

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

	static unsigned long long get(int n) {
		if(n == 1)
			return value;
		else
			return 0;//Fibonacci<0>::get(n); //NO GO?
	}

};

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

	static unsigned long long get(int n) {
		return value;
	}
};

template <int FIB_MAX = 93>
class FibonacciGenerator {


	typedef Fibonacci<FIB_MAX> fibMax;
	static unsigned long long numbers[FIB_MAX + 1];

public:
	static unsigned long long get(int which) {
		if(numbers[which]) {
			return numbers[which];
		} else {
			return numbers[which] = fibMax::get(which);
		}
	}

};

template <int FIB_MAX>
unsigned long long FibonacciGenerator<FIB_MAX>::numbers[FIB_MAX + 1];

unsigned long long fibonacci(int which) {

	return FibonacciGenerator<>::get(which);
}

int main() {
	std::cout << "15th Fibonacci number is "<< FibonacciGenerator<>::get(15) << '\n';

	int which;
	std::cout << "Which Fibonacci number you want to calculate? ";
	std::cin >> which;

	std::cout << which << ". Fibonacci number is " << fibonacci(which) << '\n';
}

It works exactly as I need, however I'd like to ask you all what you thinkk about it. It is not hard to undestand how it works, because idea is generally simple. Still there are some drawbacks of this approach:
- One has to define max value for calculations, and somehow respond to out-of-bounds ones. Like, create class Fibonacci<50> and its get(int) function should throw or something. But with runtime calculations problem is the same.
- Value lookup is somewhat slow. It goes value by value, and, since I have no access to optimizing compiler, I doubt whether it is anything near to efficient. Asking for FibonacciGenerator::get(1) takes 60 steps if results are not cached. Moreover, stack space is used heavily for nested function call.
- Previous issue might be resolved with caching, but sometimes it may require really large arrays. Fibonacci sequence is simple example which overflows fast, so there is at most ~50 elements. However there are suequences, which I think would not fit into 1GB memory, and some mixed approach would be needed (runtime calculations for high values, which resort to precompiled ones when available).

Or maybe my approach is just simply wrong? Maybe it would be better, more clear and/or efficient to make all calculations at runtime, simply because they are depending on runtime input? Maybe there is no need to mess with templates and metaprograms?

Please tell me what you think about this code and tell me if you know any better solutions, since this one was found by myslef because I did not get any answer here, nor could find any on the web.

Cheers,
Hob