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.
f<35,48>()
is ill-formed and that the compiler is welcome to actually compile said code with arbitrary results?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;
}
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)>
.