]>
Commit | Line | Data |
---|---|---|
1 | /////////////////////////////////////////////////////////////// | |
2 | // Copyright 2012 John Maddock. Distributed under the Boost | |
3 | // Software License, Version 1.0. (See accompanying file | |
4 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_ | |
5 | // | |
6 | // Comparison operators for cpp_int_backend: | |
7 | // | |
8 | #ifndef BOOST_MP_CPP_INT_MISC_HPP | |
9 | #define BOOST_MP_CPP_INT_MISC_HPP | |
10 | ||
11 | #include <boost/multiprecision/detail/bitscan.hpp> // lsb etc | |
12 | #include <boost/integer/common_factor_rt.hpp> // gcd/lcm | |
13 | #include <boost/functional/hash_fwd.hpp> | |
14 | ||
15 | #ifdef BOOST_MSVC | |
16 | #pragma warning(push) | |
17 | #pragma warning(disable:4702) | |
18 | #pragma warning(disable:4127) // conditional expression is constant | |
19 | #pragma warning(disable:4146) // unary minus operator applied to unsigned type, result still unsigned | |
20 | #endif | |
21 | ||
22 | ||
23 | namespace boost{ namespace multiprecision{ namespace backends{ | |
24 | ||
25 | template <class R, class CppInt> | |
26 | void check_in_range(const CppInt& val, const mpl::int_<checked>&) | |
27 | { | |
28 | typedef typename boost::multiprecision::detail::canonical<R, CppInt>::type cast_type; | |
29 | if(val.sign()) | |
30 | { | |
31 | if(val.compare(static_cast<cast_type>((std::numeric_limits<R>::min)())) < 0) | |
32 | BOOST_THROW_EXCEPTION(std::overflow_error("Could not convert to the target type - -value is out of range.")); | |
33 | } | |
34 | else | |
35 | { | |
36 | if(val.compare(static_cast<cast_type>((std::numeric_limits<R>::max)())) > 0) | |
37 | BOOST_THROW_EXCEPTION(std::overflow_error("Could not convert to the target type - -value is out of range.")); | |
38 | } | |
39 | } | |
40 | template <class R, class CppInt> | |
41 | inline void check_in_range(const CppInt& /*val*/, const mpl::int_<unchecked>&) BOOST_NOEXCEPT {} | |
42 | ||
43 | inline void check_is_negative(const mpl::true_&) BOOST_NOEXCEPT {} | |
44 | inline void check_is_negative(const mpl::false_&) | |
45 | { | |
46 | BOOST_THROW_EXCEPTION(std::range_error("Attempt to assign a negative value to an unsigned type.")); | |
47 | } | |
48 | ||
49 | template <class Integer> | |
50 | inline Integer negate_integer(Integer i, const mpl::true_&) BOOST_NOEXCEPT | |
51 | { | |
52 | return -i; | |
53 | } | |
54 | template <class Integer> | |
55 | inline Integer negate_integer(Integer i, const mpl::false_&) BOOST_NOEXCEPT | |
56 | { | |
57 | return ~(i-1); | |
58 | } | |
59 | ||
60 | template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
61 | inline typename enable_if_c<is_integral<R>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, void>::type | |
62 | eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& backend) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
63 | { | |
64 | typedef mpl::int_<Checked1> checked_type; | |
65 | check_in_range<R>(backend, checked_type()); | |
66 | ||
67 | *result = static_cast<R>(backend.limbs()[0]); | |
68 | unsigned shift = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
69 | for(unsigned i = 1; (i < backend.size()) && (shift < static_cast<unsigned>(std::numeric_limits<R>::digits)); ++i) | |
70 | { | |
71 | *result += static_cast<R>(backend.limbs()[i]) << shift; | |
72 | shift += cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
73 | } | |
74 | if(backend.sign()) | |
75 | { | |
76 | check_is_negative(boost::is_signed<R>()); | |
77 | *result = negate_integer(*result, boost::is_signed<R>()); | |
78 | } | |
79 | } | |
80 | ||
81 | template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
82 | inline typename enable_if_c<is_floating_point<R>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, void>::type | |
83 | eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& backend) BOOST_MP_NOEXCEPT_IF(is_arithmetic<R>::value) | |
84 | { | |
85 | typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::const_limb_pointer p = backend.limbs(); | |
86 | unsigned shift = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
87 | *result = static_cast<R>(*p); | |
88 | for(unsigned i = 1; i < backend.size(); ++i) | |
89 | { | |
90 | *result += static_cast<R>(std::ldexp(static_cast<long double>(p[i]), shift)); | |
91 | shift += cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
92 | } | |
93 | if(backend.sign()) | |
94 | *result = -*result; | |
95 | } | |
96 | ||
97 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
98 | BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, bool>::type | |
99 | eval_is_zero(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT | |
100 | { | |
101 | return (val.size() == 1) && (val.limbs()[0] == 0); | |
102 | } | |
103 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
104 | BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, int>::type | |
105 | eval_get_sign(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT | |
106 | { | |
107 | return eval_is_zero(val) ? 0 : val.sign() ? -1 : 1; | |
108 | } | |
109 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
110 | BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
111 | eval_abs(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
112 | { | |
113 | result = val; | |
114 | result.sign(false); | |
115 | } | |
116 | ||
117 | // | |
118 | // Get the location of the least-significant-bit: | |
119 | // | |
120 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
121 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
122 | eval_lsb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
123 | { | |
124 | using default_ops::eval_get_sign; | |
125 | if(eval_get_sign(a) == 0) | |
126 | { | |
127 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
128 | } | |
129 | if(a.sign()) | |
130 | { | |
131 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
132 | } | |
133 | ||
134 | // | |
135 | // Find the index of the least significant limb that is non-zero: | |
136 | // | |
137 | unsigned index = 0; | |
138 | while(!a.limbs()[index] && (index < a.size())) | |
139 | ++index; | |
140 | // | |
141 | // Find the index of the least significant bit within that limb: | |
142 | // | |
143 | unsigned result = boost::multiprecision::detail::find_lsb(a.limbs()[index]); | |
144 | ||
145 | return result + index * cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
146 | } | |
147 | ||
148 | // | |
149 | // Get the location of the most-significant-bit: | |
150 | // | |
151 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
152 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
153 | eval_msb_imp(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
154 | { | |
155 | // | |
156 | // Find the index of the most significant bit that is non-zero: | |
157 | // | |
158 | return (a.size() - 1) * cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits + boost::multiprecision::detail::find_msb(a.limbs()[a.size() - 1]); | |
159 | } | |
160 | ||
161 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
162 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
163 | eval_msb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
164 | { | |
165 | using default_ops::eval_get_sign; | |
166 | if(eval_get_sign(a) == 0) | |
167 | { | |
168 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
169 | } | |
170 | if(a.sign()) | |
171 | { | |
172 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
173 | } | |
174 | return eval_msb_imp(a); | |
175 | } | |
176 | ||
177 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
178 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, bool>::type | |
179 | eval_bit_test(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) BOOST_NOEXCEPT | |
180 | { | |
181 | unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
182 | unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
183 | limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u); | |
184 | if(offset >= val.size()) | |
185 | return false; | |
186 | return val.limbs()[offset] & mask ? true : false; | |
187 | } | |
188 | ||
189 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
190 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
191 | eval_bit_set(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) | |
192 | { | |
193 | unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
194 | unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
195 | limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u); | |
196 | if(offset >= val.size()) | |
197 | { | |
198 | unsigned os = val.size(); | |
199 | val.resize(offset + 1, offset + 1); | |
200 | if(offset >= val.size()) | |
201 | return; // fixed precision overflow | |
202 | for(unsigned i = os; i <= offset; ++i) | |
203 | val.limbs()[i] = 0; | |
204 | } | |
205 | val.limbs()[offset] |= mask; | |
206 | } | |
207 | ||
208 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
209 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
210 | eval_bit_unset(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) BOOST_NOEXCEPT | |
211 | { | |
212 | unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
213 | unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
214 | limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u); | |
215 | if(offset >= val.size()) | |
216 | return; | |
217 | val.limbs()[offset] &= ~mask; | |
218 | val.normalize(); | |
219 | } | |
220 | ||
221 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
222 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
223 | eval_bit_flip(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val, unsigned index) | |
224 | { | |
225 | unsigned offset = index / cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
226 | unsigned shift = index % cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits; | |
227 | limb_type mask = shift ? limb_type(1u) << shift : limb_type(1u); | |
228 | if(offset >= val.size()) | |
229 | { | |
230 | unsigned os = val.size(); | |
231 | val.resize(offset + 1, offset + 1); | |
232 | if(offset >= val.size()) | |
233 | return; // fixed precision overflow | |
234 | for(unsigned i = os; i <= offset; ++i) | |
235 | val.limbs()[i] = 0; | |
236 | } | |
237 | val.limbs()[offset] ^= mask; | |
238 | val.normalize(); | |
239 | } | |
240 | ||
241 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
242 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
243 | eval_qr( | |
244 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, | |
245 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& y, | |
246 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q, | |
247 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
248 | { | |
249 | divide_unsigned_helper(&q, x, y, r); | |
250 | q.sign(x.sign() != y.sign()); | |
251 | r.sign(x.sign()); | |
252 | } | |
253 | ||
254 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
255 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
256 | eval_qr( | |
257 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, | |
258 | limb_type y, | |
259 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q, | |
260 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
261 | { | |
262 | divide_unsigned_helper(&q, x, y, r); | |
263 | q.sign(x.sign()); | |
264 | r.sign(x.sign()); | |
265 | } | |
266 | ||
267 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class U> | |
268 | inline typename enable_if_c<is_integral<U>::value>::type eval_qr( | |
269 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, | |
270 | U y, | |
271 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& q, | |
272 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& r) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
273 | { | |
274 | using default_ops::eval_qr; | |
275 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t; | |
276 | t = y; | |
277 | eval_qr(x, t, q, r); | |
278 | } | |
279 | ||
280 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer> | |
281 | inline typename enable_if_c<is_unsigned<Integer>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, Integer>::type | |
282 | eval_integer_modulus(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, Integer val) | |
283 | { | |
284 | if((sizeof(Integer) <= sizeof(limb_type)) || (val <= (std::numeric_limits<limb_type>::max)())) | |
285 | { | |
286 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> d; | |
287 | divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>*>(0), x, static_cast<limb_type>(val), d); | |
288 | return d.limbs()[0]; | |
289 | } | |
290 | else | |
291 | { | |
292 | return default_ops::eval_integer_modulus(x, val); | |
293 | } | |
294 | } | |
295 | ||
296 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer> | |
297 | BOOST_MP_FORCEINLINE typename enable_if_c<is_signed<Integer>::value && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, Integer>::type | |
298 | eval_integer_modulus(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& x, Integer val) | |
299 | { | |
300 | return eval_integer_modulus(x, boost::multiprecision::detail::unsigned_abs(val)); | |
301 | } | |
302 | ||
303 | inline limb_type integer_gcd_reduce(limb_type u, limb_type v) | |
304 | { | |
305 | do | |
306 | { | |
307 | if(u > v) | |
308 | std::swap(u, v); | |
309 | if(u == v) | |
310 | break; | |
311 | v -= u; | |
312 | v >>= boost::multiprecision::detail::find_lsb(v); | |
313 | } while(true); | |
314 | return u; | |
315 | } | |
316 | ||
317 | inline double_limb_type integer_gcd_reduce(double_limb_type u, double_limb_type v) | |
318 | { | |
319 | do | |
320 | { | |
321 | if(u > v) | |
322 | std::swap(u, v); | |
323 | if(u == v) | |
324 | break; | |
325 | if(v <= ~static_cast<limb_type>(0)) | |
326 | { | |
327 | u = integer_gcd_reduce(static_cast<limb_type>(v), static_cast<limb_type>(u)); | |
328 | break; | |
329 | } | |
330 | v -= u; | |
331 | #ifdef __MSVC_RUNTIME_CHECKS | |
332 | while((v & 1u) == 0) | |
333 | #else | |
334 | while((static_cast<unsigned>(v) & 1u) == 0) | |
335 | #endif | |
336 | v >>= 1; | |
337 | } while(true); | |
338 | return u; | |
339 | } | |
340 | ||
341 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
342 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
343 | eval_gcd( | |
344 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, | |
345 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, | |
346 | limb_type v) | |
347 | { | |
348 | using default_ops::eval_lsb; | |
349 | using default_ops::eval_is_zero; | |
350 | using default_ops::eval_get_sign; | |
351 | ||
352 | int shift; | |
353 | ||
354 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> u(a); | |
355 | ||
356 | int s = eval_get_sign(u); | |
357 | ||
358 | /* GCD(0,x) := x */ | |
359 | if(s < 0) | |
360 | { | |
361 | u.negate(); | |
362 | } | |
363 | else if(s == 0) | |
364 | { | |
365 | result = v; | |
366 | return; | |
367 | } | |
368 | if(v == 0) | |
369 | { | |
370 | result = u; | |
371 | return; | |
372 | } | |
373 | ||
374 | /* Let shift := lg K, where K is the greatest power of 2 | |
375 | dividing both u and v. */ | |
376 | ||
377 | unsigned us = eval_lsb(u); | |
378 | unsigned vs = boost::multiprecision::detail::find_lsb(v); | |
379 | shift = (std::min)(us, vs); | |
380 | eval_right_shift(u, us); | |
381 | if(vs) | |
382 | v >>= vs; | |
383 | ||
384 | do | |
385 | { | |
386 | /* Now u and v are both odd, so diff(u, v) is even. | |
387 | Let u = min(u, v), v = diff(u, v)/2. */ | |
388 | if(u.size() <= 2) | |
389 | { | |
390 | if(u.size() == 1) | |
391 | v = integer_gcd_reduce(*u.limbs(), v); | |
392 | else | |
393 | { | |
394 | double_limb_type i; | |
395 | i = u.limbs()[0] | (static_cast<double_limb_type>(u.limbs()[1]) << sizeof(limb_type) * CHAR_BIT); | |
396 | v = static_cast<limb_type>(integer_gcd_reduce(i, static_cast<double_limb_type>(v))); | |
397 | } | |
398 | break; | |
399 | } | |
400 | eval_subtract(u, v); | |
401 | us = eval_lsb(u); | |
402 | eval_right_shift(u, us); | |
403 | } | |
404 | while(true); | |
405 | ||
406 | result = v; | |
407 | eval_left_shift(result, shift); | |
408 | } | |
409 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer> | |
410 | inline typename enable_if_c<is_unsigned<Integer>::value && (sizeof(Integer) <= sizeof(limb_type)) && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
411 | eval_gcd( | |
412 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, | |
413 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, | |
414 | const Integer& v) | |
415 | { | |
416 | eval_gcd(result, a, static_cast<limb_type>(v)); | |
417 | } | |
418 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class Integer> | |
419 | inline typename enable_if_c<is_signed<Integer>::value && (sizeof(Integer) <= sizeof(limb_type)) && !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
420 | eval_gcd( | |
421 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, | |
422 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, | |
423 | const Integer& v) | |
424 | { | |
425 | eval_gcd(result, a, static_cast<limb_type>(v < 0 ? -v : v)); | |
426 | } | |
427 | ||
428 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
429 | inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
430 | eval_gcd( | |
431 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, | |
432 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, | |
433 | const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) | |
434 | { | |
435 | using default_ops::eval_lsb; | |
436 | using default_ops::eval_is_zero; | |
437 | using default_ops::eval_get_sign; | |
438 | ||
439 | if(a.size() == 1) | |
440 | { | |
441 | eval_gcd(result, b, *a.limbs()); | |
442 | return; | |
443 | } | |
444 | if(b.size() == 1) | |
445 | { | |
446 | eval_gcd(result, a, *b.limbs()); | |
447 | return; | |
448 | } | |
449 | ||
450 | int shift; | |
451 | ||
452 | cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> u(a), v(b); | |
453 | ||
454 | int s = eval_get_sign(u); | |
455 | ||
456 | /* GCD(0,x) := x */ | |
457 | if(s < 0) | |
458 | { | |
459 | u.negate(); | |
460 | } | |
461 | else if(s == 0) | |
462 | { | |
463 | result = v; | |
464 | return; | |
465 | } | |
466 | s = eval_get_sign(v); | |
467 | if(s < 0) | |
468 | { | |
469 | v.negate(); | |
470 | } | |
471 | else if(s == 0) | |
472 | { | |
473 | result = u; | |
474 | return; | |
475 | } | |
476 | ||
477 | /* Let shift := lg K, where K is the greatest power of 2 | |
478 | dividing both u and v. */ | |
479 | ||
480 | unsigned us = eval_lsb(u); | |
481 | unsigned vs = eval_lsb(v); | |
482 | shift = (std::min)(us, vs); | |
483 | eval_right_shift(u, us); | |
484 | eval_right_shift(v, vs); | |
485 | ||
486 | do | |
487 | { | |
488 | /* Now u and v are both odd, so diff(u, v) is even. | |
489 | Let u = min(u, v), v = diff(u, v)/2. */ | |
490 | s = u.compare(v); | |
491 | if(s > 0) | |
492 | u.swap(v); | |
493 | if(s == 0) | |
494 | break; | |
495 | if(v.size() <= 2) | |
496 | { | |
497 | if(v.size() == 1) | |
498 | u = integer_gcd_reduce(*v.limbs(), *u.limbs()); | |
499 | else | |
500 | { | |
501 | double_limb_type i, j; | |
502 | i = v.limbs()[0] | (static_cast<double_limb_type>(v.limbs()[1]) << sizeof(limb_type) * CHAR_BIT); | |
503 | j = (u.size() == 1) ? *u.limbs() : u.limbs()[0] | (static_cast<double_limb_type>(u.limbs()[1]) << sizeof(limb_type) * CHAR_BIT); | |
504 | u = integer_gcd_reduce(i, j); | |
505 | } | |
506 | break; | |
507 | } | |
508 | eval_subtract(v, u); | |
509 | vs = eval_lsb(v); | |
510 | eval_right_shift(v, vs); | |
511 | } | |
512 | while(true); | |
513 | ||
514 | result = u; | |
515 | eval_left_shift(result, shift); | |
516 | } | |
517 | // | |
518 | // Now again for trivial backends: | |
519 | // | |
520 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
521 | BOOST_MP_FORCEINLINE typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type | |
522 | eval_gcd(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_NOEXCEPT | |
523 | { | |
524 | *result.limbs() = boost::integer::gcd(*a.limbs(), *b.limbs()); | |
525 | } | |
526 | // This one is only enabled for unchecked cpp_int's, for checked int's we need the checking in the default version: | |
527 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
528 | BOOST_MP_FORCEINLINE typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && (Checked1 == unchecked)>::type | |
529 | eval_lcm(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)) | |
530 | { | |
531 | *result.limbs() = boost::integer::lcm(*a.limbs(), *b.limbs()); | |
532 | result.normalize(); // result may overflow the specified number of bits | |
533 | } | |
534 | ||
535 | inline void conversion_overflow(const mpl::int_<checked>&) | |
536 | { | |
537 | BOOST_THROW_EXCEPTION(std::overflow_error("Overflow in conversion to narrower type")); | |
538 | } | |
539 | inline void conversion_overflow(const mpl::int_<unchecked>&){} | |
540 | ||
541 | template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
542 | inline typename enable_if_c< | |
543 | is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value | |
544 | && is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value | |
545 | && boost::is_convertible<typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type, R>::value | |
546 | >::type | |
547 | eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) | |
548 | { | |
549 | typedef typename common_type<R, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type>::type common_type; | |
550 | if(std::numeric_limits<R>::is_specialized && (static_cast<common_type>(*val.limbs()) > static_cast<common_type>((std::numeric_limits<R>::max)()))) | |
551 | { | |
552 | if(val.isneg()) | |
553 | { | |
554 | if(static_cast<common_type>(*val.limbs()) > -static_cast<common_type>((std::numeric_limits<R>::min)())) | |
555 | conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type()); | |
556 | *result = (std::numeric_limits<R>::min)(); | |
557 | } | |
558 | else | |
559 | { | |
560 | conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type()); | |
561 | *result = (std::numeric_limits<R>::max)(); | |
562 | } | |
563 | } | |
564 | else | |
565 | { | |
566 | *result = static_cast<R>(*val.limbs()); | |
567 | if(val.isneg()) | |
568 | { | |
569 | check_is_negative(mpl::bool_<is_signed_number<R>::value || (number_category<R>::value == number_kind_floating_point)>()); | |
570 | *result = negate_integer(*result, mpl::bool_<is_signed_number<R>::value || (number_category<R>::value == number_kind_floating_point)>()); | |
571 | } | |
572 | } | |
573 | } | |
574 | ||
575 | template <class R, unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
576 | inline typename enable_if_c< | |
577 | is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value | |
578 | && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value | |
579 | && boost::is_convertible<typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type, R>::value | |
580 | >::type | |
581 | eval_convert_to(R* result, const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) | |
582 | { | |
583 | typedef typename common_type<R, typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::local_limb_type>::type common_type; | |
584 | if(std::numeric_limits<R>::is_specialized && (static_cast<common_type>(*val.limbs()) > static_cast<common_type>((std::numeric_limits<R>::max)()))) | |
585 | { | |
586 | conversion_overflow(typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type()); | |
587 | *result = (std::numeric_limits<R>::max)(); | |
588 | } | |
589 | else | |
590 | *result = static_cast<R>(*val.limbs()); | |
591 | } | |
592 | ||
593 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
594 | inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
595 | eval_lsb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
596 | { | |
597 | using default_ops::eval_get_sign; | |
598 | if(eval_get_sign(a) == 0) | |
599 | { | |
600 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
601 | } | |
602 | if(a.sign()) | |
603 | { | |
604 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
605 | } | |
606 | // | |
607 | // Find the index of the least significant bit within that limb: | |
608 | // | |
609 | return boost::multiprecision::detail::find_lsb(*a.limbs()); | |
610 | } | |
611 | ||
612 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
613 | inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
614 | eval_msb_imp(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
615 | { | |
616 | // | |
617 | // Find the index of the least significant bit within that limb: | |
618 | // | |
619 | return boost::multiprecision::detail::find_msb(*a.limbs()); | |
620 | } | |
621 | ||
622 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
623 | inline typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value, unsigned>::type | |
624 | eval_msb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) | |
625 | { | |
626 | using default_ops::eval_get_sign; | |
627 | if(eval_get_sign(a) == 0) | |
628 | { | |
629 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
630 | } | |
631 | if(a.sign()) | |
632 | { | |
633 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
634 | } | |
635 | return eval_msb_imp(a); | |
636 | } | |
637 | ||
638 | template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1> | |
639 | inline std::size_t hash_value(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& val) BOOST_NOEXCEPT | |
640 | { | |
641 | std::size_t result = 0; | |
642 | for(unsigned i = 0; i < val.size(); ++i) | |
643 | { | |
644 | boost::hash_combine(result, val.limbs()[i]); | |
645 | } | |
646 | boost::hash_combine(result, val.sign()); | |
647 | return result; | |
648 | } | |
649 | ||
650 | #ifdef BOOST_MSVC | |
651 | #pragma warning(pop) | |
652 | #endif | |
653 | ||
654 | }}} // namespaces | |
655 | ||
656 | #endif |