template metaprogramming problem

Hi, I have a struct POW which calculates the power of a number in compiletime, and it looked like this before:

Code:

template<uint64 b, uint n>
struct POW {
private: 
    STATIC_ASSERT(b <= 1 || n < (sizeof b) * CHAR_BIT);  /* Quick check for power overflow */
    enum {pre_pow = b > 1 && n ? POW<b, n/2>::value : 1,
          factor = pre_pow * (n & 1 ? b : 1) };
    STATIC_ASSERT(b <= 1 || n == 0 ||
                  pre_pow*factor/factor == pre_pow); /* Extensive check for power overflow */
public: 
    enum {value = (b == 1 || n == 0 ? 1 :
                   b <= 1           ? 0 :
                   pre_pow * factor)};
};

But I got the compile error

Code:

preprocessing.hpp: In instantiation of `POW<2ull, 0u>':
preprocessing.hpp:41:   instantiated from `POW<2ull, 1u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 2u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 4u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 8u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 16u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 32u>'
integer.hpp:51:   instantiated from here
preprocessing.hpp:41: error: incomplete type `POW<2ull, 0u>' used in nested name specifier
preprocessing.hpp:41: error: enumerator value for `pre_pow' not integer constant

Line 41 is the line where I calculate pre_pow. So I changed the line to

Code:

pre_pow = b > 1 && n ? POW<b, n/2 - !n>::value : 1

instead, and now I get this error:

Code:

preprocessing.hpp: In instantiation of `POW<2ull, -1u>':
preprocessing.hpp:41:   instantiated from `POW<2ull, 0u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 1u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 2u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 4u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 8u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 16u>'
preprocessing.hpp:41:   instantiated from `POW<2ull, 32u>'
integer.hpp:51:   instantiated from here
preprocessing.hpp:40: error: invalid application of `sizeof' to incomplete type `COMPILE_TIME_ERROR<1u>'

Why do I get this error? Does it maybe have to do with my STATIC_ASSERT macro (which is tested and should work)?

Everything works fine though if I add an extra

Code:

template<uint64 b> struct POW<b, 0> { enum {value = 1}; };

afterwards. This however, I didn't need to do for my LOG_B struct which works perfectly; it looks like this by the way:

Code:

template<uint b, uint64 n>
struct LOG_B {
    STATIC_ASSERT(b > 1);
    STATIC_ASSERT(n > 0);
    enum {value = n >= b ? LOG_B<b, n/b>::value + 1 : 0};
};

Unfortunately, I don't have the time right now to go over the template. I'm sure someone else will, though.

That said, you're welcome to use this one (or at least it can be used as a reference):

Code:

namespace impl_ {

template < size_t Base, size_t Exponent, size_t Accumulator >
struct static_pow_calculator
{
    enum
    {
        value = static_pow_calculator
        < 
            Base, 
            Exponent - 1, 
            Accumulator * Base 
        >::value
    };
};

template < size_t Base, size_t Accumulator >
struct static_pow_calculator< Base, 0, Accumulator >
{
    enum
    {
        value = Accumulator
    };
};

}

template < size_t Base, size_t Exponent >
struct static_pow
{
    enum
    {
        value = impl_::static_pow_calculator< Base, Exponent, 1 >::value
    };
};

Good luck, either way.

As far as I can see, your problem is trying to use ?: for meta-programming. The compiler will instantiate templates in both operands, regardless of whether the condition is true or false.

Your LOG_B structs should fire the static_asserts for the same reason (unless perhaps your STATIC_ASSERT is something bizarre that somehow manages to stop the recursion without causing an error).

This enum hack is outdated and not necessary on modern compilers. Use static constants instead. And the decision-making ?: operator is completely unnecessary.

Code:

template < unsigned int B, unsigned int N >
class Power
{
public:
    static const unsigned int Value = B * Power< B, N - 1 >::Value;
};

template < unsigned int B >
class Power< B, 0 >
{
public:
    static const unsigned int Value = 1;
};

Thanks anon, it was right as you said; you need to have special template for when n=0. Maybe g++ optimized it in my case with LOG_B; I think it instantiated the template (hence I got the error incomplete type `POW<2ull, 0u>' used in nested name specifier), but realized that it didn't have to calculate value (hence I didn't get an infinite recursion and the same problem in LOG_B).

Anyway, I changed the 'enum hack' into const static uint64, and it works very well. In the latter case in my previous post, STATIC_ASSERT had been triggered because my overflow test failed thanks to the lack of capacity in enum; using uint64 instead solved the problem.

Here's the code now, I have tested it with several different arguments and it seems to do well:

Code:

/*********/
/* LOG_B */
/*********/

template<uint64 b, uint64 n>
struct LOG_B { /* Rounds down */
    /* Check for arguments outside definition set */
    STATIC_ASSERT(b != 0 && b != 1); /* Invalid base */
    STATIC_ASSERT(n != 0);
    const static uint value = LOG_B<b, n/b + (n < b)>::value + (n >= b);
};
template<uint64 b>
struct LOG_B<b, 1> {STATIC_ASSERT(b > 1); const static uint value = 0;};

/*******/
/* POW */
/*******/

template<uint64 b, uint n>
struct POW {
private:
    const static uint64 pre_pow = b > 1 ? POW<b, n/2>::value : b;
    const static uint64 factor  = pre_pow * (n & 1 ? b : 1);
    /* Check for overflow */
    STATIC_ASSERT(pre_pow*factor/(b ? factor : 1) == pre_pow);
public: 
    const static uint64 value = pre_pow * factor;
};
template<uint64 b> struct POW<b, 0> {const static uint64 value = 1;};

If anyone is interested of the code. Here uint64 is simply a typedef of uint_64 in stdint.h.

This is what I used to test the templates:

Code:

    cout << "2^63: " << POW<2, 63>::value << endl;
    //cout << "2^64: " << POW<2, 64>::value << endl; //Overflow
    cout << "11^4: " << POW<11, 4>::value << endl;
    cout << "1^63: " << POW<1, 63>::value << endl;
    cout << "0^63: " << POW<0, 63>::value << endl;
    cout << "2^0: " << POW<2, 0>::value << endl;
    cout << "1^0: " << POW<1, 0>::value << endl;
    cout << "0^0: " << POW<0, 0>::value << endl;
    cout << "0^1: " << POW<0, 1>::value << endl;
    cout << endl;
    cout << "log_2(63): " << LOG_B<2, 63>::value << endl;
    cout << "log_2(64): " << LOG_B<2, 64>::value << endl;
    cout << "log_2(2^63): " << LOG_B<2, POW<2, 63>::value>::value << endl;
    //cout << "log_2(0): " << LOG_B<2, 0>::value << endl; //Undefined; -> -inty. when x -> 0+
    //cout << "log_0(64): " << LOG_B<0, 64>::value << endl; //Undefined, but -> 0- when base -> 0+
    //cout << "log_1(64): " << LOG_B<1, 64>::value << endl; //Undefined; -> +inty. when base -> 1+
    //--------------------------------||-------------------------------- -> -inty. when base -> 1-
    cout << "log_10(10): " << LOG_B<10, 10>::value << endl;
    cout << "log_10(9): " << LOG_B<10, 9>::value << endl;
    cout << "log_10(10): " << LOG_B<10, 10>::value << endl;
    cout << "log_10(99): " << LOG_B<10, 99>::value << endl;
    cout << "log_10(100): " << LOG_B<10, 100>::value << endl;
    cout << endl;
    system("PAUSE");

Sebastiani, I know it's good to do what you do if you're programming in Lisp (to make a function become iterative), but is there any purpose with doing that in this case?