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