c++ power of integer, template meta programming

Question

I want to make a function which returns a power of integer. Please read the fmuecke's solution in power of an integer in c++ .

However, I want to generalize his solution to the arbitrary type T. Since c++11 has constexpr, I guess this is possible.

Naively, I tried something like,

template<class T, int N>
inline constexpr T pow(const T x){
    return pow<N-1>(x) * x;
}
template<class T>
inline constexpr T pow<T, 1>(const T x){
    return x;
}
template<class T>
inline constexpr T pow<T, 0>(const T x){
    return 1;
}

Actually this approach failed since the partial specialization for function template is not allowed.

And one more question. I heard that it is up to the compiler whether the constexpr function is evaluated in compile time or not. How do I force it to compute for general type. I read from somewhere that one of the simplest hack for integral consts is to wrap it in std::integral_const::value.

Answer 1

Solution using recursion:

#include <iostream>

template<class T>
inline constexpr T pow(const T base, unsigned const exponent)
{
    // (parentheses not required in next line)
    return (exponent == 0) ? 1 : (base * pow(base, exponent-1));
}

int main()
{
    std::cout << "pow(2, 4): " << pow(2, 4) << std::endl;
    std::cout << "pow(5, 0): " << pow(5, 0) << std::endl;
}

Jeremy W. Murphy suggested/requested a version using exponentiation by squaring:

template<class T>
inline constexpr T pow(const T base, unsigned const exponent)
{
    // (parentheses not required in next line)
    return (exponent == 0)     ? 1 :
           (exponent % 2 == 0) ? pow(base, exponent/2)*pow(base, exponent/2) :
           base * pow(base, (exponent-1)/2) * pow(base, (exponent-1)/2);
}

---

"I heard that it is up to the compiler whether the constexpr function is evaluated in compile time or not."

True, AFAIK. The compiler isn't required to do constant-initialization at compile-time, but if you use the result of a constexpr function as a non-type template argument, it has to compute the result at compile-time.

std::cout << std::integral_constant<int, pow(2, 4)>::value << std::endl;

Also see the approach using integral_constant as parameter of pow in Andy Prowl's answer.

Here's how you can enforce compile-time evaluation:

#include <iostream>
#include <type_traits>

// insert a constexpr `pow` implementation, e.g. the one from above

template < typename T, T base, unsigned exponent >
using pow_ = std::integral_constant < T, pow(base, exponent) >;

// macro == error prone, you have been warned
#define POW(BASE, EXPONENT) (pow_ < decltype(BASE), BASE, EXPONENT > :: value)

int main()
{
    std::cout << "pow(2, 4): " << pow_<int, 2, 4>::value << std::endl;
    std::cout << "pow(2, 4): " << POW(2, 4) << std::endl;
}

---

Please leave a comment if you downvote so I can improve my answer.

Answer 2

When you find yourself in need of partially specializing a function template (beware, this does not mean that in this case you are in need, as DyP's answer shows), you may either resort to overloading (see the last update at the end of this answer) or, if that's not possible, wrap that function template into a class template, and have a static, non-template member function replace your original function template (and its specializations):

namespace detail
{
    template<class T, int N>
    struct helper
    {
        static constexpr T pow(const T x){
            return helper<T, N-1>::pow(x) * x;
        }
    };

    template<class T>
    struct helper<T, 1> // Unnecessary specialization! (see the edit)
    {
        static constexpr T pow(const T x){
            return x;
        }
    };

    template<class T>
    struct helper<T, 0>
    {
        static constexpr T pow(const T x){
            return 1;
        }
    };
}

Then, you could provide a helper function template that delegates to the specialization of your helper class template:

template<int N, class T>
T constexpr pow(T const x)
{
    return detail::helper<T, N>::pow(x);
}

Here is a live example.

EDIT:

Notice, that the specialization for N == 1 is actually not necessary. I kept it in the original text because the purpose of this answer was mainly to show how to workaround the impossibility of partially specializing function templates in general - so I translated the original program piece-by-piece.

As noted by Dyp in the comments, however, this would be enough:

namespace detail
{
    template<class T, int N>
    struct helper
    {
        static constexpr T pow(const T x){
            return helper<T, N-1>::pow(x) * x;
        }
    };

    template<class T>
    struct helper<T, 0>
    {
        static constexpr T pow(const T x){
            return 1;
        }
    };
}

UPDATE:

As a further remark, please keep in mind that even when you can specialize function templates (e.g. with explicit - not partial - specializations), it is generally not a good idea to do so, because function template specialization does not normally behave as one would expect.

Most of those situations that may seem to ask for function template specialization can actually be achieved through overloading, powered by well-known techniques such as tag dispatching. An example is proposed by Potatoswatter in the comments, pointing out that std::integral_constant could be used in this situation:

template<class T>
inline constexpr T pow(const T x, std::integral_constant<T, 0>){
    return 1;
}

template<class T, int N>
inline constexpr T pow(const T x, std::integral_constant<T, N>){
    return pow(x, std::integral_constant<T, N-1>()) * x;
}

template<int N, class T>
inline constexpr T pow(const T x)
{
    return pow(x, std::integral_constant<T, N>());
}

However, all these guidelines on "how to solve problems that seem to require function template partial specialization" should be taken into consideration when they are really needed. In this concrete case, as DyP showed in his answer, they are not.

Answer 3

Here is a solution with a single function:

template <int N, class T> 
constexpr T pow(const T& x) 
{
    return N > 1 ? x*pow<(N-1)*(N > 1)>(x) 
                 : N < 0 ? T(1)/pow<(-N)*(N < 0)>(x) 
                         : N == 1 ? x 
                                  : T(1);
}

Answer 4

Here is a simple solution:

#include<bits/stdc++.h>
using namespace std;

template<int N, int M>
struct Pow
{
    enum { res = N * Pow<N,M-1>::res};
};


template<int N>
struct Pow<N,0>
{
    enum {res = 1};
};
int main()
{
    cout<<Pow<2,3>::res<<"\n";
}