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   // Using Binary GCD algorithm https://en.wikipedia.org/wiki/Binary_GCD_algorithm, based on an implementation
  59   // from https://lemire.me/blog/2024/04/13/greatest-common-divisor-the-extended-euclidean-algorithm-and-speed/
  60   //
  61   // If power of two divides both numbers, we can push it out.
  62   // - gcd( 2^x * a, 2^x * b) = 2^x * gcd(a, b)
  63   //
  64   // If and only if exactly one number is even, we can divide that number by that power.
  65   // - if a, b are odd, then gcd(2^x * a, b) = gcd(a, b)
  66   //
  67   // And standard gcd algorithm where instead of modulo, minus is used.
  68
  69   if (__a < __b) {
  70     _Tp __tmp = __b;
  71     __b       = __a;
  72     __a       = __tmp;
  73   }
  74   if (__b == 0)
  75     return __a;
  76   __a %= __b; // Make both argument of the same size, and early result in the easy case.
  77   if (__a == 0)
  78     return __b;
  79
  80   _Tp __c     = __a | __b;
  81   int __shift = std::__countr_zero(__c);
  82   __a >>= std::__countr_zero(__a);
  83   do {
  84     _Tp __t = __b >> std::__countr_zero(__b);
  85     if (__a > __t) {
  86       __b = __a - __t;
  87       __a = __t;
  88     } else {
  89       __b = __t - __a;
  90     }
  91   } while (__b != 0);
  92   return __a << __shift;
  93 }
  94
  95 template <class _Tp, class _Up>
  96 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> gcd(_Tp __m, _Up __n) {
  97   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to gcd must be integer types");
  98   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to gcd cannot be bool");
  99   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to gcd cannot be bool");
 100   using _Rp = common_type_t<_Tp, _Up>;
 101   using _Wp = make_unsigned_t<_Rp>;
 102   return static_cast<_Rp>(
 103       std::__gcd(static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n))));
 104 }
 105
 106 template <class _Tp, class _Up>
 107 constexpr _LIBCPP_HIDE_FROM_ABI common_type_t<_Tp, _Up> lcm(_Tp __m, _Up __n) {
 108   static_assert(is_integral<_Tp>::value && is_integral<_Up>::value, "Arguments to lcm must be integer types");
 109   static_assert(!is_same<__remove_cv_t<_Tp>, bool>::value, "First argument to lcm cannot be bool");
 110   static_assert(!is_same<__remove_cv_t<_Up>, bool>::value, "Second argument to lcm cannot be bool");
 111   if (__m == 0 || __n == 0)
 112     return 0;
 113
 114   using _Rp  = common_type_t<_Tp, _Up>;
 115   _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / std::gcd(__m, __n);
 116   _Rp __val2 = __ct_abs<_Rp, _Up>()(__n);
 117   _Rp __res;
 118   [[maybe_unused]] bool __overflow = __builtin_mul_overflow(__val1, __val2, &__res);
 119   _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(!__overflow, "Overflow in lcm");
 120   return __res;
 121 }
 122
 123 #endif // _LIBCPP_STD_VER >= 17
 124
 125 _LIBCPP_END_NAMESPACE_STD
 126
 127 _LIBCPP_POP_MACROS
 128
 129 #endif // _LIBCPP___NUMERIC_GCD_LCM_H