c++template-meta-programminginteger-arithmeticrational-number

Compile time check that lcm(a,b) doesn't overflow


I would like to have a compile-time check that taking the least common multiple of two numbers doesn't overflow. Difficulty: regarding std::lcm,

The behavior is undefined if |m|, |n|, or the least common multiple of |m| and |n| is not representable as a value of type std::common_type_t<M, N>.

(Source: https://en.cppreference.com/w/cpp/numeric/lcm)

Here is what I have come up with:

#include <type_traits>
#include <cstdint>
#include <numeric>

template<int8_t a, int8_t b,
  std::enable_if_t<
    (std::lcm(a,b) > 0 && (std::lcm(a,b) % a == 0) && (std::lcm(a,b) % b == 0)),
    std::nullptr_t> = nullptr>
void f() { }

The rationale here is that that the condition checks that std::lcm(a,b) has produced a positive number of type std::common_type_t<typeof(a), typeof(b)> which is a multiple of both a and b. Given that some common multiple of a and b fits in std::common_type_t<typeof(a), typeof(b)>, it follows that the least common multiple fits, and therefore we are guaranteed by the definition of std::lcm that what we have computed is in fact the lcm.

I checked that this appears to work correctly, e.g.

f<3, 5>();      // compiles
f<127, 127>();  // compiles
f<35, 48>();    // doesn't compile

However I have a couple of questions.

  1. The documentation says that if the least common multiple is not representable, the behavior is undefined, and not just implementation-dependent or something. Does this mean that a program containing something like f<35,48>() is ill-formed and that the compiler is welcome to actually compile said code with arbitrary results?
  2. Is there a simpler way of doing what I'm trying to do?

I suppose I could write my own constexpr safe_lcm function that would guarantee defined behavior and return 0 in the case of an overflow, but that seems like a pretty inelegant solution and also I'd have to work pretty hard to make sure I covered every conceivable combination of arithmetic types I might feed to it.

Update: It sounds like undefined behavior isn't allowed in constant expressions. Since I clearly need this to be a constant expression in order to use it at compile time, does that mean I'm safe here?

Update 2: This appears to be a definite strike against the no-undefined-behavior-in-constexpr theory:

template<int n> struct S {};

template<int8_t a, int8_t b>
S<std::lcm(a, b)> g()
{
  return S<std::lcm(a,b)>();
}

int main(int, char **)
{
  g<35, 48>(); // compiles :'(
  return 0;
}

Solution

  • Assuming that both a and b are positive, there is the relationship

    a * b == lcm(a,b) * gcd(a,b)
    

    that you can use to your advantage. Computing gcd(a,b) does not overflow. Then you can check whether

    a / gcd(a,b) <= std::numeric_limits<CT>::max() / b
    

    where CT is std::common_type_t<decltype(a),decltype(b)>.