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.

Mignonmignonette

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.

Fournier

@BЈовић No it isn't but why do you need a template metaprogramming approach? You can use constexpr functions (and their results) in metaprogramming as well. – Fournier

@BЈовић: Seriously, who cares? “Are you sure you used the blue hammer for this nail?” – Groos

@ChristopherCreutzig Ok, the title confused me. – Rotunda

@BЈовић sorry for the confusion title. Maybe it should be changed to compile time power of int. – Mignonmignonette

Please, explain the rationale after the Yoda Condition (0 == N), I think that there's a good reason to do the constant == value trick but I cannot explain it. – Fetial

@Fetial If you're referring to the order (constant first, then variable) that is to prevent errors like if(N = 0). I'll update the code to make N const as well, it doesn't matter here. – Fournier

@DyP yes, I was referring to that, but I betted that the reason was more impressive :P – Fetial

It would be even better if it used exponentiation by squaring. – Lilly

Thanks for the great answer. As a small c++20 update you could mention that replacing constexpr with consteval to enforce compile-time evaluation. – Monochasium

@Monochasium Hmm, not sure if consteval strictly requires evaluation at compile-time... I mean, a consteval function call must be possible to evaluate at compile, but who is forcing the compiler to do so? – Fournier

@Fournier Now that you say that, I am not sure either. I thought that was the whole point of consteval and I guess every halfway decent compiler will evaluate at compile-time to perform further optimizations, but the description on this page does not say that the compiler has to perform a compile-time evaluation. So it seems you are right. Still asking myself, if there is any case, a compiler might choose to not evaluate at compile-time... – Monochasium

@Monochasium See https://mcmap.net/q/282774/-is-compiler-allowed-to-call-an-immediate-consteval-function-during-runtime and https://mcmap.net/q/282775/-what-are-the-advantages-of-using-consteval-instead-of-constexpr-function – Fournier

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<int, 0>){
    return 1;
}

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

template<int N, class T>
inline constexpr T pow(const T x)
{
    return pow(x, std::integral_constant<int, 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.

Malorie

@taocp: Thanks a lot for your appreciation, but you are celebrating me more than I deserve ;) I wish I knew every bit of C++ – Malorie

Is the partial specialization for N == 1 required? – Fournier

@DyP: Good catch, actually no, it isn't. The purpose of my answer was mostly to show the OP how to translate a function template partial specialization into a class template partial specialization. But I will edit, thank you – Malorie

Thank you. It helps me a lot. I was having hard time to pick the accepted answer. Because both were great. – Mignonmignonette

I just picked the simplest solution. Sorry. – Mignonmignonette

@Sungmin: That's all right, DyP's answer shows the right way to solve this particular problem, mine was mostly a guideline for more general situations – Malorie

More general guideline is, if you feel you need function template partial specialization, use overloading instead. This can be done using a std::integral_constant argument instead of a helper class. Essentially a form of tag dispatching. – Desta

@Potatoswatter: Indeed, overloading is in general preferable over function template specialization, but it does not always replace it - although in this case it does. I will edit the answer, anyway – Malorie

@Sungmin: Thank you, although what Potatoswatter wrote is correct - and I tried to reflect that in the last update to my answer – Malorie

@0x499602D2: Indeed, it does (7.1.5/2) – Malorie

Is both constexpr and inline really needed? – Coley

@0x499602D2: No, it is not – Malorie

@0x499602D2: I copy-pasted the example from the OP's text and shown the minimal fixes. Probably the same applies for the accepted answer. Also, it is possible that by the time I answered I did not know about this yet – Malorie

N should be unsigned. – Discompose

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);
}

Wombat

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";
}

Julianajuliane

Cool solution, this is what I was looking for – Algophobia

M should be unsigned. – Discompose

Answer 5

Clean and simple solution here:

#include <cstddef>

template<size_t N, size_t P>
struct pow_constexpr { constexpr static auto value = N * pow_constexpr<N, P-1>::value; };

template<size_t N>
struct pow_constexpr<N, 1> { constexpr static auto value = N; };

template<size_t N>
struct pow_constexpr<N, 0> { constexpr static auto value = 1; };

int main() {
    return pow_constexpr<2, 30>::value; // 1073741824
}

Tooth

pow_constexpr<N, 1> not needed. Others above can calculate for variables too. eg constexpr int p5 = pow<5>(2); and int x = 1; int p5 = pow<5>(x); – Pinite

thanks! for computing variables I'll choose constexpr funcs with loop, I'll run runtime and compile-time. – Tooth