1

In C++, is there a compile-time way to compute the largest value of an integral type T that can be safely squared, i.e. that mathematically x * x <= std::numeric_limits<T>::max() so that if the operation x*x were to be performed, it would not cause undefined behavior (for signed types) or overflow (for unsigned types?

I'm fine restricting to only integral types that have specializations in std::numeric_limits, i.e. no need to worry about new user-defined integral types, if that makes it any easier.

Mathematically, of course, the answer is floor(sqrt(std::numeric_limits<T>::max())). For example, this would be floor(sqrt(2^63-1)) == 3037000499 for a 64-bit signed long long. A (correct even for large numbers) constexpr sqrt would do the trick, though I don't know if that is the best way.

Answers should be:

  • 64-bit unsigned: floor(sqrt(2^64-1)) == 4294967295
  • 64-bit signed: floor(sqrt(2^63-1)) == 3037000499
  • 32-bit unsigned: floor(sqrt(2^32-1)) == 65535
  • 32-bit signed: floor(sqrt(2^31-1)) == 46340
nullUser
  • 1,601
  • 1
  • 12
  • 29
  • 3
    Get a constexpr `sqrt`? https://stackoverflow.com/a/27709195/4342498 – NathanOliver Jan 29 '21 at 16:56
  • Related: [p0533](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0533r6.pdf) will hopefully get standardized soon. Edit: Scratch that, `sqrt` is not a candidate for `constexpr` in that proposal – AndyG Jan 29 '21 at 17:00
  • @NathanOliver This does not mean it is not done at compile time depending on the compiler, right? Or am I missing something here https://godbolt.org/z/avEf7z ? –  Jan 29 '21 at 17:12
  • 2
    Don't use `std::sqrt`, it is not `constexpr`. If you follow my link, it gives you a constexpr version of `sqrt` that works with integers. – NathanOliver Jan 29 '21 at 17:14
  • @NathanOliver It seems those answers are a bit dodgy. Plus none of them seem to work for signed types. – nullUser Jan 29 '21 at 17:22
  • For a 64 bit integer, which is capable of (2^64 - 1), is 2^32 -1. The square root of 2^64 is 2^32. Similarly, for 32 bit integer, the largest value that can be squared is 2^16 - 1. Be aware that signed integers do not have the same positive range that unsigned integers do. – Thomas Matthews Jan 29 '21 at 17:33
  • @ThomasMatthews Thanks, I've updated my question to include the correct answers for signed and unsigned 32, 64 bit. – nullUser Jan 29 '21 at 17:43
  • 1
    Do you need to actually calculate the value at compile time? You already showed the four values that you want, so maybe you could just write four type traits. – Bob__ Jan 29 '21 at 17:53
  • @Bob__ If I precomputed the values for 8, 16, 32 ,64 bit signed unsigned, could I somehow template it based off `std::numeric_limits::digits` and `std::numeric_limits::is_signed`? I'm not very familiar with template programming or how to do this. – nullUser Jan 29 '21 at 18:00
  • @nullUser why you need those if you already have answer for specific type `T` ? – apple apple Jan 29 '21 at 18:11
  • You can specialize for the various fixed width integer types like `int32_t`, `uint32_t`, `int64_t` and so on (note that you need to use those instead of the generic `int` or `long`, which have implentation defined sizes). – Bob__ Jan 29 '21 at 18:14
  • @appleapple Because `T` won't be known until compile time. – nullUser Jan 29 '21 at 19:06
  • @nullUser ? I mean the same as @ Bob__ – apple apple Jan 30 '21 at 14:59

1 Answers1

3
  • Set the lower half of the bits.
  • For signed types, add 1 and then divide with sqrt(2)
#include <climits>
#include <limits>
#include <type_traits>

template<class T>
constexpr T largest_squareable() {
    static_assert(std::is_integral_v<T>, "Must be an integral type");

    if constexpr (std::is_unsigned_v<T>) {
        return std::numeric_limits<T>::max() >> sizeof(T) * CHAR_BIT / 2;
    } else {        
        constexpr long double sqrt_2 = 1.41421356237309504880L;
        return (largest_squareable<std::make_unsigned_t<T>>() + 1) / sqrt_2;    
    }
}

Demo

Or just define the values by hand since there are a very limited number of sizes:

#include <cstdint>

template<typename T>
constexpr T largest_squareable();

template<> constexpr int8_t largest_squareable<int8_t>() { return 11; }
template<> constexpr uint8_t largest_squareable<uint8_t>() { return 15; }
template<> constexpr int16_t largest_squareable<int16_t>() { return 181; }
template<> constexpr uint16_t largest_squareable<uint16_t>() { return 255; }
template<> constexpr int32_t largest_squareable<int32_t>() { return 46340L; }
template<> constexpr uint32_t largest_squareable<uint32_t>() { return 65535UL; }
template<> constexpr int64_t largest_squareable<int64_t>() { return 3037000499LL; }
template<> constexpr uint64_t largest_squareable<uint64_t>() { return 4294967295ULL; }
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • Assuming that you replaced uintmax_t with a templated unsigned type T, this still only handles unsigned types, no? For signed types it would invoke undefined behavior. – nullUser Jan 29 '21 at 17:20
  • See: https://godbolt.org/z/WrqcMG your answer fails for long long (and other signed types) – nullUser Jan 29 '21 at 17:27
  • 1
    this has nothing to do with follow up questions, your answer does not answer my original question. I asked for a way to find the answer for an arbitrary signed or unsigned integral type T. You gave me a function that works for ONE type, uintmax_t. If I asked how to get the biggest number for a given type, would honestly say "return 18446744073709551615" instead of using, say, `std::numeric_limits::max()`? – nullUser Jan 30 '21 at 23:16
  • 1
    @nullUser Yeah, you're right. I read it sloppy I guess. Sorry about that. Better now? – Ted Lyngmo Jan 30 '21 at 23:42
  • Above and beyond, this is exactly what I was looking for. Thank you so much. I think I actually prefer the the "dumb" method of just hard coding the answers, other people reading the code would probably understand it much easier. – nullUser Feb 01 '21 at 17:47
  • @nullUser You're welcome! It's a matter of taste I guess. I was starting to think about how this could be done for arbitrary exponents and found an interesting library called [Sprout](https://github.com/bolero-MURAKAMI/Sprout/tree/master/sprout/math) that has `constexpr` versions of the needed function (`pow`). Using that would give the user "indefinite" options :) – Ted Lyngmo Feb 01 '21 at 18:06