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>
constexpr_min(T const & a,T const & b)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>
constexpr_swap(T & a,T & b)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>
constexpr_swap(T & a,U & b...)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 {
absboost::integer::gcd_detail::gcd_traits_abs_defaults93 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 {
absboost::integer::gcd_detail::gcd_traits_abs_defaults98 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 {
make_oddboost::integer::gcd_detail::gcd_traits_defaults129 BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(T& val) BOOST_GCD_NOEXCEPT(T)
130 {
131 unsigned r = 0;
132 while (T(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 }
lessboost::integer::gcd_detail::gcd_traits_defaults143 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 {
find_lsbboost::integer::gcd_detail::gcd_traits175 BOOST_FORCEINLINE static unsigned find_lsb(unsigned long val) BOOST_NOEXCEPT
176 {
177 unsigned long result;
178 _BitScanForward(&result, val);
179 return result;
180 }
make_oddboost::integer::gcd_detail::gcd_traits181 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 {
find_lsbboost::integer::gcd_detail::gcd_traits194 BOOST_FORCEINLINE static unsigned find_lsb(unsigned __int64 mask) BOOST_NOEXCEPT
195 {
196 unsigned long result;
197 _BitScanForward64(&result, mask);
198 return result;
199 }
make_oddboost::integer::gcd_detail::gcd_traits200 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>
make_oddboost::integer::gcd_detail::gcd_traits214 { 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>
make_oddboost::integer::gcd_detail::gcd_traits216 { 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>
make_oddboost::integer::gcd_detail::gcd_traits218 { 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>
make_oddboost::integer::gcd_detail::gcd_traits220 { 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>
make_oddboost::integer::gcd_detail::gcd_traits222 { 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>
make_oddboost::integer::gcd_detail::gcd_traits224 { 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>
make_oddboost::integer::gcd_detail::gcd_traits226 { BOOST_FORCEINLINE static unsigned make_odd(signed char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } };
227 template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
make_oddboost::integer::gcd_detail::gcd_traits228 { 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>
make_oddboost::integer::gcd_detail::gcd_traits231 { 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>
make_oddboost::integer::gcd_detail::gcd_traits235 { 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 {
find_lsbboost::integer::gcd_detail::gcd_traits243 BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned mask)BOOST_NOEXCEPT
244 {
245 return __builtin_ctz(mask);
246 }
make_oddboost::integer::gcd_detail::gcd_traits247 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 {
find_lsbboost::integer::gcd_detail::gcd_traits257 BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned long mask)BOOST_NOEXCEPT
258 {
259 return __builtin_ctzl(mask);
260 }
make_oddboost::integer::gcd_detail::gcd_traits261 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 {
find_lsbboost::integer::gcd_detail::gcd_traits271 BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(boost::ulong_long_type mask)BOOST_NOEXCEPT
272 {
273 return __builtin_ctzll(mask);
274 }
make_oddboost::integer::gcd_detail::gcd_traits275 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 {
make_oddboost::integer::gcd_detail::gcd_traits289 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 {
make_oddboost::integer::gcd_detail::gcd_traits293 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 {
make_oddboost::integer::gcd_detail::gcd_traits297 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 {
make_oddboost::integer::gcd_detail::gcd_traits301 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 {
make_oddboost::integer::gcd_detail::gcd_traits305 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 {
make_oddboost::integer::gcd_detail::gcd_traits309 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 {
make_oddboost::integer::gcd_detail::gcd_traits313 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; }
314 };
315 template <> struct gcd_traits<char> : public gcd_traits_defaults<char>
316 {
make_oddboost::integer::gcd_detail::gcd_traits317 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 {
make_oddboost::integer::gcd_detail::gcd_traits322 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>
mixed_binary_gcd(T u,T v)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>
Stein_gcd(SteinDomain m,SteinDomain n)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 unsigned d_m = gcd_traits<SteinDomain>::make_odd(m);
377 unsigned 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>
Euclid_gcd(EuclideanDomain a,EuclideanDomain b)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
optimal_gcd_select(T const & a,T const & b)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
optimal_gcd_select(T const & a,T const & b)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
optimal_gcd_select(T const & a,T const & b)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>
lcm_imp(const T & a,const T & b)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>
gcd(Integer const & a,Integer const & b)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>
lcm(Integer const & a,Integer const & b)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>
gcd(Integer const & a,Integer const & b,const Integer & c,Args const &...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>
lcm(Integer const & a,Integer const & b,Integer const & c,Args const &...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>
gcd(boost::rational<Integer> const & a,boost::rational<Integer> const & b)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>
lcm(boost::rational<Integer> const & a,boost::rational<Integer> const & b)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>
gcd_range(I first,I last)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 ++first;
513 while (d != T(1) && first != last)
514 {
515 d = gcd(d, *first);
516 ++first;
517 }
518 return std::make_pair(d, first);
519 }
520 template <typename I>
521 std::pair<typename std::iterator_traits<I>::value_type, I>
lcm_range(I first,I last)522 lcm_range(I first, I last) BOOST_GCD_NOEXCEPT(I)
523 {
524 BOOST_ASSERT(first != last);
525 typedef typename std::iterator_traits<I>::value_type T;
526
527 T d = *first;
528 ++first;
529 while (d != T(0) && first != last)
530 {
531 d = lcm(d, *first);
532 ++first;
533 }
534 return std::make_pair(d, first);
535 }
536
537 template < typename IntegerType >
538 class gcd_evaluator
539 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
540 : public std::binary_function<IntegerType, IntegerType, IntegerType>
541 #endif
542 {
543 public:
544 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
545 typedef IntegerType first_argument_type;
546 typedef IntegerType second_argument_type;
547 typedef IntegerType result_type;
548 #endif
operator ()(IntegerType const & a,IntegerType const & b) const549 IntegerType operator()(IntegerType const &a, IntegerType const &b) const
550 {
551 return boost::integer::gcd(a, b);
552 }
553 };
554
555 template < typename IntegerType >
556 class lcm_evaluator
557 #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
558 : public std::binary_function<IntegerType, IntegerType, IntegerType>
559 #endif
560 {
561 public:
562 #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL
563 typedef IntegerType first_argument_type;
564 typedef IntegerType second_argument_type;
565 typedef IntegerType result_type;
566 #endif
operator ()(IntegerType const & a,IntegerType const & b) const567 IntegerType operator()(IntegerType const &a, IntegerType const &b)const
568 {
569 return boost::integer::lcm(a, b);
570 }
571 };
572
573 } // namespace integer
574 } // namespace boost
575
576 #ifdef BOOST_MSVC
577 #pragma warning(pop)
578 #endif
579
580 #endif // BOOST_INTEGER_COMMON_FACTOR_RT_HPP
581