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 17namespace std { 18namespace experimental { 19inline 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 48template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs; 49 50template <typename _Result, typename _Source> 51struct __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 61template <typename _Result, typename _Source> 62struct __abs<_Result, _Source, false> { 63 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 64 _Result operator()(_Source __t) const noexcept { return __t; } 65}; 66 67 68template<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 77template<class _Tp, class _Up> 78_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 79common_type_t<_Tp,_Up> 80gcd(_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 91template<class _Tp, class _Up> 92_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 93common_type_t<_Tp,_Up> 94lcm(_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