xref: /freebsd/contrib/llvm-project/libcxx/include/__numeric/gcd_lcm.h (revision 7ef62cebc2f965b0f640263e179276928885e33d)
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 <__assert>
14 #include <__config>
15 #include <__type_traits/common_type.h>
16 #include <__type_traits/is_integral.h>
17 #include <__type_traits/is_same.h>
18 #include <__type_traits/is_signed.h>
19 #include <__type_traits/make_unsigned.h>
20 #include <limits>
21 
22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23 #  pragma GCC system_header
24 #endif
25 
26 _LIBCPP_PUSH_MACROS
27 #include <__undef_macros>
28 
29 _LIBCPP_BEGIN_NAMESPACE_STD
30 
31 #if _LIBCPP_STD_VER > 14
32 
33 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs;
34 
35 template <typename _Result, typename _Source>
36 struct __ct_abs<_Result, _Source, true> {
37     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
38     _Result operator()(_Source __t) const noexcept
39     {
40         if (__t >= 0) return __t;
41         if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t);
42         return -__t;
43     }
44 };
45 
46 template <typename _Result, typename _Source>
47 struct __ct_abs<_Result, _Source, false> {
48     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
49     _Result operator()(_Source __t) const noexcept { return __t; }
50 };
51 
52 
53 template<class _Tp>
54 _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN
55 _Tp __gcd(_Tp __m, _Tp __n)
56 {
57     static_assert((!is_signed<_Tp>::value), "");
58     return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n);
59 }
60 
61 template<class _Tp, class _Up>
62 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
63 common_type_t<_Tp,_Up>
64 gcd(_Tp __m, _Up __n)
65 {
66     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");
67     static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to gcd cannot be bool" );
68     static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to gcd cannot be bool" );
69     using _Rp = common_type_t<_Tp,_Up>;
70     using _Wp = make_unsigned_t<_Rp>;
71     return static_cast<_Rp>(_VSTD::__gcd(
72         static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)),
73         static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n))));
74 }
75 
76 template<class _Tp, class _Up>
77 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
78 common_type_t<_Tp,_Up>
79 lcm(_Tp __m, _Up __n)
80 {
81     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types");
82     static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to lcm cannot be bool" );
83     static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to lcm cannot be bool" );
84     if (__m == 0 || __n == 0)
85         return 0;
86 
87     using _Rp = common_type_t<_Tp,_Up>;
88     _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n);
89     _Rp __val2 = __ct_abs<_Rp, _Up>()(__n);
90     _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm");
91     return __val1 * __val2;
92 }
93 
94 #endif // _LIBCPP_STD_VER
95 
96 _LIBCPP_END_NAMESPACE_STD
97 
98 _LIBCPP_POP_MACROS
99 
100 #endif // _LIBCPP___NUMERIC_GCD_LCM_H
101