14824e7fdSDimitry Andric // -*- C++ -*- 24824e7fdSDimitry Andric //===----------------------------------------------------------------------===// 34824e7fdSDimitry Andric // 44824e7fdSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 54824e7fdSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 64824e7fdSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 74824e7fdSDimitry Andric // 84824e7fdSDimitry Andric //===----------------------------------------------------------------------===// 94824e7fdSDimitry Andric 104824e7fdSDimitry Andric #ifndef _LIBCPP___NUMERIC_GCD_LCM_H 114824e7fdSDimitry Andric #define _LIBCPP___NUMERIC_GCD_LCM_H 124824e7fdSDimitry Andric 1381ad6265SDimitry Andric #include <__assert> 144824e7fdSDimitry Andric #include <__config> 15bdd1243dSDimitry Andric #include <__type_traits/common_type.h> 16bdd1243dSDimitry Andric #include <__type_traits/is_integral.h> 17bdd1243dSDimitry Andric #include <__type_traits/is_same.h> 18bdd1243dSDimitry Andric #include <__type_traits/is_signed.h> 19bdd1243dSDimitry Andric #include <__type_traits/make_unsigned.h> 204824e7fdSDimitry Andric #include <limits> 214824e7fdSDimitry Andric 224824e7fdSDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 234824e7fdSDimitry Andric # pragma GCC system_header 244824e7fdSDimitry Andric #endif 254824e7fdSDimitry Andric 264824e7fdSDimitry Andric _LIBCPP_PUSH_MACROS 274824e7fdSDimitry Andric #include <__undef_macros> 284824e7fdSDimitry Andric 294824e7fdSDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 304824e7fdSDimitry Andric 31*06c3fb27SDimitry Andric #if _LIBCPP_STD_VER >= 17 324824e7fdSDimitry Andric 334824e7fdSDimitry Andric template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs; 344824e7fdSDimitry Andric 354824e7fdSDimitry Andric template <typename _Result, typename _Source> 364824e7fdSDimitry Andric struct __ct_abs<_Result, _Source, true> { 374824e7fdSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 384824e7fdSDimitry Andric _Result operator()(_Source __t) const noexcept 394824e7fdSDimitry Andric { 404824e7fdSDimitry Andric if (__t >= 0) return __t; 414824e7fdSDimitry Andric if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 424824e7fdSDimitry Andric return -__t; 434824e7fdSDimitry Andric } 444824e7fdSDimitry Andric }; 454824e7fdSDimitry Andric 464824e7fdSDimitry Andric template <typename _Result, typename _Source> 474824e7fdSDimitry Andric struct __ct_abs<_Result, _Source, false> { 484824e7fdSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 494824e7fdSDimitry Andric _Result operator()(_Source __t) const noexcept { return __t; } 504824e7fdSDimitry Andric }; 514824e7fdSDimitry Andric 524824e7fdSDimitry Andric 534824e7fdSDimitry Andric template<class _Tp> 544824e7fdSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN 554824e7fdSDimitry Andric _Tp __gcd(_Tp __m, _Tp __n) 564824e7fdSDimitry Andric { 574824e7fdSDimitry Andric static_assert((!is_signed<_Tp>::value), ""); 584824e7fdSDimitry Andric return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n); 594824e7fdSDimitry Andric } 604824e7fdSDimitry Andric 614824e7fdSDimitry Andric template<class _Tp, class _Up> 624824e7fdSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 634824e7fdSDimitry Andric common_type_t<_Tp,_Up> 644824e7fdSDimitry Andric gcd(_Tp __m, _Up __n) 654824e7fdSDimitry Andric { 664824e7fdSDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 67bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to gcd cannot be bool" ); 68bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to gcd cannot be bool" ); 694824e7fdSDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 704824e7fdSDimitry Andric using _Wp = make_unsigned_t<_Rp>; 714824e7fdSDimitry Andric return static_cast<_Rp>(_VSTD::__gcd( 724824e7fdSDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), 734824e7fdSDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n)))); 744824e7fdSDimitry Andric } 754824e7fdSDimitry Andric 764824e7fdSDimitry Andric template<class _Tp, class _Up> 774824e7fdSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 784824e7fdSDimitry Andric common_type_t<_Tp,_Up> 794824e7fdSDimitry Andric lcm(_Tp __m, _Up __n) 804824e7fdSDimitry Andric { 814824e7fdSDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 82bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to lcm cannot be bool" ); 83bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to lcm cannot be bool" ); 844824e7fdSDimitry Andric if (__m == 0 || __n == 0) 854824e7fdSDimitry Andric return 0; 864824e7fdSDimitry Andric 874824e7fdSDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 884824e7fdSDimitry Andric _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n); 894824e7fdSDimitry Andric _Rp __val2 = __ct_abs<_Rp, _Up>()(__n); 90*06c3fb27SDimitry Andric _LIBCPP_ASSERT_UNCATEGORIZED((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 914824e7fdSDimitry Andric return __val1 * __val2; 924824e7fdSDimitry Andric } 934824e7fdSDimitry Andric 944824e7fdSDimitry Andric #endif // _LIBCPP_STD_VER 954824e7fdSDimitry Andric 964824e7fdSDimitry Andric _LIBCPP_END_NAMESPACE_STD 974824e7fdSDimitry Andric 984824e7fdSDimitry Andric _LIBCPP_POP_MACROS 994824e7fdSDimitry Andric 1004824e7fdSDimitry Andric #endif // _LIBCPP___NUMERIC_GCD_LCM_H 101