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