libcxx/include/__numeric/gcd_lcm.h

   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 <__algorithm/min.h>
  14 #include <__assert>
  15 #include <__bit/countr.h>
  16 #include <__config>
  17 #include <__type_traits/common_type.h>
  18 #include <__type_traits/is_integral.h>
  19 #include <__type_traits/is_same.h>
  20 #include <__type_traits/is_signed.h>
  21 #include <__type_traits/make_unsigned.h>
  22 #include <limits>
  23
  24 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  25 #  pragma GCC system_header
  26 #endif
  27
  28 _LIBCPP_PUSH_MACROS
  29 #include <__undef_macros>
  30
  31 _LIBCPP_BEGIN_NAMESPACE_STD
  32
  33 #if _LIBCPP_STD_VER >= 17
  34
  35 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value>
  36 struct __ct_abs;
  37
  38 template <typename _Result, typename _Source>
  39 struct __ct_abs<_Result, _Source, true> {
  40   constexpr _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept {
  41     if (__t >= 0)
  42       return __t;
  43     if (__t == numeric_limits<_Source>::min())
  44       return -static_cast<_Result>(__t);
  45     return -__t;
  46   }
  47 };
  48
  49 template <typename _Result, typename _Source>
  50 struct __ct_abs<_Result, _Source, false> {
  51   constexpr _LIBCPP_HIDE_FROM_ABI _Result operator()(_Source __t) const noexcept { return __t; }
  52 };
  53
  54 template <class _Tp>
  55 constexpr _LIBCPP_HIDDEN _Tp __gcd(_Tp __a, _Tp __b) {
  56   static_assert(!is_signed<_Tp>::value, "");
  57
  58   // From: https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor
  59   //
  60   // If power of two divides both numbers, we can push it out.
  61   // - gcd( 2^x * a, 2^x * b) = 2^x * gcd(a, b)
  62   //
  63   // If and only if exactly one number is even, we can divide that number by that power.
  64   // - if a, b are odd, then gcd(2^x * a, b) = gcd(a, b)
  65   //
  66   // And standard gcd algorithm where instead of modulo, minus is used.
  67
  68   if (__a < __b) {
  69     _Tp __tmp = __b;
  70     __b       = __a;
  71     __a       = __tmp;
  72   }
  73   if (__b == 0)
  74     return __a;
  75   __a %= __b; // Make both argument of the same size, and early result in the easy case.
  76   if (__a == 0)
  77     return __b;
  78
  79   int __az    = std::__countr_zero(__a);
  80   int __bz    = std::__countr_zero(__b);
  81   int __shift = std::min(__az, __bz);
  82   __a >>= __az;
  83   __b >>= __bz;
  84   do {
  85     _Tp __diff = __a - __b;
  86     if (__a > __b) {
  87       __a = __b;
  88       __b = __diff;
  89     } else {
  90       __b = __b - __a;
  91     }
  92     if (__diff != 0)
  93       __b >>= std::__countr_zero(__diff);
  94   } while (__b != 0);
  95   return __a << __shift;
  96 }
  97
  98 template <class _Tp, class _Up>
  99 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> gcd(_Tp __m, _Up __n) {
 100   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to gcd must be integer types");
 101   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to gcd cannot be bool");
 102   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to gcd cannot be bool");
 103   using _Rp = common_type_t<_Tp, _Up>;
 104   using _Wp = make_unsigned_t<_Rp>;
 105   return static_cast<_Rp>(
 106       std::__gcd(static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n))));
 107 }
 108
 109 template <class _Tp, class _Up>
 110 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> lcm(_Tp __m, _Up __n) {
 111   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to lcm must be integer types");
 112   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to lcm cannot be bool");
 113   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to lcm cannot be bool");
 114   if (__m == 0 || __n == 0)
 115     return 0;
 116
 117   using _Rp  = common_type_t<_Tp, _Up>;
 118   _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / std::gcd(__m, __n);
 119   _Rp __val2 = __ct_abs<_Rp, _Up>()(__n);
 120   _Rp __res;
 121   [[maybe_unused]] bool __overflow = __builtin_mul_overflow(__val1, __val2, &__res);
 122   _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(!__overflow, "Overflow in lcm");
 123   return __res;
 124 }
 125
 126 #endif // _LIBCPP_STD_VER >= 17
 127
 128 _LIBCPP_END_NAMESPACE_STD
 129
 130 _LIBCPP_POP_MACROS
 131
 132 #endif // _LIBCPP___NUMERIC_GCD_LCM_H