__cxx03/__numeric/gcd_lcm.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03___NUMERIC_GCD_LCM_H
0011 #define _LIBCPP___CXX03___NUMERIC_GCD_LCM_H
0012
0013 #include <__cxx03/__algorithm/min.h>
0014 #include <__cxx03/__assert>
0015 #include <__cxx03/__bit/countr.h>
0016 #include <__cxx03/__config>
0017 #include <__cxx03/__type_traits/common_type.h>
0018 #include <__cxx03/__type_traits/is_integral.h>
0019 #include <__cxx03/__type_traits/is_same.h>
0020 #include <__cxx03/__type_traits/is_signed.h>
0021 #include <__cxx03/__type_traits/make_unsigned.h>
0022 #include <__cxx03/limits>
0023
0024 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0025 #  pragma GCC system_header
0026 #endif
0027
0028 _LIBCPP_PUSH_MACROS
0029 #include <__cxx03/__undef_macros>
0030
0031 _LIBCPP_BEGIN_NAMESPACE_STD
0032
0033 #if _LIBCPP_STD_VER >= 17
0034
0035 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value>
0036 struct __ct_abs;
0037
0038 template <typename _Result, typename _Source>
0039 struct __ct_abs<_Result, _Source, true> {
0040   constexpr _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept {
0041     if (__t >= 0)
0042       return __t;
0043     if (__t == numeric_limits<_Source>::min())
0044       return -static_cast<_Result>(__t);
0045     return -__t;
0046   }
0047 };
0048
0049 template <typename _Result, typename _Source>
0050 struct __ct_abs<_Result, _Source, false> {
0051   constexpr _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept { return __t; }
0052 };
0053
0054 template <class _Tp>
0055 constexpr _LIBCPP_HIDDEN _Tp __gcd(_Tp __a, _Tp __b) {
0056   static_assert(!is_signed<_Tp>::value, "");
0057
0058   // From: https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor
0059   //
0060   // If power of two divides both numbers, we can push it out.
0061   // - gcd( 2^x * a, 2^x * b) = 2^x * gcd(a, b)
0062   //
0063   // If and only if exactly one number is even, we can divide that number by that power.
0064   // - if a, b are odd, then gcd(2^x * a, b) = gcd(a, b)
0065   //
0066   // And standard gcd algorithm where instead of modulo, minus is used.
0067
0068   if (__a < __b) {
0069     _Tp __tmp = __b;
0070     __b       = __a;
0071     __a       = __tmp;
0072   }
0073   if (__b == 0)
0074     return __a;
0075   __a %= __b; // Make both argument of the same size, and early result in the easy case.
0076   if (__a == 0)
0077     return __b;
0078
0079   int __az    = std::__countr_zero(__a);
0080   int __bz    = std::__countr_zero(__b);
0081   int __shift = std::min(__az, __bz);
0082   __a >>= __az;
0083   __b >>= __bz;
0084   do {
0085     _Tp __diff = __a - __b;
0086     if (__a > __b) {
0087       __a = __b;
0088       __b = __diff;
0089     } else {
0090       __b = __b - __a;
0091     }
0092     if (__diff != 0)
0093       __b >>= std::__countr_zero(__diff);
0094   } while (__b != 0);
0095   return __a << __shift;
0096 }
0097
0098 template <class _Tp, class _Up>
0099 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> gcd(_Tp __m, _Up __n) {
0100   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to gcd must be integer types");
0101   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to gcd cannot be bool");
0102   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to gcd cannot be bool");
0103   using _Rp = common_type_t<_Tp, _Up>;
0104   using _Wp = make_unsigned_t<_Rp>;
0105   return static_cast<_Rp>(
0106       std::__gcd(static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n))));
0107 }
0108
0109 template <class _Tp, class _Up>
0110 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> lcm(_Tp __m, _Up __n) {
0111   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to lcm must be integer types");
0112   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to lcm cannot be bool");
0113   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to lcm cannot be bool");
0114   if (__m == 0 || __n == 0)
0115     return 0;
0116
0117   using _Rp  = common_type_t<_Tp, _Up>;
0118   _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / std::gcd(__m, __n);
0119   _Rp __val2 = __ct_abs<_Rp, _Up>()(__n);
0120   _Rp __res;
0121   [[maybe_unused]] bool __overflow = __builtin_mul_overflow(__val1, __val2, &__res);
0122   _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(!__overflow, "Overflow in lcm");
0123   return __res;
0124 }
0125
0126 #endif // _LIBCPP_STD_VER >= 17
0127
0128 _LIBCPP_END_NAMESPACE_STD
0129
0130 _LIBCPP_POP_MACROS
0131
0132 #endif // _LIBCPP___CXX03___NUMERIC_GCD_LCM_H