1 // -*- C++ -*- 2 //===--------------------------- numeric ----------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_EXPERIMENTAL_NUMERIC 12 #define _LIBCPP_EXPERIMENTAL_NUMERIC 13 /* 14 experimental/numeric synopsis 15 16 // C++1z 17 namespace std { 18 namespace experimental { 19 inline namespace fundamentals_v2 { 20 21 // 13.1.2, Greatest common divisor 22 template<class M, class N> 23 constexpr common_type_t<M,N> gcd(M m, N n); 24 25 // 13.1.3, Least common multiple 26 template<class M, class N> 27 constexpr common_type_t<M,N> lcm(M m, N n); 28 29 } // namespace fundamentals_v2 30 } // namespace experimental 31 } // namespace std 32 33 */ 34 35 #include <experimental/__config> 36 #include <numeric> 37 #include <type_traits> // is_integral 38 #include <limits> // numeric_limits 39 40 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 41 #pragma GCC system_header 42 #endif 43 44 #if _LIBCPP_STD_VER > 11 45 46 _LIBCPP_BEGIN_NAMESPACE_LFTS_V2 47 48 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs; 49 50 template <typename _Result, typename _Source> 51 struct __abs<_Result, _Source, true> { 52 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 53 _Result operator()(_Source __t) const noexcept 54 { 55 if (__t >= 0) return __t; 56 if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 57 return -__t; 58 } 59 }; 60 61 template <typename _Result, typename _Source> 62 struct __abs<_Result, _Source, false> { 63 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 64 _Result operator()(_Source __t) const noexcept { return __t; } 65 }; 66 67 68 template<class _Tp> 69 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 70 _Tp __gcd(_Tp __m, _Tp __n) 71 { 72 static_assert((!is_signed<_Tp>::value), "" ); 73 return __n == 0 ? __m : __gcd<_Tp>(__n, __m % __n); 74 } 75 76 77 template<class _Tp, class _Up> 78 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 79 common_type_t<_Tp,_Up> 80 gcd(_Tp __m, _Up __n) 81 { 82 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 83 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 84 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 85 using _Rp = common_type_t<_Tp,_Up>; 86 using _Wp = make_unsigned_t<_Rp>; 87 return static_cast<_Rp>(__gcd(static_cast<_Wp>(__abs<_Rp, _Tp>()(__m)), 88 static_cast<_Wp>(__abs<_Rp, _Up>()(__n)))); 89 } 90 91 template<class _Tp, class _Up> 92 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 93 common_type_t<_Tp,_Up> 94 lcm(_Tp __m, _Up __n) 95 { 96 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 97 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 98 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 99 if (__m == 0 || __n == 0) 100 return 0; 101 102 using _Rp = common_type_t<_Tp,_Up>; 103 _Rp __val1 = __abs<_Rp, _Tp>()(__m) / gcd(__m, __n); 104 _Rp __val2 = __abs<_Rp, _Up>()(__n); 105 _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 106 return __val1 * __val2; 107 } 108 109 _LIBCPP_END_NAMESPACE_LFTS_V2 110 111 #endif /* _LIBCPP_STD_VER > 11 */ 112 #endif /* _LIBCPP_EXPERIMENTAL_NUMERIC */ 113
