How to precompute array of values?

Question

Is there a way to pre-compute an array of values based on templates? In the following example I would like the 'powers_of_2' array to have 256 values computed at compile-time if that is possible without having to type all of the values.

#include <iostream>
using namespace std;

template <int X, char Y>
struct power {
   enum { value = X * power<X,Y-1>::value };
};

template <int X>
struct power<X,1> {
   enum { value = X };
};

template <int X>
struct power<X,0> {
   enum { value = 1 };
};

int _tmain(int argc, _TCHAR* argv[])
{
   int powers_of_2[] = { power<2,0>::value, power<2,1>::value, ..., power<2,255>::value };
   cout << powers_of_2[1] << endl;
   return 0;
}

Answer 1

That is exactly what a macro is useful for...

Answer 2

Unless you plan on using a big integer package you will overflow the integer type at 2^32 (or 2^64, depending), but to answer your real question look at this wikipedia article on template metaprogramming.

Answer 3

You could easily write a small script to prepopulate the array for you using your preferred scripting language. Depending on the compiler and preprocessor you use, you should also be able to do it as a macro.

Answer 4

Holding the value 2^255 would require 32 bytes. This cannot be held in an int; you'd need a char array

typedef unsigned char BYTE32[32];
BYTE32 powers_of_2[256] =
{
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,16},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,64},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,128},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0},
// :
// :
  {32,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {64,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};

Answer 5

I agree with Lokkju. It is not possible to initialize the array by only means of template metaprogramming and macros in this case are very useful. Even Boost libraries make use of macros to implement repetitive statements.

Examples of useful macros are available here: http://awgn.antifork.org/codes++/macro_template.h

Answer 6

What I do in situations like that is write a small program that generates and writes to a file the array initialization in C++ source and then #include that file. This technique is simple and effective.