GCD, LCM, and Extended GCD
Greatest Common Divisor and Least Common Multiple.
Caution
Imports <bit>, <concepts>, <limits>, <type_traits>, <stdexcept>, and <utility>. For now, also <tuple> and <vector>.
Tip
To import use #include "atl/numeric/gcd.hpp".
abl::gcd and abl::lcm
Compute GCD and LCM of two or more numbers using binary GCD algorithm. The resulting type is the common type of the function’s argument’s types.
Note
Functions are constexpr and conditionally noexcept (throw on failed type conversion).
Usage
Both abl::gcd and abl::lcm take at least two arguments.
abl::gcd(a, b) // computes gcd(a, b)
abl::gcd(a, b, c) // computes gcd(gcd(a, b), c)
abl::gcd({a, b, c}) // computes gcd(gcd(a, b), c) iteratively
// and so on
Warning
LCM of two negative numbers (as of a negative and positive) is a negative number, to be really “the least”.
abl::lcm(a, b) // computes lcm(a, b)
abl::lcm(a, b, c) // computes lcm(gcd(a, b), c)
abl::lcm({a, b, c}) // computes lcm(gcd(a, b), c) iteratively
// and so on
abl::gcdx
Computes the greatest common divisor and the Bézout coefficients of a list of signed integers.
Note
Functions are constexpr and conditionally noexcept (throw on failed type conversion).
Usage
abl::gcdx takes two or more integer arguments. When called with two arguments, returns Bézout coefficients as std::tuple, otherwise as std::vector.
auto [d1, coeffs1] = abl::gcdx(a, b);
auto [d2, coeffs2] = abl::gcdx(a, b, c);
auto [d3, coeffs3] = abl::gcdx({a, b, c});