Metafunction to compute x^n and return the integer limit without overflow if not possible?

Question

Consider the following code:

template <std::intmax_t Base, std::intmax_t Exponent> 
struct integer_power_bounded
{
    static_assert(Exponent >= 0, 
                  "Error in 'integer_power_bounded': 'Exponent >= 0' is false");
    static constexpr std::intmax_t value = /* something */;
};

template <std::intmax_t Base> 
struct integer_power_bounded<Base, 0>
{
    static constexpr std::intmax_t value = 1;
};

Instead of /* something */, I would like to return std::numeric_limits<std::intmax_t>::min() or std::numeric_limits<std::intmax_t>::max() if Base^Exponent cannot be represented by a std::intmax_t. The difficult thing is to avoid overflows during computation because they create errors at compilation.

How to do that (without boost) ?

dyp · Accepted Answer · 2013-11-09T15:33:18.620

A version based on SFINAE:

#include <cstdint>
#include <cmath>
#include <limits>
#include <type_traits>

constexpr std::intmax_t integer_power(std::intmax_t base,
                                      std::intmax_t exponent)
{
    return (exponent == 0) ? 1 :
           (exponent % 2 == 0) ?  integer_power(base, exponent/2)
                                 *integer_power(base, exponent/2) :
           base*integer_power(base, exponent-1);
}

namespace detail
{
    template<std::intmax_t base, std::intmax_t exponent,
             std::intmax_t res = integer_power(base,exponent)>
    constexpr std::intmax_t pow_helper(int)
    {
        return res;
    }

    template<std::intmax_t base, std::intmax_t exponent>
    constexpr std::intmax_t pow_helper(...)
    {
        return (exponent%2 == 0 || base > 0)
               ? std::numeric_limits<std::intmax_t>::max()
               : std::numeric_limits<std::intmax_t>::min();
    }
}

template<std::intmax_t base, std::intmax_t exponent>
constexpr std::intmax_t integer_power_bounded()
{
    return detail::pow_helper<base,exponent>(0);
}

Usage example:

#include <iostream>
int main()
{
    std::cout << sizeof(std::intmax_t) << '\n';

    constexpr auto p2t6 = integer_power_bounded<2, 6>();
    constexpr auto p2t62 = integer_power_bounded<2, 62>();
    constexpr auto p2t63 = integer_power_bounded<2, 63>();
    constexpr auto p2t64 = integer_power_bounded<2, 64>();
    constexpr auto p2t65 = integer_power_bounded<2, 65>();

    std::cout << "2^6 == " << p2t6 << '\n';
    std::cout << "2^62 == " << p2t62 << '\n';
    std::cout << "2^63 == " << p2t63 << '\n';
    std::cout << "2^64 == " << p2t64 << '\n';
    std::cout << "2^65 == " << p2t65 << '\n';

    constexpr auto pm2t6 = integer_power_bounded<-2, 6>();
    constexpr auto pm2t62 = integer_power_bounded<-2, 62>();
    constexpr auto pm2t63 = integer_power_bounded<-2, 63>();
    constexpr auto pm2t64 = integer_power_bounded<-2, 64>();
    constexpr auto pm2t65 = integer_power_bounded<-2, 65>();

    std::cout << "-2^6 == " << pm2t6 << '\n';
    std::cout << "-2^62 == " << pm2t62 << '\n';
    std::cout << "-2^63 == " << pm2t63 << '\n';
    std::cout << "-2^64 == " << pm2t64 << '\n';
    std::cout << "-2^65 == " << pm2t65 << '\n';
}

Output:

8
2^6 == 64
2^62 == 4611686018427387904
2^63 == 9223372036854775807
2^64 == 9223372036854775807
2^65 == 9223372036854775807
-2^6 == 64
-2^62 == 4611686018427387904
-2^63 == -9223372036854775808
-2^64 == 9223372036854775807
-2^65 == -9223372036854775808

Explanation:

A constant expression may not contain Undefined Behaviour [expr.const]/2:

an operation that would have undefined behavior [Note: including, for example, signed integer overflow, certain pointer arithmetic, division by zero, or certain shift operations — end note];

Therefore, whenever the unbounded integer_power produces an overflow, the expression used to declare the std::integral_constant is no valid constant expression; substitution fails and the fall-back function is used.

Very clever to use SFINAE in that way. I never thought about that but I love this approach ! — Vincent, Nov 09 '13 at 14:25
+1 this is really cleaver, it inspired part of my answer [here](http://stackoverflow.com/questions/21319413/why-do-constant-expressions-have-an-exclusion-for-undefined-behavior). — Shafik Yaghmour, Jan 23 '14 at 21:24
@dyp what do bounded and unbounded here mean? **"integer_power_bounded"** means that it will not overflow? thanks and +1 — Koushik Shetty, Jan 24 '14 at 05:55
@Koushik Yes. The result of `integer_power_bounded` is `base` to the power of `power`, clamped to the range representable by an `std::intmax_t`. I.e., if the power computation would yield a value greater than the greatest representable value, the result of `integer_power_bounded` is the greatest representable value. Similarly for the smallest representable value. — dyp, Jan 24 '14 at 18:35

Metafunction to compute x^n and return the integer limit without overflow if not possible?

1 Answers1

Linked