General Utility Library for C++14  2.11
gcd_lcm.h
Go to the documentation of this file.
1 
23 #ifndef GUL14_GCD_LCM_H_
24 #define GUL14_GCD_LCM_H_
25 
26 #include <type_traits>
27 
28 #include "gul14/internal.h"
29 #include "gul14/num_util.h"
30 
31 namespace gul14 {
32 
69 template <typename IntTypeA, typename IntTypeB>
70 constexpr inline auto
71 gcd(IntTypeA a, IntTypeB b)
72 {
73  static_assert(std::is_integral<IntTypeA>::value and std::is_integral<IntTypeB>::value,
74  "gcd() arguments must be integers");
75 
76  static_assert(std::is_signed<IntTypeA>::value == std::is_signed<IntTypeB>::value,
77  "gcd() arguments must have the same signedness");
78 
79  using CommonType = std::common_type_t<IntTypeA, IntTypeB>;
80 
81  auto c = gul14::abs(static_cast<CommonType>(a));
82  auto d = gul14::abs(static_cast<CommonType>(b));
83 
84  while (d != 0)
85  {
86  CommonType tmp = d;
87  d = c % d;
88  c = tmp;
89  }
90 
91  return c;
92 }
93 
123 template <typename IntTypeA, typename IntTypeB>
124 constexpr inline auto
125 lcm(IntTypeA a, IntTypeB b)
126 {
127  static_assert(std::is_integral<IntTypeA>::value and std::is_integral<IntTypeB>::value,
128  "lcm() arguments must be integers");
129 
130  static_assert(std::is_signed<IntTypeA>::value == std::is_signed<IntTypeB>::value,
131  "lcm() arguments must have the same signedness");
132 
133  using CommonType = std::common_type_t<IntTypeA, IntTypeB>;
134 
135  if (a == 0 && b == 0)
136  return CommonType{ 0 };
137 
138  return static_cast<CommonType>(gul14::abs((a / gcd(a, b)) * b));
139 }
140 
142 
143 } // namespace gul14
144 
145 #endif
constexpr auto lcm(IntTypeA a, IntTypeB b)
Calculate the least common multiple of two integers.
Definition: gcd_lcm.h:125
constexpr auto gcd(IntTypeA a, IntTypeB b)
Calculate the greatest common divisor of two integers using the Euclidean algorithm.
Definition: gcd_lcm.h:71
constexpr auto abs(ValueT n) noexcept -> std::enable_if_t< std::is_unsigned< ValueT >::value, ValueT >
Compute the absolute value of a number.
Definition: num_util.h:53
Definition of macros used internally by GUL.
Namespace gul14 contains all functions and classes of the General Utility Library.
Definition: doxygen.h:26
Declaration of numerical utility functions.