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