boost/integer/common_factor_rt.hpp

0001 //  (C) Copyright Jeremy William Murphy 2016.
0002
0003 //  Use, modification and distribution are subject to the
0004 //  Boost Software License, Version 1.0. (See accompanying file
0005 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_INTEGER_COMMON_FACTOR_RT_HPP
0008 #define BOOST_INTEGER_COMMON_FACTOR_RT_HPP
0009
0010 #include <boost/assert.hpp>
0011 #include <boost/core/enable_if.hpp>
0012
0013 #include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.
0014 #include <boost/limits.hpp>  // for std::numeric_limits
0015 #include <climits>           // for CHAR_MIN
0016 #include <boost/detail/workaround.hpp>
0017 #include <iterator>
0018 #include <algorithm>
0019 #include <limits>
0020 #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS
0021 #include <type_traits>
0022 #endif
0023 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
0024 #include <functional>
0025 #endif
0026
0027 #if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
0028 #include <intrin.h>
0029 #endif
0030
0031 #ifdef BOOST_MSVC
0032 #pragma warning(push)
0033 #pragma warning(disable:4127 4244)  // Conditional expression is constant
0034 #endif
0035
0036 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) && !defined(BOOST_NO_CXX11_NOEXCEPT)
0037 #define BOOST_GCD_NOEXCEPT(T) noexcept(std::is_arithmetic<T>::value)
0038 #else
0039 #define BOOST_GCD_NOEXCEPT(T)
0040 #endif
0041
0042 namespace boost {
0043
0044    template <class I>
0045    class rational;
0046
0047    namespace integer {
0048
0049       namespace gcd_detail{
0050
0051          //
0052          // some helper functions which really should be constexpr already, but sadly aren't:
0053          //
0054 #ifndef BOOST_NO_CXX14_CONSTEXPR
0055          template <class T>
0056          inline constexpr T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T)
0057          {
0058             return a < b ? a : b;
0059          }
0060          template <class T>
0061          inline constexpr auto constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T) -> decltype(a.swap(b))
0062          {
0063             return a.swap(b);
0064          }
0065          template <class T, class U>
0066          inline constexpr void constexpr_swap(T&a, U& b...) BOOST_GCD_NOEXCEPT(T)
0067          {
0068             T t(static_cast<T&&>(a));
0069             a = static_cast<T&&>(b);
0070             b = static_cast<T&&>(t);
0071          }
0072 #else
0073          template <class T>
0074          inline T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T)
0075          {
0076             return a < b ? a : b;
0077          }
0078          template <class T>
0079          inline void constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T)
0080          {
0081             using std::swap;
0082             swap(a, b);
0083          }
0084 #endif
0085
0086       template <class T, bool a =
0087 #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS
0088          std::is_unsigned<T>::value ||
0089 #endif
0090          (std::numeric_limits<T>::is_specialized && !std::numeric_limits<T>::is_signed)>
0091       struct gcd_traits_abs_defaults
0092       {
0093          inline static BOOST_CXX14_CONSTEXPR const T& abs(const T& val) BOOST_GCD_NOEXCEPT(T) { return val; }
0094       };
0095       template <class T>
0096       struct gcd_traits_abs_defaults<T, false>
0097       {
0098          inline static T BOOST_CXX14_CONSTEXPR abs(const T& val) BOOST_GCD_NOEXCEPT(T)
0099          {
0100             // This sucks, but std::abs is not constexpr :(
0101             return val < T(0) ? -val : val;
0102          }
0103       };
0104
0105       enum method_type
0106       {
0107          method_euclid = 0,
0108          method_binary = 1,
0109          method_mixed = 2
0110       };
0111
0112       struct any_convert
0113       {
0114          template <class T>
0115          any_convert(const T&);
0116       };
0117
0118       struct unlikely_size
0119       {
0120          char buf[9973];
0121       };
0122
0123       unlikely_size operator <<= (any_convert, any_convert);
0124       unlikely_size operator >>= (any_convert, any_convert);
0125
0126       template <class T>
0127       struct gcd_traits_defaults : public gcd_traits_abs_defaults<T>
0128       {
0129          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(T& val) BOOST_GCD_NOEXCEPT(T)
0130          {
0131             unsigned r = 0;
0132             while (T(0) == (val & 1u))
0133             {
0134 #ifdef _MSC_VER  // VC++ can't handle operator >>= in constexpr code for some reason
0135                val = val >> 1;
0136 #else
0137                val >>= 1;
0138 #endif
0139                ++r;
0140             }
0141             return r;
0142          }
0143          inline static BOOST_CXX14_CONSTEXPR bool less(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T)
0144          {
0145             return a < b;
0146          }
0147
0148          static T& get_value();
0149
0150 #ifndef BOOST_NO_SFINAE
0151          static const bool has_operator_left_shift_equal = sizeof(get_value() <<= 2) != sizeof(unlikely_size);
0152          static const bool has_operator_right_shift_equal = sizeof(get_value() >>= 2) != sizeof(unlikely_size);
0153 #else
0154          static const bool has_operator_left_shift_equal = true;
0155          static const bool has_operator_right_shift_equal = true;
0156 #endif
0157          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;
0158       };
0159       //
0160       // Default gcd_traits just inherits from defaults:
0161       //
0162       template <class T>
0163       struct gcd_traits : public gcd_traits_defaults<T> {};
0164
0165       //
0166       // Some platforms have fast bitscan operations, that allow us to implement
0167       // make_odd much more efficiently, unfortunately we can't use these if we want
0168       // the functions to be constexpr as the compiler intrinsics aren't constexpr.
0169       //
0170 #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))
0171 #pragma intrinsic(_BitScanForward,)
0172       template <>
0173       struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long>
0174       {
0175          BOOST_FORCEINLINE static unsigned find_lsb(unsigned long val) BOOST_NOEXCEPT
0176          {
0177             unsigned long result;
0178             _BitScanForward(&result, val);
0179             return result;
0180          }
0181          BOOST_FORCEINLINE static unsigned make_odd(unsigned long& val) BOOST_NOEXCEPT
0182          {
0183             unsigned result = find_lsb(val);
0184             val >>= result;
0185             return result;
0186          }
0187       };
0188
0189 #ifdef _M_X64
0190 #pragma intrinsic(_BitScanForward64)
0191       template <>
0192       struct gcd_traits<unsigned __int64> : public gcd_traits_defaults<unsigned __int64>
0193       {
0194          BOOST_FORCEINLINE static unsigned find_lsb(unsigned __int64 mask) BOOST_NOEXCEPT
0195          {
0196             unsigned long result;
0197             _BitScanForward64(&result, mask);
0198             return result;
0199          }
0200          BOOST_FORCEINLINE static unsigned make_odd(unsigned __int64& val) BOOST_NOEXCEPT
0201          {
0202             unsigned result = find_lsb(val);
0203             val >>= result;
0204             return result;
0205          }
0206       };
0207 #endif
0208       //
0209       // Other integer type are trivial adaptations of the above,
0210       // this works for signed types too, as by the time these functions
0211       // are called, all values are > 0.
0212       //
0213       template <> struct gcd_traits<long> : public gcd_traits_defaults<long>
0214       { BOOST_FORCEINLINE static unsigned make_odd(long& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0215       template <> struct gcd_traits<unsigned int> : public gcd_traits_defaults<unsigned int>
0216       { BOOST_FORCEINLINE static unsigned make_odd(unsigned int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0217       template <> struct gcd_traits<int> : public gcd_traits_defaults<int>
0218       { BOOST_FORCEINLINE static unsigned make_odd(int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0219       template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short>
0220       { BOOST_FORCEINLINE static unsigned make_odd(unsigned short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0221       template <> struct gcd_traits<short> : public gcd_traits_defaults<short>
0222       { BOOST_FORCEINLINE static unsigned make_odd(short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0223       template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char>
0224       { BOOST_FORCEINLINE static unsigned make_odd(unsigned char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0225       template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char>
0226       { BOOST_FORCEINLINE static unsigned make_odd(signed char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0227       template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
0228       { BOOST_FORCEINLINE static unsigned make_odd(char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0229 #ifndef BOOST_NO_INTRINSIC_WCHAR_T
0230       template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t>
0231       { BOOST_FORCEINLINE static unsigned make_odd(wchar_t& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
0232 #endif
0233 #ifdef _M_X64
0234       template <> struct gcd_traits<__int64> : public gcd_traits_defaults<__int64>
0235       { BOOST_FORCEINLINE static unsigned make_odd(__int64& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned __int64>::find_lsb(val); val >>= result; return result; } };
0236 #endif
0237
0238 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
0239
0240       template <>
0241       struct gcd_traits<unsigned> : public gcd_traits_defaults<unsigned>
0242       {
0243          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned mask)BOOST_NOEXCEPT
0244          {
0245             return __builtin_ctz(mask);
0246          }
0247          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned& val)BOOST_NOEXCEPT
0248          {
0249             unsigned result = find_lsb(val);
0250             val >>= result;
0251             return result;
0252          }
0253       };
0254       template <>
0255       struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long>
0256       {
0257          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned long mask)BOOST_NOEXCEPT
0258          {
0259             return __builtin_ctzl(mask);
0260          }
0261          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned long& val)BOOST_NOEXCEPT
0262          {
0263             unsigned result = find_lsb(val);
0264             val >>= result;
0265             return result;
0266          }
0267       };
0268       template <>
0269       struct gcd_traits<boost::ulong_long_type> : public gcd_traits_defaults<boost::ulong_long_type>
0270       {
0271          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(boost::ulong_long_type mask)BOOST_NOEXCEPT
0272          {
0273             return __builtin_ctzll(mask);
0274          }
0275          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(boost::ulong_long_type& val)BOOST_NOEXCEPT
0276          {
0277             unsigned result = find_lsb(val);
0278             val >>= result;
0279             return result;
0280          }
0281       };
0282       //
0283       // Other integer type are trivial adaptations of the above,
0284       // this works for signed types too, as by the time these functions
0285       // are called, all values are > 0.
0286       //
0287       template <> struct gcd_traits<boost::long_long_type> : public gcd_traits_defaults<boost::long_long_type>
0288       {
0289          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; }
0290       };
0291       template <> struct gcd_traits<long> : public gcd_traits_defaults<long>
0292       {
0293          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; }
0294       };
0295       template <> struct gcd_traits<int> : public gcd_traits_defaults<int>
0296       {
0297          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; }
0298       };
0299       template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short>
0300       {
0301          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; }
0302       };
0303       template <> struct gcd_traits<short> : public gcd_traits_defaults<short>
0304       {
0305          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; }
0306       };
0307       template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char>
0308       {
0309          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; }
0310       };
0311       template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char>
0312       {
0313          BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(signed char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; }
0314       };
0315       template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
0316       {
0317          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; }
0318       };
0319 #ifndef BOOST_NO_INTRINSIC_WCHAR_T
0320       template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t>
0321       {
0322          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; }
0323       };
0324 #endif
0325 #endif
0326    //
0327    // The Mixed Binary Euclid Algorithm
0328    // Sidi Mohamed Sedjelmaci
0329    // Electronic Notes in Discrete Mathematics 35 (2009) 169-176
0330    //
0331    template <class T>
0332    BOOST_CXX14_CONSTEXPR T mixed_binary_gcd(T u, T v) BOOST_GCD_NOEXCEPT(T)
0333    {
0334       if(gcd_traits<T>::less(u, v))
0335          constexpr_swap(u, v);
0336
0337       unsigned shifts = 0;
0338
0339       if(u == T(0))
0340          return v;
0341       if(v == T(0))
0342          return u;
0343
0344       shifts = constexpr_min(gcd_traits<T>::make_odd(u), gcd_traits<T>::make_odd(v));
0345
0346       while(gcd_traits<T>::less(1, v))
0347       {
0348          u %= v;
0349          v -= u;
0350          if(u == T(0))
0351             return v << shifts;
0352          if(v == T(0))
0353             return u << shifts;
0354          gcd_traits<T>::make_odd(u);
0355          gcd_traits<T>::make_odd(v);
0356          if(gcd_traits<T>::less(u, v))
0357             constexpr_swap(u, v);
0358       }
0359       return (v == 1 ? v : u) << shifts;
0360    }
0361
0362     /** Stein gcd (aka 'binary gcd')
0363      *
0364      * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose
0365      */
0366     template <typename SteinDomain>
0367     BOOST_CXX14_CONSTEXPR SteinDomain Stein_gcd(SteinDomain m, SteinDomain n) BOOST_GCD_NOEXCEPT(SteinDomain)
0368     {
0369         BOOST_ASSERT(m >= 0);
0370         BOOST_ASSERT(n >= 0);
0371         if (m == SteinDomain(0))
0372             return n;
0373         if (n == SteinDomain(0))
0374             return m;
0375         // m > 0 && n > 0
0376         unsigned d_m = gcd_traits<SteinDomain>::make_odd(m);
0377         unsigned d_n = gcd_traits<SteinDomain>::make_odd(n);
0378         // odd(m) && odd(n)
0379         while (m != n)
0380         {
0381             if (n > m)
0382                constexpr_swap(n, m);
0383             m -= n;
0384             gcd_traits<SteinDomain>::make_odd(m);
0385         }
0386         // m == n
0387         m <<= constexpr_min(d_m, d_n);
0388         return m;
0389     }
0390
0391
0392     /** Euclidean algorithm
0393      *
0394      * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose
0395      *
0396      */
0397     template <typename EuclideanDomain>
0398     inline BOOST_CXX14_CONSTEXPR EuclideanDomain Euclid_gcd(EuclideanDomain a, EuclideanDomain b) BOOST_GCD_NOEXCEPT(EuclideanDomain)
0399     {
0400         while (b != EuclideanDomain(0))
0401         {
0402             a %= b;
0403             constexpr_swap(a, b);
0404         }
0405         return a;
0406     }
0407
0408
0409     template <typename T>
0410     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_mixed, T>::type
0411        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
0412     {
0413        return gcd_detail::mixed_binary_gcd(a, b);
0414     }
0415
0416     template <typename T>
0417     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_binary, T>::type
0418        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
0419     {
0420        return gcd_detail::Stein_gcd(a, b);
0421     }
0422
0423     template <typename T>
0424     inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_euclid, T>::type
0425        optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T)
0426     {
0427        return gcd_detail::Euclid_gcd(a, b);
0428     }
0429
0430     template <class T>
0431     inline BOOST_CXX14_CONSTEXPR T lcm_imp(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T)
0432     {
0433        T temp = boost::integer::gcd_detail::optimal_gcd_select(a, b);
0434 #if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40500)
0435        return (temp != T(0)) ? T(a / temp * b) : T(0);
0436 #else
0437        return temp != T(0) ? T(a / temp * b) : T(0);
0438 #endif
0439     }
0440
0441 } // namespace detail
0442
0443
0444 template <typename Integer>
0445 inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer)
0446 {
0447     if(a == (std::numeric_limits<Integer>::min)())
0448        return a == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(b) : boost::integer::gcd(static_cast<Integer>(a % b), b);
0449     else if (b == (std::numeric_limits<Integer>::min)())
0450        return b == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(a) : boost::integer::gcd(a, static_cast<Integer>(b % a));
0451     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)));
0452 }
0453
0454 template <typename Integer>
0455 inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer)
0456 {
0457    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)));
0458 }
0459 #ifndef BOOST_NO_CXX11_VARIADIC_TEMPLATES
0460 //
0461 // This looks slightly odd, but the variadic forms must have 3 or more arguments, and the variadic argument pack may be empty.
0462 // This matters not at all for most compilers, but Oracle C++ selects the wrong overload in the 2-arg case unless we do this.
0463 //
0464 template <typename Integer, typename... Args>
0465 inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b, const Integer& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer)
0466 {
0467    Integer t = gcd(b, c, args...);
0468    return t == 1 ? 1 : gcd(a, t);
0469 }
0470
0471 template <typename Integer, typename... Args>
0472 inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b, Integer const& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer)
0473 {
0474    return lcm(a, lcm(b, c, args...));
0475 }
0476 #endif
0477 //
0478 // Special handling for rationals:
0479 //
0480 template <typename Integer>
0481 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)
0482 {
0483    return boost::rational<Integer>(static_cast<Integer>(gcd(a.numerator(), b.numerator())), static_cast<Integer>(lcm(a.denominator(), b.denominator())));
0484 }
0485
0486 template <typename Integer>
0487 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)
0488 {
0489    return boost::rational<Integer>(static_cast<Integer>(lcm(a.numerator(), b.numerator())), static_cast<Integer>(gcd(a.denominator(), b.denominator())));
0490 }
0491 /**
0492  * Knuth, The Art of Computer Programming: Volume 2, Third edition, 1998
0493  * Chapter 4.5.2, Algorithm C: Greatest common divisor of n integers.
0494  *
0495  * Knuth counts down from n to zero but we naturally go from first to last.
0496  * We also return the termination position because it might be useful to know.
0497  *
0498  * Partly by quirk, partly by design, this algorithm is defined for n = 1,
0499  * because the gcd of {x} is x. It is not defined for n = 0.
0500  *
0501  * @tparam  I   Input iterator.
0502  * @return  The gcd of the range and the iterator position at termination.
0503  */
0504 template <typename I>
0505 std::pair<typename std::iterator_traits<I>::value_type, I>
0506 gcd_range(I first, I last) BOOST_GCD_NOEXCEPT(I)
0507 {
0508     BOOST_ASSERT(first != last);
0509     typedef typename std::iterator_traits<I>::value_type T;
0510
0511     T d = *first;
0512     ++first;
0513     while (d != T(1) && first != last)
0514     {
0515         d = gcd(d, *first);
0516         ++first;
0517     }
0518     return std::make_pair(d, first);
0519 }
0520 template <typename I>
0521 std::pair<typename std::iterator_traits<I>::value_type, I>
0522 lcm_range(I first, I last) BOOST_GCD_NOEXCEPT(I)
0523 {
0524     BOOST_ASSERT(first != last);
0525     typedef typename std::iterator_traits<I>::value_type T;
0526
0527     T d = *first;
0528     ++first;
0529     while (d != T(0) && first != last)
0530     {
0531         d = lcm(d, *first);
0532         ++first;
0533     }
0534     return std::make_pair(d, first);
0535 }
0536
0537 template < typename IntegerType >
0538 class gcd_evaluator
0539 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
0540    : public std::binary_function<IntegerType, IntegerType, IntegerType>
0541 #endif
0542 {
0543 public:
0544 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
0545    typedef IntegerType first_argument_type;
0546    typedef IntegerType second_argument_type;
0547    typedef IntegerType result_type;
0548 #endif
0549    IntegerType operator()(IntegerType const &a, IntegerType const &b) const
0550    {
0551       return boost::integer::gcd(a, b);
0552    }
0553 };
0554
0555 template < typename IntegerType >
0556 class lcm_evaluator
0557 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
0558    : public std::binary_function<IntegerType, IntegerType, IntegerType>
0559 #endif
0560 {
0561 public:
0562 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
0563    typedef IntegerType first_argument_type;
0564    typedef IntegerType second_argument_type;
0565    typedef IntegerType result_type;
0566 #endif
0567    IntegerType operator()(IntegerType const &a, IntegerType const &b)const
0568    {
0569       return boost::integer::lcm(a, b);
0570    }
0571 };
0572
0573 }  // namespace integer
0574 }  // namespace boost
0575
0576 #ifdef BOOST_MSVC
0577 #pragma warning(pop)
0578 #endif
0579
0580 #endif  // BOOST_INTEGER_COMMON_FACTOR_RT_HPP