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_DIV_HPP
9 #define BOOST_MP_CPP_INT_DIV_HPP
10
11 namespace boost{ namespace multiprecision{ namespace backends{
12
13 template <class CppInt1, class CppInt2, class CppInt3>
divide_unsigned_helper(CppInt1 * result,const CppInt2 & x,const CppInt3 & y,CppInt1 & r)14 void divide_unsigned_helper(
15 CppInt1* result,
16 const CppInt2& x,
17 const CppInt3& y,
18 CppInt1& r)
19 {
20 if(((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
21 {
22 CppInt2 t(x);
23 divide_unsigned_helper(result, t, y, r);
24 return;
25 }
26 if(((void*)result == (void*)&y) || ((void*)&r == (void*)&y))
27 {
28 CppInt3 t(y);
29 divide_unsigned_helper(result, x, t, r);
30 return;
31 }
32
33 /*
34 Very simple, fairly braindead long division.
35 Start by setting the remainder equal to x, and the
36 result equal to 0. Then in each loop we calculate our
37 "best guess" for how many times y divides into r,
38 add our guess to the result, and subtract guess*y
39 from the remainder r. One wrinkle is that the remainder
40 may go negative, in which case we subtract the current guess
41 from the result rather than adding. The value of the guess
42 is determined by dividing the most-significant-limb of the
43 current remainder by the most-significant-limb of y.
44
45 Note that there are more efficient algorithms than this
46 available, in particular see Knuth Vol 2. However for small
47 numbers of limbs this generally outperforms the alternatives
48 and avoids the normalisation step which would require extra storage.
49 */
50
51
52 using default_ops::eval_subtract;
53
54 if(result == &r)
55 {
56 CppInt1 rem;
57 divide_unsigned_helper(result, x, y, rem);
58 r = rem;
59 return;
60 }
61
62 //
63 // Find the most significant words of numerator and denominator.
64 //
65 limb_type y_order = y.size() - 1;
66
67 if(y_order == 0)
68 {
69 //
70 // Only a single non-zero limb in the denominator, in this case
71 // we can use a specialized divide-by-single-limb routine which is
72 // much faster. This also handles division by zero:
73 //
74 divide_unsigned_helper(result, x, y.limbs()[y_order], r);
75 return;
76 }
77
78 typename CppInt2::const_limb_pointer px = x.limbs();
79 typename CppInt3::const_limb_pointer py = y.limbs();
80
81 limb_type r_order = x.size() - 1;
82 if((r_order == 0) && (*px == 0))
83 {
84 // x is zero, so is the result:
85 r = x;
86 if(result)
87 *result = x;
88 return;
89 }
90
91 r = x;
92 r.sign(false);
93 if(result)
94 *result = static_cast<limb_type>(0u);
95 //
96 // Check if the remainder is already less than the divisor, if so
97 // we already have the result. Note we try and avoid a full compare
98 // if we can:
99 //
100 if(r_order <= y_order)
101 {
102 if((r_order < y_order) || (r.compare_unsigned(y) < 0))
103 {
104 return;
105 }
106 }
107
108 CppInt1 t;
109 bool r_neg = false;
110
111 //
112 // See if we can short-circuit long division, and use basic arithmetic instead:
113 //
114 if(r_order == 0)
115 {
116 if(result)
117 {
118 *result = px[0] / py[0];
119 }
120 r = px[0] % py[0];
121 return;
122 }
123 else if(r_order == 1)
124 {
125 double_limb_type a, b;
126 a = (static_cast<double_limb_type>(px[1]) << CppInt1::limb_bits) | px[0];
127 b = y_order ?
128 (static_cast<double_limb_type>(py[1]) << CppInt1::limb_bits) | py[0]
129 : py[0];
130 if(result)
131 {
132 *result = a / b;
133 }
134 r = a % b;
135 return;
136 }
137 //
138 // prepare result:
139 //
140 if(result)
141 result->resize(1 + r_order - y_order, 1 + r_order - y_order);
142 typename CppInt1::const_limb_pointer prem = r.limbs();
143 // This is initialised just to keep the compiler from emitting useless warnings later on:
144 typename CppInt1::limb_pointer pr
145 = typename CppInt1::limb_pointer();
146 if(result)
147 {
148 pr = result->limbs();
149 for(unsigned i = 1; i < 1 + r_order - y_order; ++i)
150 pr[i] = 0;
151 }
152 bool first_pass = true;
153
154 do
155 {
156 //
157 // Calculate our best guess for how many times y divides into r:
158 //
159 limb_type guess;
160 if((prem[r_order] <= py[y_order]) && (r_order > 0))
161 {
162 double_limb_type a, b, v;
163 a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
164 b = py[y_order];
165 v = a / b;
166 if(v > CppInt1::max_limb_value)
167 guess = 1;
168 else
169 {
170 guess = static_cast<limb_type>(v);
171 --r_order;
172 }
173 }
174 else if(r_order == 0)
175 {
176 guess = prem[0] / py[y_order];
177 }
178 else
179 {
180 double_limb_type a, b, v;
181 a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
182 b = (y_order > 0) ? (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits) | py[y_order - 1] : (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits);
183 v = a / b;
184 guess = static_cast<limb_type>(v);
185 }
186 BOOST_ASSERT(guess); // If the guess ever gets to zero we go on forever....
187 //
188 // Update result:
189 //
190 limb_type shift = r_order - y_order;
191 if(result)
192 {
193 if(r_neg)
194 {
195 if(pr[shift] > guess)
196 pr[shift] -= guess;
197 else
198 {
199 t.resize(shift + 1, shift + 1);
200 t.limbs()[shift] = guess;
201 for(unsigned i = 0; i < shift; ++i)
202 t.limbs()[i] = 0;
203 eval_subtract(*result, t);
204 }
205 }
206 else if(CppInt1::max_limb_value - pr[shift] > guess)
207 pr[shift] += guess;
208 else
209 {
210 t.resize(shift + 1, shift + 1);
211 t.limbs()[shift] = guess;
212 for(unsigned i = 0; i < shift; ++i)
213 t.limbs()[i] = 0;
214 eval_add(*result, t);
215 }
216 }
217 //
218 // Calculate guess * y, we use a fused mutiply-shift O(N) for this
219 // rather than a full O(N^2) multiply:
220 //
221 double_limb_type carry = 0;
222 t.resize(y.size() + shift + 1, y.size() + shift);
223 bool truncated_t = !CppInt1::variable && (t.size() != y.size() + shift + 1);
224 typename CppInt1::limb_pointer pt = t.limbs();
225 for(unsigned i = 0; i < shift; ++i)
226 pt[i] = 0;
227 for(unsigned i = 0; i < y.size(); ++i)
228 {
229 carry += static_cast<double_limb_type>(py[i]) * static_cast<double_limb_type>(guess);
230 pt[i + shift] = static_cast<limb_type>(carry);
231 carry >>= CppInt1::limb_bits;
232 }
233 if(carry && !truncated_t)
234 {
235 pt[t.size() - 1] = static_cast<limb_type>(carry);
236 }
237 else if(!truncated_t)
238 {
239 t.resize(t.size() - 1, t.size() - 1);
240 }
241 //
242 // Update r in a way that won't actually produce a negative result
243 // in case the argument types are unsigned:
244 //
245 if(truncated_t && carry)
246 {
247 // We need to calculate 2^n + t - r
248 // where n is the number of bits in this type.
249 // Simplest way is to get 2^n - r by complementing
250 // r, then add t to it. Note that we can't call eval_complement
251 // in case this is a signed checked type:
252 for(unsigned i = 0; i <= r_order; ++i)
253 r.limbs()[i] = ~prem[i];
254 r.normalize();
255 eval_increment(r);
256 eval_add(r, t);
257 r_neg = !r_neg;
258 }
259 else if(r.compare(t) > 0)
260 {
261 eval_subtract(r, t);
262 }
263 else
264 {
265 r.swap(t);
266 eval_subtract(r, t);
267 prem = r.limbs();
268 r_neg = !r_neg;
269 }
270 //
271 // First time through we need to strip any leading zero, otherwise
272 // the termination condition goes belly-up:
273 //
274 if(result && first_pass)
275 {
276 first_pass = false;
277 while(pr[result->size() - 1] == 0)
278 result->resize(result->size() - 1, result->size() - 1);
279 }
280 //
281 // Update r_order:
282 //
283 r_order = r.size() - 1;
284 if(r_order < y_order)
285 break;
286 }
287 // Termination condition is really just a check that r > y, but with a common
288 // short-circuit case handled first:
289 while((r_order > y_order) || (r.compare_unsigned(y) >= 0));
290
291 //
292 // We now just have to normalise the result:
293 //
294 if(r_neg && eval_get_sign(r))
295 {
296 // We have one too many in the result:
297 if(result)
298 eval_decrement(*result);
299 if(y.sign())
300 {
301 r.negate();
302 eval_subtract(r, y);
303 }
304 else
305 eval_subtract(r, y, r);
306 }
307
308 BOOST_ASSERT(r.compare_unsigned(y) < 0); // remainder must be less than the divisor or our code has failed
309 }
310
311 template <class CppInt1, class CppInt2>
divide_unsigned_helper(CppInt1 * result,const CppInt2 & x,limb_type y,CppInt1 & r)312 void divide_unsigned_helper(
313 CppInt1* result,
314 const CppInt2& x,
315 limb_type y,
316 CppInt1& r)
317 {
318 if(((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
319 {
320 CppInt2 t(x);
321 divide_unsigned_helper(result, t, y, r);
322 return;
323 }
324
325 if(result == &r)
326 {
327 CppInt1 rem;
328 divide_unsigned_helper(result, x, y, rem);
329 r = rem;
330 return;
331 }
332
333 // As above, but simplified for integer divisor:
334
335 using default_ops::eval_subtract;
336
337 if(y == 0)
338 {
339 BOOST_THROW_EXCEPTION(std::overflow_error("Integer Division by zero."));
340 }
341 //
342 // Find the most significant word of numerator.
343 //
344 limb_type r_order = x.size() - 1;
345
346 //
347 // Set remainder and result to their initial values:
348 //
349 r = x;
350 r.sign(false);
351 typename CppInt1::limb_pointer pr = r.limbs();
352
353 //
354 // check for x < y, try to do this without actually having to
355 // do a full comparison:
356 //
357 if((r_order == 0) && (*pr < y))
358 {
359 if(result)
360 *result = static_cast<limb_type>(0u);
361 return;
362 }
363
364 //
365 // See if we can short-circuit long division, and use basic arithmetic instead:
366 //
367 if(r_order == 0)
368 {
369 if(result)
370 {
371 *result = *pr / y;
372 result->sign(x.sign());
373 }
374 *pr %= y;
375 r.sign(x.sign());
376 return;
377 }
378 else if(r_order == 1)
379 {
380 double_limb_type a;
381 a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[0];
382 if(result)
383 {
384 *result = a / y;
385 result->sign(x.sign());
386 }
387 r = a % y;
388 r.sign(x.sign());
389 return;
390 }
391
392 // This is initialised just to keep the compiler from emitting useless warnings later on:
393 typename CppInt1::limb_pointer pres = typename CppInt1::limb_pointer();
394 if(result)
395 {
396 result->resize(r_order + 1, r_order + 1);
397 pres = result->limbs();
398 if(result->size() > r_order)
399 pres[r_order] = 0; // just in case we don't set the most significant limb below.
400 }
401
402 do
403 {
404 //
405 // Calculate our best guess for how many times y divides into r:
406 //
407 if((pr[r_order] < y) && r_order)
408 {
409 double_limb_type a, b;
410 a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[r_order - 1];
411 b = a % y;
412 r.resize(r.size() - 1, r.size() - 1);
413 --r_order;
414 pr[r_order] = static_cast<limb_type>(b);
415 if(result)
416 pres[r_order] = static_cast<limb_type>(a / y);
417 if(r_order && pr[r_order] == 0)
418 {
419 --r_order; // No remainder, division was exact.
420 r.resize(r.size() - 1, r.size() - 1);
421 if(result)
422 pres[r_order] = static_cast<limb_type>(0u);
423 }
424 }
425 else
426 {
427 if(result)
428 pres[r_order] = pr[r_order] / y;
429 pr[r_order] %= y;
430 if(r_order && pr[r_order] == 0)
431 {
432 --r_order; // No remainder, division was exact.
433 r.resize(r.size() - 1, r.size() - 1);
434 if(result)
435 pres[r_order] = static_cast<limb_type>(0u);
436 }
437 }
438 }
439 // Termination condition is really just a check that r >= y, but with two common
440 // short-circuit cases handled first:
441 while(r_order || (pr[r_order] >= y));
442
443 if(result)
444 {
445 result->normalize();
446 result->sign(x.sign());
447 }
448 r.normalize();
449 r.sign(x.sign());
450
451 BOOST_ASSERT(r.compare(y) < 0); // remainder must be less than the divisor or our code has failed
452 }
453
454 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, unsigned MinBits3, unsigned MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
455 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,const cpp_int_backend<MinBits3,MaxBits3,SignType3,Checked3,Allocator3> & b)456 eval_divide(
457 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
458 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
459 const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
460 {
461 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
462 bool s = a.sign() != b.sign();
463 divide_unsigned_helper(&result, a, b, r);
464 result.sign(s);
465 }
466
467 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
468 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,limb_type & b)469 eval_divide(
470 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
471 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
472 limb_type& b)
473 {
474 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
475 bool s = a.sign();
476 divide_unsigned_helper(&result, a, b, r);
477 result.sign(s);
478 }
479
480 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
481 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,signed_limb_type & b)482 eval_divide(
483 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
484 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
485 signed_limb_type& b)
486 {
487 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
488 bool s = a.sign() != (b < 0);
489 divide_unsigned_helper(&result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(b)), r);
490 result.sign(s);
491 }
492
493 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
494 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & b)495 eval_divide(
496 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
497 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
498 {
499 // There is no in place divide:
500 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
501 eval_divide(result, a, b);
502 }
503
504 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
505 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,limb_type b)506 eval_divide(
507 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
508 limb_type b)
509 {
510 // There is no in place divide:
511 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
512 eval_divide(result, a, b);
513 }
514
515 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
516 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,signed_limb_type b)517 eval_divide(
518 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
519 signed_limb_type b)
520 {
521 // There is no in place divide:
522 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
523 eval_divide(result, a, b);
524 }
525
526 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, unsigned MinBits3, unsigned MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
527 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,const cpp_int_backend<MinBits3,MaxBits3,SignType3,Checked3,Allocator3> & b)528 eval_modulus(
529 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
530 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
531 const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
532 {
533 bool s = a.sign();
534 divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
535 result.sign(s);
536 }
537
538 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
539 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,limb_type b)540 eval_modulus(
541 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
542 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, limb_type b)
543 {
544 bool s = a.sign();
545 divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
546 result.sign(s);
547 }
548
549 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
550 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & a,signed_limb_type b)551 eval_modulus(
552 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
553 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
554 signed_limb_type b)
555 {
556 bool s = a.sign();
557 divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(b)), result);
558 result.sign(s);
559 }
560
561 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
562 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits2,MaxBits2,SignType2,Checked2,Allocator2> & b)563 eval_modulus(
564 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
565 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
566 {
567 // There is no in place divide:
568 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
569 eval_modulus(result, a, b);
570 }
571
572 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
573 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,limb_type b)574 eval_modulus(
575 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
576 limb_type b)
577 {
578 // There is no in place divide:
579 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
580 eval_modulus(result, a, b);
581 }
582
583 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
584 BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,signed_limb_type b)585 eval_modulus(
586 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
587 signed_limb_type b)
588 {
589 // There is no in place divide:
590 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
591 eval_modulus(result, a, b);
592 }
593
594 //
595 // Over again for trivial cpp_int's:
596 //
597 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
598 BOOST_MP_FORCEINLINE typename enable_if_c<
599 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
600 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
601 && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
602 || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
603 >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)604 eval_divide(
605 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
606 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
607 {
608 if(!*o.limbs())
609 BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
610 *result.limbs() /= *o.limbs();
611 result.sign(result.sign() != o.sign());
612 }
613
614 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
615 BOOST_MP_FORCEINLINE typename enable_if_c<
616 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
617 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
618 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
619 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
620 >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)621 eval_divide(
622 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
623 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
624 {
625 if(!*o.limbs())
626 BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
627 *result.limbs() /= *o.limbs();
628 }
629
630 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
631 BOOST_MP_FORCEINLINE typename enable_if_c<
632 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
633 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
634 >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)635 eval_modulus(
636 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
637 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
638 {
639 if(!*o.limbs())
640 BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
641 *result.limbs() %= *o.limbs();
642 result.sign(result.sign());
643 }
644
645 }}} // namespaces
646
647 #endif
648