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

source code of boost/libs/multiprecision/include/boost/multiprecision/cpp_int/divide.hpp