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