template metaprogramming problem

This is a discussion on template metaprogramming problem within the C++ Programming forums, part of the General Programming Boards category; Hi, I have a struct POW which calculates the power of a number in compiletime, and it looked like this ...

  1. #1
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286

    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};
    };
    Last edited by TriKri; 10-28-2009 at 07:53 AM.
    Come on, you can do it! b( ~_')

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    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.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    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;
    };
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286
    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");
    Come on, you can do it! b( ~_')

  6. #6
    Algorithm engineer
    Join Date
    Jun 2006
    Posts
    286
    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?
    Come on, you can do it! b( ~_')

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template object creation problem
    By babu198649 in forum C++ Programming
    Replies: 7
    Last Post: 09-16-2008, 04:02 AM
  2. matrix class
    By shuo in forum C++ Programming
    Replies: 2
    Last Post: 07-13-2007, 01:03 AM
  3. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  4. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  5. Problem with template usage
    By rmullen3 in forum C++ Programming
    Replies: 2
    Last Post: 02-23-2002, 05:30 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21