It's a Fibonacci number generator. The "cool" part is that it has support for big integers, and it converts big integers to strings (char arrays, really) at compile time.
// I'm too lazy to comment this really well.
// If you're compiling with g++ and you hit the template instantiation limit, you
// can use -ftemplate-depth-NN to increase the maximum
// Written by Michael Bradshaw
// Some indentation my be messed up in this code paste...
#include <iostream>
// Various math functions
template <unsigned int b, unsigned int i>
struct log
{
enum { value = !!(i / b) + log<b, i / b>::value };
};
template <unsigned int b>
struct log<b, 0>
{
enum { value = 0 };
};
template <unsigned int i>
struct log2
{
enum { value = log<2, i>::value };
};
template <unsigned int i>
struct log10
{
enum { value = log<10, i>::value };
};
template <unsigned int b, unsigned int e>
struct pow
{
enum { value = b * pow<b, e - 1>::value };
};
template <unsigned int b>
struct pow<b, 0>
{
enum { value = 1 };
};
// I would use numeric_limits, but it's max() function isn't a constant
// expresion (in C++03)
template <typename T>
struct limits
{
enum { max = (T)(-1) };
};
// Conditional epxressions
template <bool expression, typename if_true, typename if_false>
struct if_then_else
{
typedef if_true result;
};
template <typename if_true, typename if_false>
struct if_then_else<false, if_true, if_false>
{
typedef if_false result;
};
// A big integer struct... really it's just a linked list, but it has special rules about
// keeping each element's values within the specified base (and carrying over when needed)
template <unsigned int v, typename next_big_uint>
struct big_uint
{
enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
value = v % base };
typedef typename if_then_else<v < base,
next_big_uint,
typename big_uint<next_big_uint::value + v / base,
typename next_big_uint::next>::canonical>::result next;
typedef big_uint<v % base, typename next::canonical> canonical;
};
// End of the linked list
template <unsigned int v>
struct big_uint<v, void>
{
enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
value = v % base };
typedef typename if_then_else<v < base,
void,
typename big_uint<v / base,
void>::canonical>::result next;
typedef big_uint<v % base, next> canonical;
};
// Having a zero case lets some canonicalization be done
template <>
struct big_uint<0, void>
{
enum { base = pow<10, log10<limits<unsigned int>::max>::value / 2>::value,
value = 0 };
typedef void next;
typedef big_uint<0, void> canonical;
};
// Logic for adding two big integers
template <typename a, typename b>
struct add
{
typedef typename big_uint<a::value + b::value,
typename add<typename a::next,
typename b::next>::result>::canonical result;
};
template <unsigned int av, typename b>
struct add<big_uint<av, void>, b>
{
typedef typename big_uint<av + b::value, typename b::next>::canonical result;
};
template <typename a, unsigned int bv>
struct add<a, big_uint<bv, void> >
{
typedef typename big_uint<a::value + bv, typename a::next>::canonical result;
};
template <unsigned int av, unsigned int bv>
struct add<big_uint<av, void>, big_uint<bv, void> >
{
typedef typename big_uint<av + bv, void>::canonical result;
};
// Fibonacci implementation detail... just keeps the public interface pretty
template <unsigned int i, typename a, typename b>
struct detail_fib
{
typedef typename detail_fib<i - 1, b, typename add<a, b>::result>::result result;
};
template <typename a, typename b>
struct detail_fib<0, a, b>
{
typedef typename add<a, b>::result result;
};
// Pretty public interface for the Fibonacci sequence; given the parameter i, it
// calculates the ith number in the Fibonacci sequence
template <unsigned int i>
struct fibonacci
{
typedef typename detail_fib<i - 2, big_uint<0, void>, big_uint<1, void> >::result result;
};
template <>
struct fibonacci<0>
{
typedef big_uint<0, void> result;
};
template <>
struct fibonacci<1>
{
typedef big_uint<1, void> result;
};
// Some math functions for taking the log10 of a big integer
template <typename v>
struct big_log10
{
enum { value = log10<v::base>::value + big_log10<typename v::next>::value };
};
template <unsigned int v>
struct big_log10<big_uint<v, void> >
{
enum { value = log10<v>::value };
};
// Got this idea from http://stackoverflow.com/a/3499919/1287251
// Modified it a bit; compile time strings! Yay!
template <typename v, unsigned int n = big_log10<v>::value + 1, unsigned int i = 0>
struct cstring : public cstring<v, n, i + 1>
{
static const char dummy;
};
template <typename v, unsigned int n>
struct cstring<v, n, n>
{
static const char dummy;
static char str[n + 1];
};
template <typename v, unsigned int n>
const char cstring<v, n, n>::dummy = 0 * cstring<v, n, 0>::dummy;
template <typename v, unsigned int n>
char cstring<v, n, n>::str[n + 1] = {cstring<v, n, n>::dummy}; // fill str with all zeros
// Used to actually populate the string; given a big integer v and a string index i,
// it computes the corresponding character for the reversed string (the logic is
// easier if you reverse the string)
template <typename v, unsigned int i, bool use_this = i < log10<v::base>::value>
struct to_string_detail
{
enum { value = '0' + (v::value / pow<10, i>::value) % 10 };
};
template <typename v, unsigned int i>
struct to_string_detail<v, i, false>
{
enum { value = to_string_detail<typename v::next, i - log10<v::base>::value>::value };
};
// Use to_string_detail to extract characters and actually populate the string
template <typename v, unsigned int n, unsigned int i>
const char cstring<v, n, i>::dummy = cstring<v, n, n>::str[i] = to_string_detail<v, n - 1 - i>::value + 0 * cstring<v, n, i + 1>::dummy;
// Same as cstring<n>, really, but just a different name to convey meaning
template <typename n>
struct to_string : public cstring<n>
{
};
int main()
{
std::cout << "Fibonacci number generate (at compile time!)\n"
<< "F_N indicates the Nth Fibonacci number" << std::endl;
std::cout << "F_0:\t" << to_string<fibonacci<0>::result>::str << std::endl;
std::cout << "F_50:\t" << to_string<fibonacci<50>::result>::str << std::endl;
std::cout << "F_100:\t" << to_string<fibonacci<100>::result>::str << std::endl;
std::cout << "F_150:\t" << to_string<fibonacci<150>::result>::str << std::endl;
std::cout << "F_200:\t" << to_string<fibonacci<200>::result>::str << std::endl;
std::cout << "F_250:\t" << to_string<fibonacci<250>::result>::str << std::endl;
std::cout << "F_300:\t" << to_string<fibonacci<300>::result>::str << std::endl;
std::cout << "F_350:\t" << to_string<fibonacci<330>::result>::str << std::endl;
std::cout << "F_400:\t" << to_string<fibonacci<400>::result>::str << std::endl;
}
Anyone else have any cool template metaprogramming demos?
Edit: Here's some output for those of you too lazy to compile this sucker :
Fibonacci number generate (at compile time!)
F_N indicates the Nth Fibonacci number
F_0: 0
F_50: 12586269025
F_100: 354224848179261915075
F_150: 9969216677189303386214405760200
F_200: 280571172992510140037611932413038677189525
F_250: 7896325826131730509282738943634332893686268675876375
F_300: 222232244629420445529739893461909967206666939096499764990979600
F_350: 413462646668428032346940119724892718502248750418536685577487386752440
F_400: 176023680645013966468226945392411250770384383304492191886725992896575345044216019675