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 https://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
42namespace 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 (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 }
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 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>
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(mask: 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(mask: 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(mask: 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(mask: 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(mask: 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(mask: 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(mask: 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(mask: 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(mask: 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 unsigned make_odd(signed char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(mask: 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(mask: 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(mask: 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 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>
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
444template <typename Integer>
445inline 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
454template <typename Integer>
455inline 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//
464template <typename Integer, typename... Args>
465inline 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
471template <typename Integer, typename... Args>
472inline 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//
480template <typename Integer>
481inline 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
486template <typename Integer>
487inline 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 */
504template <typename I>
505std::pair<typename std::iterator_traits<I>::value_type, I>
506gcd_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}
520template <typename I>
521std::pair<typename std::iterator_traits<I>::value_type, I>
522lcm_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
537template < typename IntegerType >
538class gcd_evaluator
539#ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
540 : public std::binary_function<IntegerType, IntegerType, IntegerType>
541#endif
542{
543public:
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
549 IntegerType operator()(IntegerType const &a, IntegerType const &b) const
550 {
551 return boost::integer::gcd(a, b);
552 }
553};
554
555template < typename IntegerType >
556class lcm_evaluator
557#ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL
558 : public std::binary_function<IntegerType, IntegerType, IntegerType>
559#endif
560{
561public:
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
567 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

source code of boost/libs/integer/include/boost/integer/common_factor_rt.hpp