gul17/gcd_lcm.h

Detailed Description

Greatest common divisor and least common multiple.

Functions
template<typename IntTypeA , typename IntTypeB >
constexpr auto	gul17::gcd (IntTypeA a, IntTypeB b)
	Calculate the greatest common divisor of two integers using the Euclidean algorithm.
template<typename IntTypeA , typename IntTypeB >
constexpr auto	gul17::lcm (IntTypeA a, IntTypeB b)
	Calculate the least common multiple of two integers.

Function Documentation

gcd()

template<typename IntTypeA , typename IntTypeB >

constexpr auto gul17::gcd ( IntTypeA  a, IntTypeB  b  )

inlineconstexpr

Calculate the greatest common divisor of two integers using the Euclidean algorithm.

If both numbers are zero, the function returns zero. Otherwise, the result is a positive integer.

int greatest_common_divisor = gcd(10, 15); // returns 5

Returns

the least common multiple of the two numbers, represented as an integer type (std::common_type_t<IntTypeA, IntTypeB>) that both inputs can implicitly be converted to. If either a, b, or the result can not be represented by that type, the result is undefined.

Note

Unlike std::gcd() from C++17, the GUL17 version cannot be used with integers of different signedness. This avoids undefined behavior when mixing unsigned integers with negative signed values:

// C++17 gcd(): Undefined behavior - the common type is `unsigned int` and -5 has no
// representation in that type
auto bad_result = std::gcd(10u, -5);
 
// GUL17 gcd(): Does not compile
auto static_assertion_failure = gul17::gcd(10u, -5);

Since

GUL version 2.7

References gul17::abs(), and gul17::bit_set().

Referenced by gul17::lcm().

lcm()

template<typename IntTypeA , typename IntTypeB >

constexpr auto gul17::lcm ( IntTypeA  a, IntTypeB  b  )

inlineconstexpr

Calculate the least common multiple of two integers.

If both numbers are zero, the function returns zero. Otherwise, the result is a positive integer.

int least_common_multiple = lcm(10, 15); // returns 30

Returns

the least common multiple of the two numbers, represented as an integer type (std::common_type_t<IntTypeA, IntTypeB>) that both inputs can implicitly be converted to. If either a, b, or the result can not be represented by that type, the result is undefined.

Note

Unlike std::lcm() from C++17, the GUL17 version cannot be used with integers of different signedness. This avoids undefined behavior when mixing unsigned integers with negative signed values:

// C++17 lcm(): Undefined behavior - the common type is `unsigned int` and -5 has no
// representation in that type
auto bad_result = std::lcm(10u, -5);
 
// GUL17 lcm(): Does not compile
auto static_assertion_failure = gul17::lcm(10u, -5);

Since

GUL version 2.7

References gul17::abs(), gul17::bit_set(), and gul17::gcd().