1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___NUMERIC_GCD_LCM_H 11 #define _LIBCPP___NUMERIC_GCD_LCM_H 12 13 #include <__config> 14 #include <__debug> 15 #include <limits> 16 #include <type_traits> 17 18 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 19 # pragma GCC system_header 20 #endif 21 22 _LIBCPP_PUSH_MACROS 23 #include <__undef_macros> 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 #if _LIBCPP_STD_VER > 14 28 29 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs; 30 31 template <typename _Result, typename _Source> 32 struct __ct_abs<_Result, _Source, true> { 33 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 34 _Result operator()(_Source __t) const noexcept 35 { 36 if (__t >= 0) return __t; 37 if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 38 return -__t; 39 } 40 }; 41 42 template <typename _Result, typename _Source> 43 struct __ct_abs<_Result, _Source, false> { 44 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 45 _Result operator()(_Source __t) const noexcept { return __t; } 46 }; 47 48 49 template<class _Tp> 50 _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN 51 _Tp __gcd(_Tp __m, _Tp __n) 52 { 53 static_assert((!is_signed<_Tp>::value), ""); 54 return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n); 55 } 56 57 template<class _Tp, class _Up> 58 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 59 common_type_t<_Tp,_Up> 60 gcd(_Tp __m, _Up __n) 61 { 62 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 63 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 64 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 65 using _Rp = common_type_t<_Tp,_Up>; 66 using _Wp = make_unsigned_t<_Rp>; 67 return static_cast<_Rp>(_VSTD::__gcd( 68 static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), 69 static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n)))); 70 } 71 72 template<class _Tp, class _Up> 73 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 74 common_type_t<_Tp,_Up> 75 lcm(_Tp __m, _Up __n) 76 { 77 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 78 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 79 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 80 if (__m == 0 || __n == 0) 81 return 0; 82 83 using _Rp = common_type_t<_Tp,_Up>; 84 _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n); 85 _Rp __val2 = __ct_abs<_Rp, _Up>()(__n); 86 _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 87 return __val1 * __val2; 88 } 89 90 #endif // _LIBCPP_STD_VER 91 92 _LIBCPP_END_NAMESPACE_STD 93 94 _LIBCPP_POP_MACROS 95 96 #endif // _LIBCPP___NUMERIC_GCD_LCM_H 97