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