ceph/src/boost/boost/integer/common_factor_rt.hpp

   1 //  (C) Copyright Jeremy William Murphy 2016.
   2
   3 //  Use, modification and distribution are subject to the
   4 //  Boost Software License, Version 1.0. (See accompanying file
   5 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_INTEGER_COMMON_FACTOR_RT_HPP
   8 #define BOOST_INTEGER_COMMON_FACTOR_RT_HPP
   9
  10 #include <boost/assert.hpp>
  11 #include <boost/core/enable_if.hpp>
  12
  13 #include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.
  14 #include <boost/limits.hpp>  // for std::numeric_limits
  15 #include <climits>           // for CHAR_MIN
  16 #include <boost/detail/workaround.hpp>
  17 #include <iterator>
  18 #include <algorithm>
  19 #include <limits>
  20 #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS
  21 #include <type_traits>
  22 #endif
  23 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
  24 #include <functional>
  25 #endif
  26
  27 #if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
  28 #include <intrin.h>
  29 #endif
  30
  31 #ifdef BOOST_MSVC
  32 #pragma warning(push)
  33 #pragma warning(disable:4127 4244)  // Conditional expression is constant
  34 #endif
  35
  36 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) && !defined(BOOST_NO_CXX11_NOEXCEPT)
  37 #define BOOST_GCD_NOEXCEPT(T) noexcept(std::is_arithmetic<T>::value)
  38 #else
  39 #define BOOST_GCD_NOEXCEPT(T)
  40 #endif
  41
  42 namespace boost {
  43
  44    template <class I>
  45    class rational;
  46
  47    namespace integer {
  48
  49       namespace gcd_detail{
  50
  51          //
  52          // some helper functions which really should be constexpr already, but sadly aren't:
  53          //
  54 #ifndef BOOST_NO_CXX14_CONSTEXPR
  55          template <class T>
  56          inline constexpr T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T)
  57          {
  58             return a < b ? a : b;
  59          }
  60          template <class T>
  61          inline constexpr auto constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T) -> decltype(a.swap(b))
  62          {
  63             return a.swap(b);
  64          }
  65          template <class T, class U>
  66          inline constexpr void constexpr_swap(T&a, U& b...) BOOST_GCD_NOEXCEPT(T)
  67          {
  68             T t(static_cast<T&&>(a));
  69             a = static_cast<T&&>(b);
  70             b = static_cast<T&&>(t);
  71          }
  72 #else
  73          template <class T>
  74          inline T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T)
  75          {
  76             return a < b ? a : b;
  77          }
  78          template <class T>
  79          inline void constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T)
  80          {
  81             using std::swap;
  82             swap(a, b);
  83          }
  84 #endif
  85
  86       template <class T, bool a =
  87 #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS
  88          std::is_unsigned<T>::value ||
  89 #endif
  90          (std::numeric_limits<T>::is_specialized && !std::numeric_limits<T>::is_signed)>
  91       struct gcd_traits_abs_defaults
  92       {
  93          inline static BOOST_CXX14_CONSTEXPR const T& abs(const T& val) BOOST_GCD_NOEXCEPT(T) { return val; }
  94       };
  95       template <class T>
  96       struct gcd_traits_abs_defaults<T, false>
  97       {
  98          inline static T BOOST_CXX14_CONSTEXPR abs(const T& val) BOOST_GCD_NOEXCEPT(T)
  99          {
 100             // This sucks, but std::abs is not constexpr :(
 101             return val < T(0) ? -val : val;
 102          }
 103       };
 104
 105       enum method_type
 106       {
 107          method_euclid = 0,
 108          method_binary = 1,
 109          method_mixed = 2
 110       };
 111
 112       struct any_convert
 113       {
 114          template <class T>
 115          any_convert(const T&);
 116       };
 117
 118       struct unlikely_size
 119       {
 120          char buf[9973];
 121       };
 122
 123       unlikely_size operator <<= (any_convert, any_convert);
 124       unlikely_size operator >>= (any_convert, any_convert);
 125
 126       template <class T>
 127       struct gcd_traits_defaults : public gcd_traits_abs_defaults<T>
 128       {
 129          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(T& val) BOOST_GCD_NOEXCEPT(T)
 130          {
 131             unsigned r = 0;
 132             while(0 == (val & 1u))
 133             {
 134 #ifdef _MSC_VER  // VC++ can't handle operator >>= in constexpr code for some reason
 135                val = val >> 1;
 136 #else
 137                val >>= 1;
 138 #endif
 139                ++r;
 140             }
 141             return r;
 142          }
 143          inline static BOOST_CXX14_CONSTEXPR bool less(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T)
 144          {
 145             return a < b;
 146          }
 147
 148          static T& get_value();
 149
 150 #ifndef BOOST_NO_SFINAE
 151          static const bool has_operator_left_shift_equal = sizeof(get_value() <<= 2) != sizeof(unlikely_size);
 152          static const bool has_operator_right_shift_equal = sizeof(get_value() >>= 2) != sizeof(unlikely_size);
 153 #else
 154          static const bool has_operator_left_shift_equal = true;
 155          static const bool has_operator_right_shift_equal = true;
 156 #endif
 157          static const method_type method = std::numeric_limits<T>::is_specialized && std::numeric_limits<T>::is_integer && has_operator_left_shift_equal && has_operator_right_shift_equal ? method_mixed : method_euclid;
 158       };
 159       //
 160       // Default gcd_traits just inherits from defaults:
 161       //
 162       template <class T>
 163       struct gcd_traits : public gcd_traits_defaults<T> {};
 164
 165       //
 166       // Some platforms have fast bitscan operations, that allow us to implement
 167       // make_odd much more efficiently, unfortunately we can't use these if we want
 168       // the functions to be constexpr as the compiler intrinsics aren't constexpr.
 169       //
 170 #if defined(BOOST_NO_CXX14_CONSTEXPR) && ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
 171 #pragma intrinsic(_BitScanForward,)
 172       template <>
 173       struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long>
 174       {
 175          BOOST_FORCEINLINE static unsigned find_lsb(unsigned long val) BOOST_NOEXCEPT
 176          {
 177             unsigned long result;
 178             _BitScanForward(&result, val);
 179             return result;
 180          }
 181          BOOST_FORCEINLINE static unsigned make_odd(unsigned long& val) BOOST_NOEXCEPT
 182          {
 183             unsigned result = find_lsb(val);
 184             val >>= result;
 185             return result;
 186          }
 187       };
 188
 189 #ifdef _M_X64
 190 #pragma intrinsic(_BitScanForward64)
 191       template <>
 192       struct gcd_traits<unsigned __int64> : public gcd_traits_defaults<unsigned __int64>
 193       {
 194          BOOST_FORCEINLINE static unsigned find_lsb(unsigned __int64 mask) BOOST_NOEXCEPT
 195          {
 196             unsigned long result;
 197             _BitScanForward64(&result, mask);
 198             return result;
 199          }
 200          BOOST_FORCEINLINE static unsigned make_odd(unsigned __int64& val) BOOST_NOEXCEPT
 201          {
 202             unsigned result = find_lsb(val);
 203             val >>= result;
 204             return result;
 205          }
 206       };
 207 #endif
 208       //
 209       // Other integer type are trivial adaptations of the above,
 210       // this works for signed types too, as by the time these functions
 211       // are called, all values are > 0.
 212       //
 213       template <> struct gcd_traits<long> : public gcd_traits_defaults<long>
 214       { BOOST_FORCEINLINE static unsigned make_odd(long& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 215       template <> struct gcd_traits<unsigned int> : public gcd_traits_defaults<unsigned int>
 216       { BOOST_FORCEINLINE static unsigned make_odd(unsigned int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 217       template <> struct gcd_traits<int> : public gcd_traits_defaults<int>
 218       { BOOST_FORCEINLINE static unsigned make_odd(int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 219       template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short>
 220       { BOOST_FORCEINLINE static unsigned make_odd(unsigned short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 221       template <> struct gcd_traits<short> : public gcd_traits_defaults<short>
 222       { BOOST_FORCEINLINE static unsigned make_odd(short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 223       template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char>
 224       { BOOST_FORCEINLINE static unsigned make_odd(unsigned char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 225       template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char>
 226       { BOOST_FORCEINLINE static signed make_odd(signed char& val)BOOST_NOEXCEPT{ signed result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 227       template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
 228       { BOOST_FORCEINLINE static unsigned make_odd(char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 229 #ifndef BOOST_NO_INTRINSIC_WCHAR_T
 230       template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t>
 231       { BOOST_FORCEINLINE static unsigned make_odd(wchar_t& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
 232 #endif
 233 #ifdef _M_X64
 234       template <> struct gcd_traits<__int64> : public gcd_traits_defaults<__int64>
 235       { BOOST_FORCEINLINE static unsigned make_odd(__int64& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned __int64>::find_lsb(val); val >>= result; return result; } };
 236 #endif
 237
 238 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
 239
 240       template <>
 241       struct gcd_traits<unsigned> : public gcd_traits_defaults<unsigned>
 242       {
 243          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned mask)BOOST_NOEXCEPT
 244          {
 245             return __builtin_ctz(mask);
 246          }
 247          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned& val)BOOST_NOEXCEPT
 248          {
 249             unsigned result = find_lsb(val);
 250             val >>= result;
 251             return result;
 252          }
 253       };
 254       template <>
 255       struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long>
 256       {
 257          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned long mask)BOOST_NOEXCEPT
 258          {
 259             return __builtin_ctzl(mask);
 260          }
 261          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned long& val)BOOST_NOEXCEPT
 262          {
 263             unsigned result = find_lsb(val);
 264             val >>= result;
 265             return result;
 266          }
 267       };
 268       template <>
 269       struct gcd_traits<boost::ulong_long_type> : public gcd_traits_defaults<boost::ulong_long_type>
 270       {
 271          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(boost::ulong_long_type mask)BOOST_NOEXCEPT
 272          {
 273             return __builtin_ctzll(mask);
 274          }
 275          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(boost::ulong_long_type& val)BOOST_NOEXCEPT
 276          {
 277             unsigned result = find_lsb(val);
 278             val >>= result;
 279             return result;
 280          }
 281       };
 282       //
 283       // Other integer type are trivial adaptations of the above,
 284       // this works for signed types too, as by the time these functions
 285       // are called, all values are > 0.
 286       //
 287       template <> struct gcd_traits<boost::long_long_type> : public gcd_traits_defaults<boost::long_long_type>
 288       {
 289          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(boost::long_long_type& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<boost::ulong_long_type>::find_lsb(val); val >>= result; return result; }
 290       };
 291       template <> struct gcd_traits<long> : public gcd_traits_defaults<long>
 292       {
 293          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(long& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; }
 294       };
 295       template <> struct gcd_traits<int> : public gcd_traits_defaults<int>
 296       {
 297          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(int& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; }
 298       };
 299       template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short>
 300       {
 301          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned short& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 302       };
 303       template <> struct gcd_traits<short> : public gcd_traits_defaults<short>
 304       {
 305          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(short& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 306       };
 307       template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char>
 308       {
 309          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 310       };
 311       template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char>
 312       {
 313          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR signed make_odd(signed char& val)BOOST_NOEXCEPT { signed result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 314       };
 315       template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
 316       {
 317          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 318       };
 319 #ifndef BOOST_NO_INTRINSIC_WCHAR_T
 320       template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t>
 321       {
 322          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(wchar_t& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
 323       };
 324 #endif
 325 #endif
 326    //
 327    // The Mixed Binary Euclid Algorithm
 328    // Sidi Mohamed Sedjelmaci
 329    // Electronic Notes in Discrete Mathematics 35 (2009) 169-176
 330    //
 331    template <class T>
 332    BOOST_CXX14_CONSTEXPR T mixed_binary_gcd(T u, T v) BOOST_GCD_NOEXCEPT(T)
 333    {
 334       if(gcd_traits<T>::less(u, v))
 335          constexpr_swap(u, v);
 336
 337       unsigned shifts = 0;
 338
 339       if(u == T(0))
 340          return v;
 341       if(v == T(0))
 342          return u;
 343
 344       shifts = constexpr_min(gcd_traits<T>::make_odd(u), gcd_traits<T>::make_odd(v));
 345
 346       while(gcd_traits<T>::less(1, v))
 347       {
 348          u %= v;
 349          v -= u;
 350          if(u == T(0))
 351             return v << shifts;
 352          if(v == T(0))
 353             return u << shifts;
 354          gcd_traits<T>::make_odd(u);
 355          gcd_traits<T>::make_odd(v);
 356          if(gcd_traits<T>::less(u, v))
 357             constexpr_swap(u, v);
 358       }
 359       return (v == 1 ? v : u) << shifts;
 360    }
 361
 362     /** Stein gcd (aka 'binary gcd')
 363      *
 364      * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose
 365      */
 366     template <typename SteinDomain>
 367     BOOST_CXX14_CONSTEXPR SteinDomain Stein_gcd(SteinDomain m, SteinDomain n) BOOST_GCD_NOEXCEPT(SteinDomain)
 368     {
 369         BOOST_ASSERT(m >= 0);
 370         BOOST_ASSERT(n >= 0);
 371         if (m == SteinDomain(0))
 372             return n;
 373         if (n == SteinDomain(0))
 374             return m;
 375         // m > 0 && n > 0
 376         int d_m = gcd_traits<SteinDomain>::make_odd(m);
 377         int d_n = gcd_traits<SteinDomain>::make_odd(n);
 378         // odd(m) && odd(n)
 379         while (m != n)
 380         {
 381             if (n > m)
 382                constexpr_swap(n, m);
 383             m -= n;
 384             gcd_traits<SteinDomain>::make_odd(m);
 385         }
 386         // m == n
 387         m <<= constexpr_min(d_m, d_n);
 388         return m;
 389     }
 390
 391
 392     /** Euclidean algorithm
 393      *
 394      * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose
 395      *
 396      */
 397     template <typename EuclideanDomain>
 398     inline BOOST_CXX14_CONSTEXPR EuclideanDomain Euclid_gcd(EuclideanDomain a, EuclideanDomain b) BOOST_GCD_NOEXCEPT(EuclideanDomain)
 399     {
 400         while (b != EuclideanDomain(0))
 401         {
 402             a %= b;
 403             constexpr_swap(a, b);
 404         }
 405         return a;
 406     }
 407
 408
 409     template <typename T>
 410     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_mixed, T>::type
 411        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
 412     {
 413        return gcd_detail::mixed_binary_gcd(a, b);
 414     }
 415
 416     template <typename T>
 417     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_binary, T>::type
 418        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
 419     {
 420        return gcd_detail::Stein_gcd(a, b);
 421     }
 422
 423     template <typename T>
 424     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_euclid, T>::type
 425        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
 426     {
 427        return gcd_detail::Euclid_gcd(a, b);
 428     }
 429
 430     template <class T>
 431     inline BOOST_CXX14_CONSTEXPR T lcm_imp(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T)
 432     {
 433        T temp = boost::integer::gcd_detail::optimal_gcd_select(a, b);
 434 #if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40500)
 435        return (temp != T(0)) ? T(a / temp * b) : T(0);
 436 #else
 437        return temp != T(0) ? T(a / temp * b) : T(0);
 438 #endif
 439     }
 440
 441 } // namespace detail
 442
 443
 444 template <typename Integer>
 445 inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer)
 446 {
 447     if(a == (std::numeric_limits<Integer>::min)())
 448        return a == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(b) : boost::integer::gcd(static_cast<Integer>(a % b), b);
 449     else if (b == (std::numeric_limits<Integer>::min)())
 450        return b == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(a) : boost::integer::gcd(a, static_cast<Integer>(b % a));
 451     return gcd_detail::optimal_gcd_select(static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(b)));
 452 }
 453
 454 template <typename Integer>
 455 inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer)
 456 {
 457    return gcd_detail::lcm_imp(static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(b)));
 458 }
 459 #ifndef BOOST_NO_CXX11_VARIADIC_TEMPLATES
 460 //
 461 // This looks slightly odd, but the variadic forms must have 3 or more arguments, and the variadic argument pack may be empty.
 462 // This matters not at all for most compilers, but Oracle C++ selects the wrong overload in the 2-arg case unless we do this.
 463 //
 464 template <typename Integer, typename... Args>
 465 inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b, const Integer& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer)
 466 {
 467    Integer t = gcd(b, c, args...);
 468    return t == 1 ? 1 : gcd(a, t);
 469 }
 470
 471 template <typename Integer, typename... Args>
 472 inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b, Integer const& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer)
 473 {
 474    return lcm(a, lcm(b, c, args...));
 475 }
 476 #endif
 477 //
 478 // Special handling for rationals:
 479 //
 480 template <typename Integer>
 481 inline typename boost::enable_if_c<std::numeric_limits<Integer>::is_specialized, boost::rational<Integer> >::type gcd(boost::rational<Integer> const &a, boost::rational<Integer> const &b)
 482 {
 483    return boost::rational<Integer>(static_cast<Integer>(gcd(a.numerator(), b.numerator())), static_cast<Integer>(lcm(a.denominator(), b.denominator())));
 484 }
 485
 486 template <typename Integer>
 487 inline typename boost::enable_if_c<std::numeric_limits<Integer>::is_specialized, boost::rational<Integer> >::type lcm(boost::rational<Integer> const &a, boost::rational<Integer> const &b)
 488 {
 489    return boost::rational<Integer>(static_cast<Integer>(lcm(a.numerator(), b.numerator())), static_cast<Integer>(gcd(a.denominator(), b.denominator())));
 490 }
 491 /**
 492  * Knuth, The Art of Computer Programming: Volume 2, Third edition, 1998
 493  * Chapter 4.5.2, Algorithm C: Greatest common divisor of n integers.
 494  *
 495  * Knuth counts down from n to zero but we naturally go from first to last.
 496  * We also return the termination position because it might be useful to know.
 497  *
 498  * Partly by quirk, partly by design, this algorithm is defined for n = 1,
 499  * because the gcd of {x} is x. It is not defined for n = 0.
 500  *
 501  * @tparam  I   Input iterator.
 502  * @return  The gcd of the range and the iterator position at termination.
 503  */
 504 template <typename I>
 505 std::pair<typename std::iterator_traits<I>::value_type, I>
 506 gcd_range(I first, I last) BOOST_GCD_NOEXCEPT(I)
 507 {
 508     BOOST_ASSERT(first != last);
 509     typedef typename std::iterator_traits<I>::value_type T;
 510
 511     T d = *first++;
 512     while (d != T(1) && first != last)
 513     {
 514         d = gcd(d, *first);
 515         first++;
 516     }
 517     return std::make_pair(d, first);
 518 }
 519 template <typename I>
 520 std::pair<typename std::iterator_traits<I>::value_type, I>
 521 lcm_range(I first, I last) BOOST_GCD_NOEXCEPT(I)
 522 {
 523     BOOST_ASSERT(first != last);
 524     typedef typename std::iterator_traits<I>::value_type T;
 525
 526     T d = *first++;
 527     while (d != T(1) && first != last)
 528     {
 529         d = lcm(d, *first);
 530         first++;
 531     }
 532     return std::make_pair(d, first);
 533 }
 534
 535 template < typename IntegerType >
 536 class gcd_evaluator
 537 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
 538    : public std::binary_function<IntegerType, IntegerType, IntegerType>
 539 #endif
 540 {
 541 public:
 542 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
 543    typedef IntegerType first_argument_type;
 544    typedef IntegerType second_argument_type;
 545    typedef IntegerType result_type;
 546 #endif
 547    IntegerType operator()(IntegerType const &a, IntegerType const &b)const
 548    {
 549       return boost::integer::gcd(a, b);
 550    }
 551 };
 552
 553 template < typename IntegerType >
 554 class lcm_evaluator
 555 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
 556    : public std::binary_function<IntegerType, IntegerType, IntegerType>
 557 #endif
 558 {
 559 public:
 560 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
 561    typedef IntegerType first_argument_type;
 562    typedef IntegerType second_argument_type;
 563    typedef IntegerType result_type;
 564 #endif
 565    IntegerType operator()(IntegerType const &a, IntegerType const &b)const
 566    {
 567       return boost::integer::lcm(a, b);
 568    }
 569 };
 570
 571 }  // namespace integer
 572 }  // namespace boost
 573
 574 #ifdef BOOST_MSVC
 575 #pragma warning(pop)
 576 #endif
 577
 578 #endif  // BOOST_INTEGER_COMMON_FACTOR_RT_HPP