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 3106c3fb27SDimitry Andric #if _LIBCPP_STD_VER >= 17 324824e7fdSDimitry Andric 33*cb14a3feSDimitry Andric template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> 34*cb14a3feSDimitry Andric struct __ct_abs; 354824e7fdSDimitry Andric 364824e7fdSDimitry Andric template <typename _Result, typename _Source> 374824e7fdSDimitry Andric struct __ct_abs<_Result, _Source, true> { 38*cb14a3feSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept { 39*cb14a3feSDimitry Andric if (__t >= 0) 40*cb14a3feSDimitry Andric return __t; 41*cb14a3feSDimitry Andric if (__t == numeric_limits<_Source>::min()) 42*cb14a3feSDimitry Andric return -static_cast<_Result>(__t); 434824e7fdSDimitry Andric return -__t; 444824e7fdSDimitry Andric } 454824e7fdSDimitry Andric }; 464824e7fdSDimitry Andric 474824e7fdSDimitry Andric template <typename _Result, typename _Source> 484824e7fdSDimitry Andric struct __ct_abs<_Result, _Source, false> { 49*cb14a3feSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept { return __t; } 504824e7fdSDimitry Andric }; 514824e7fdSDimitry Andric 524824e7fdSDimitry Andric template <class _Tp> 53*cb14a3feSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN _Tp __gcd(_Tp __m, _Tp __n) { 544824e7fdSDimitry Andric static_assert((!is_signed<_Tp>::value), ""); 555f757f3fSDimitry Andric return __n == 0 ? __m : std::__gcd<_Tp>(__n, __m % __n); 564824e7fdSDimitry Andric } 574824e7fdSDimitry Andric 584824e7fdSDimitry Andric template <class _Tp, class _Up> 59*cb14a3feSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> gcd(_Tp __m, _Up __n) { 604824e7fdSDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 61bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to gcd cannot be bool"); 62bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to gcd cannot be bool"); 634824e7fdSDimitry Andric using _Rp = common_type_t<_Tp, _Up>; 644824e7fdSDimitry Andric using _Wp = make_unsigned_t<_Rp>; 65*cb14a3feSDimitry Andric return static_cast<_Rp>( 66*cb14a3feSDimitry Andric std::__gcd(static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n)))); 674824e7fdSDimitry Andric } 684824e7fdSDimitry Andric 694824e7fdSDimitry Andric template <class _Tp, class _Up> 70*cb14a3feSDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> lcm(_Tp __m, _Up __n) { 714824e7fdSDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 72bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to lcm cannot be bool"); 73bdd1243dSDimitry Andric static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to lcm cannot be bool"); 744824e7fdSDimitry Andric if (__m == 0 || __n == 0) 754824e7fdSDimitry Andric return 0; 764824e7fdSDimitry Andric 774824e7fdSDimitry Andric using _Rp = common_type_t<_Tp, _Up>; 785f757f3fSDimitry Andric _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / std::gcd(__m, __n); 794824e7fdSDimitry Andric _Rp __val2 = __ct_abs<_Rp, _Up>()(__n); 8006c3fb27SDimitry Andric _LIBCPP_ASSERT_UNCATEGORIZED((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 814824e7fdSDimitry Andric return __val1 * __val2; 824824e7fdSDimitry Andric } 834824e7fdSDimitry Andric 844824e7fdSDimitry Andric #endif // _LIBCPP_STD_VER 854824e7fdSDimitry Andric 864824e7fdSDimitry Andric _LIBCPP_END_NAMESPACE_STD 874824e7fdSDimitry Andric 884824e7fdSDimitry Andric _LIBCPP_POP_MACROS 894824e7fdSDimitry Andric 904824e7fdSDimitry Andric #endif // _LIBCPP___NUMERIC_GCD_LCM_H 91