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.

score 25 · Accepted Answer · edited May 23 '17 at 12:10

25

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.

edited May 23 '17 at 12:10

Community

1
1

answered May 08 '13 at 14:53

dyp

38,334
13
112
177

3

@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. – dyp May 08 '13 at 14:56
4

@BЈовић: Seriously, who cares? “Are you sure you used the blue hammer for this nail?” – Christopher Creutzig May 08 '13 at 14:56
@ChristopherCreutzig Ok, the title confused me. – BЈовић May 08 '13 at 14:59
@BЈовић sorry for the confusion title. Maybe it should be changed to compile time power of int. – Sungmin May 08 '13 at 15:03
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. – PaperBirdMaster May 08 '13 at 15:56
@PaperBirdMaster 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. – dyp May 08 '13 at 16:23
@DyP yes, I was referring to that, but I betted that the reason was more impressive :P – PaperBirdMaster May 08 '13 at 17:14
3

It would be even better if it used [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring). – Jeremy W. Murphy Oct 29 '13 at 12:51
Thanks for the great answer. As a small `c++20` update you could mention that replacing `constexpr` with `consteval` to enforce compile-time evaluation. – wychmaster Oct 29 '21 at 10:47
@wychmaster 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? – dyp Nov 02 '21 at 08:38
@dyp 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](https://en.cppreference.com/w/cpp/language/consteval) 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... – wychmaster Nov 02 '21 at 10:48
1

@wychmaster See https://stackoverflow.com/a/58467438/420683 and https://stackoverflow.com/a/64742167/420683 – dyp Nov 02 '21 at 11:06

score 20 · Answer 2 · edited Jan 08 '23 at 12:20

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.

@taocp: Thanks a lot for your appreciation, but you are celebrating me more than I deserve ;) I wish I knew every bit of C++ — Andy Prowl, May 08 '13 at 15:00
@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 — Andy Prowl, May 08 '13 at 15:03
Thank you. It helps me a lot. I was having hard time to pick the accepted answer. Because both were great. — Sungmin, May 08 '13 at 15:05
@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 — Andy Prowl, May 08 '13 at 15:06
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. — Potatoswatter, May 08 '13 at 15:16
@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 — Andy Prowl, May 08 '13 at 15:22
@Sungmin: Thank you, although what Potatoswatter wrote is correct - and I tried to reflect that in the last update to my answer — Andy Prowl, May 08 '13 at 15:53
@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 — Andy Prowl, May 26 '13 at 17:22

score 5 · Answer 3 · answered May 17 '14 at 23:58

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

score 1 · Answer 4 · answered May 08 '17 at 10:46

1

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

answered May 08 '17 at 10:46

Varun Rao

393
1
5
19

Cool solution, this is what I was looking for – ilciavo Apr 01 '22 at 16:14
`M` should be unsigned. – Steve Ward Aug 31 '23 at 23:58

score 1 · Answer 5 · answered Jan 08 '23 at 11:14

1

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
}

answered Jan 08 '23 at 11:14

M. Galib Uludag

369
2
8

`pow_constexpr` 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);` – QuentinUK Jan 08 '23 at 11:41
thanks! for computing variables I'll choose constexpr funcs with loop, I'll run runtime and compile-time. – M. Galib Uludag Jan 08 '23 at 23:42

c++ power of integer, template meta programming

5 Answers5

Linked