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(r.compare(t) > 0)
246 {
247 eval_subtract(r, t);
248 }
249 else
250 {
251 r.swap(t);
252 eval_subtract(r, t);
253 prem = r.limbs();
254 r_neg = !r_neg;
255 }
256 //
257 // First time through we need to strip any leading zero, otherwise
258 // the termination condition goes belly-up:
259 //
260 if(result && first_pass)
261 {
262 first_pass = false;
263 while(pr[result->size() - 1] == 0)
264 result->resize(result->size() - 1, result->size() - 1);
265 }
266 //
267 // Update r_order:
268 //
269 r_order = r.size() - 1;
270 if(r_order < y_order)
271 break;
272 }
273 // Termination condition is really just a check that r > y, but with a common
274 // short-circuit case handled first:
275 while((r_order > y_order) || (r.compare_unsigned(y) >= 0));
276
277 //
278 // We now just have to normalise the result:
279 //
280 if(r_neg && eval_get_sign(r))
281 {
282 // We have one too many in the result:
283 if(result)
284 eval_decrement(*result);
285 if(y.sign())
286 {
287 r.negate();
288 eval_subtract(r, y);
289 }
290 else
291 eval_subtract(r, y, r);
292 }
293
294 BOOST_ASSERT(r.compare_unsigned(y) < 0); // remainder must be less than the divisor or our code has failed
295 }
296
297 template <class CppInt1, class CppInt2>
divide_unsigned_helper(CppInt1 * result,const CppInt2 & x,limb_type y,CppInt1 & r)298 void divide_unsigned_helper(
299 CppInt1* result,
300 const CppInt2& x,
301 limb_type y,
302 CppInt1& r)
303 {
304 if(((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
305 {
306 CppInt2 t(x);
307 divide_unsigned_helper(result, t, y, r);
308 return;
309 }
310
311 if(result == &r)
312 {
313 CppInt1 rem;
314 divide_unsigned_helper(result, x, y, rem);
315 r = rem;
316 return;
317 }
318
319 // As above, but simplified for integer divisor:
320
321 using default_ops::eval_subtract;
322
323 if(y == 0)
324 {
325 BOOST_THROW_EXCEPTION(std::overflow_error("Integer Division by zero."));
326 }
327 //
328 // Find the most significant word of numerator.
329 //
330 limb_type r_order = x.size() - 1;
331
332 //
333 // Set remainder and result to their initial values:
334 //
335 r = x;
336 r.sign(false);
337 typename CppInt1::limb_pointer pr = r.limbs();
338
339 //
340 // check for x < y, try to do this without actually having to
341 // do a full comparison:
342 //
343 if((r_order == 0) && (*pr < y))
344 {
345 if(result)
346 *result = static_cast<limb_type>(0u);
347 return;
348 }
349
350 //
351 // See if we can short-circuit long division, and use basic arithmetic instead:
352 //
353 if(r_order == 0)
354 {
355 if(result)
356 {
357 *result = *pr / y;
358 result->sign(x.sign());
359 }
360 *pr %= y;
361 r.sign(x.sign());
362 return;
363 }
364 else if(r_order == 1)
365 {
366 double_limb_type a;
367 a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[0];
368 if(result)
369 {
370 *result = a / y;
371 result->sign(x.sign());
372 }
373 r = a % y;
374 r.sign(x.sign());
375 return;
376 }
377
378 // This is initialised just to keep the compiler from emitting useless warnings later on:
379 typename CppInt1::limb_pointer pres = typename CppInt1::limb_pointer();
380 if(result)
381 {
382 result->resize(r_order + 1, r_order + 1);
383 pres = result->limbs();
384 if(result->size() > r_order)
385 pres[r_order] = 0; // just in case we don't set the most significant limb below.
386 }
387
388 do
389 {
390 //
391 // Calculate our best guess for how many times y divides into r:
392 //
393 if((pr[r_order] < y) && r_order)
394 {
395 double_limb_type a, b;
396 a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[r_order - 1];
397 b = a % y;
398 r.resize(r.size() - 1, r.size() - 1);
399 --r_order;
400 pr[r_order] = static_cast<limb_type>(b);
401 if(result)
402 pres[r_order] = static_cast<limb_type>(a / y);
403 if(r_order && pr[r_order] == 0)
404 {
405 --r_order; // No remainder, division was exact.
406 r.resize(r.size() - 1, r.size() - 1);
407 if(result)
408 pres[r_order] = static_cast<limb_type>(0u);
409 }
410 }
411 else
412 {
413 if(result)
414 pres[r_order] = pr[r_order] / y;
415 pr[r_order] %= y;
416 if(r_order && pr[r_order] == 0)
417 {
418 --r_order; // No remainder, division was exact.
419 r.resize(r.size() - 1, r.size() - 1);
420 if(result)
421 pres[r_order] = static_cast<limb_type>(0u);
422 }
423 }
424 }
425 // Termination condition is really just a check that r >= y, but with two common
426 // short-circuit cases handled first:
427 while(r_order || (pr[r_order] >= y));
428
429 if(result)
430 {
431 result->normalize();
432 result->sign(x.sign());
433 }
434 r.normalize();
435 r.sign(x.sign());
436
437 BOOST_ASSERT(r.compare(y) < 0); // remainder must be less than the divisor or our code has failed
438 }
439
440 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>
441 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)442 eval_divide(
443 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
444 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
445 const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
446 {
447 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
448 bool s = a.sign() != b.sign();
449 divide_unsigned_helper(&result, a, b, r);
450 result.sign(s);
451 }
452
453 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>
454 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)455 eval_divide(
456 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
457 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
458 limb_type& b)
459 {
460 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
461 bool s = a.sign();
462 divide_unsigned_helper(&result, a, b, r);
463 result.sign(s);
464 }
465
466 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>
467 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)468 eval_divide(
469 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
470 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
471 signed_limb_type& b)
472 {
473 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
474 bool s = a.sign() != (b < 0);
475 divide_unsigned_helper(&result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(b)), r);
476 result.sign(s);
477 }
478
479 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>
480 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)481 eval_divide(
482 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
483 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
484 {
485 // There is no in place divide:
486 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
487 eval_divide(result, a, b);
488 }
489
490 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
491 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)492 eval_divide(
493 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
494 limb_type b)
495 {
496 // There is no in place divide:
497 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
498 eval_divide(result, a, b);
499 }
500
501 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
502 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)503 eval_divide(
504 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
505 signed_limb_type b)
506 {
507 // There is no in place divide:
508 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
509 eval_divide(result, a, b);
510 }
511
512 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>
513 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)514 eval_modulus(
515 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
516 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
517 const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
518 {
519 bool s = a.sign();
520 divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
521 result.sign(s);
522 }
523
524 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>
525 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)526 eval_modulus(
527 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
528 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, limb_type b)
529 {
530 bool s = a.sign();
531 divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
532 result.sign(s);
533 }
534
535 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>
536 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)537 eval_modulus(
538 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
539 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
540 signed_limb_type b)
541 {
542 bool s = a.sign();
543 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);
544 result.sign(s);
545 }
546
547 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>
548 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)549 eval_modulus(
550 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
551 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
552 {
553 // There is no in place divide:
554 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
555 eval_modulus(result, a, b);
556 }
557
558 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
559 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)560 eval_modulus(
561 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
562 limb_type b)
563 {
564 // There is no in place divide:
565 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
566 eval_modulus(result, a, b);
567 }
568
569 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
570 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)571 eval_modulus(
572 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
573 signed_limb_type b)
574 {
575 // There is no in place divide:
576 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
577 eval_modulus(result, a, b);
578 }
579
580 //
581 // Over again for trivial cpp_int's:
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<
585 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
586 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
587 && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
588 || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
589 >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)590 eval_divide(
591 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
592 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
593 {
594 if(!*o.limbs())
595 BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
596 *result.limbs() /= *o.limbs();
597 result.sign(result.sign() != o.sign());
598 }
599
600 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
601 BOOST_MP_FORCEINLINE typename enable_if_c<
602 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
603 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
604 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
605 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
606 >::type
eval_divide(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)607 eval_divide(
608 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
609 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
610 {
611 if(!*o.limbs())
612 BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
613 *result.limbs() /= *o.limbs();
614 }
615
616 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
617 BOOST_MP_FORCEINLINE typename enable_if_c<
618 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
619 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
620 >::type
eval_modulus(cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & result,const cpp_int_backend<MinBits1,MaxBits1,SignType1,Checked1,Allocator1> & o)621 eval_modulus(
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 result.sign(result.sign());
629 }
630
631 }}} // namespaces
632
633 #endif
634