Line data Source code
1 : // source:
2 : // https://github.com/983/Num/blob/master/num.hpp
3 : // License:
4 : // This is free and unencumbered software released into the public domain.
5 : //
6 : // Anyone is free to copy, modify, publish, use, compile, sell, or
7 : // distribute this software, either in source code form or as a compiled
8 : // binary, for any purpose, commercial or non-commercial, and by any
9 : // means.
10 : //
11 : // In jurisdictions that recognize copyright laws, the author or authors
12 : // of this software dedicate any and all copyright interest in the
13 : // software to the public domain. We make this dedication for the benefit
14 : // of the public at large and to the detriment of our heirs and
15 : // successors. We intend this dedication to be an overt act of
16 : // relinquishment in perpetuity of all present and future rights to this
17 : // software under copyright law.
18 : //
19 : // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 : // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 : // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22 : // IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 : // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 : // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 : // OTHER DEALINGS IN THE SOFTWARE.
26 : //
27 : // For more information, please refer to <http://unlicense.org>
28 :
29 : #pragma once
30 :
31 : #include <math.h>
32 : #include <stdint.h>
33 : #include <limits.h>
34 :
35 : #include <vector>
36 : #include <algorithm>
37 :
38 :
39 : //#pragma GCC diagnostic push
40 : //#pragma GCC diagnostic ignored "-Weffc++"
41 : //#pragma GCC diagnostic ignored "-Wpermissive"
42 :
43 :
44 : class Num {
45 : public:
46 : typedef uint64_t word;
47 :
48 : std::vector<word> words = {};
49 : bool neg = false;
50 :
51 19200 : static word word_mask(){
52 19200 : return (word)-1;
53 : }
54 :
55 343174 : static size_t word_bits(){
56 343174 : return sizeof(word)*CHAR_BIT;
57 : }
58 :
59 19200 : static word word_half_mask(){
60 19200 : return word_mask() >> word_bits()/2;
61 : }
62 :
63 : static word char_to_word(char c){
64 : switch (c){
65 : case '0': return 0;
66 : case '1': return 1;
67 : case '2': return 2;
68 : case '3': return 3;
69 : case '4': return 4;
70 : case '5': return 5;
71 : case '6': return 6;
72 : case '7': return 7;
73 : case '8': return 8;
74 : case '9': return 9;
75 : case 'a': case 'A': return 10;
76 : case 'b': case 'B': return 11;
77 : case 'c': case 'C': return 12;
78 : case 'd': case 'D': return 13;
79 : case 'e': case 'E': return 14;
80 : case 'f': case 'F': return 15;
81 : case 'g': case 'G': return 16;
82 : case 'h': case 'H': return 17;
83 : case 'i': case 'I': return 18;
84 : case 'j': case 'J': return 19;
85 : case 'k': case 'K': return 20;
86 : case 'l': case 'L': return 21;
87 : case 'm': case 'M': return 22;
88 : case 'n': case 'N': return 23;
89 : case 'o': case 'O': return 24;
90 : case 'p': case 'P': return 25;
91 : case 'q': case 'Q': return 26;
92 : case 'r': case 'R': return 27;
93 : case 's': case 'S': return 28;
94 : case 't': case 'T': return 29;
95 : case 'u': case 'U': return 30;
96 : case 'v': case 'V': return 31;
97 : case 'w': case 'W': return 32;
98 : case 'x': case 'X': return 33;
99 : case 'y': case 'Y': return 34;
100 : case 'z': case 'Z': return 35;
101 : default: return word_mask();
102 : }
103 : }
104 :
105 : static word word_gcd(word a, word b){
106 : while (1){
107 : if (a == 0) return b;
108 : b %= a;
109 : if (b == 0) return a;
110 : a %= b;
111 : }
112 : }
113 :
114 600 : Num(): neg(false){}
115 :
116 900 : Num(size_t n, word w, bool sign = false): words(n, w), neg(sign){}
117 :
118 1500 : Num(const word *a, const word *b, bool sign = false) : words(a, b), neg(sign){}
119 :
120 400 : Num(const Num &a){
121 400 : words = a.words;
122 400 : neg = a.neg;
123 400 : }
124 :
125 700 : Num& operator = (const Num &a){
126 700 : words = a.words;
127 700 : neg = a.neg;
128 700 : return *this;
129 : }
130 :
131 300 : Num(int i): neg(i < 0){
132 300 : for (unsigned u = std::abs(i); u;){
133 0 : push_back(u);
134 : // carefully shift 'u' bit-by-bit because u >>= 32 might be undefined
135 0 : for (size_t j = 0; j < word_bits(); j++) u >>= 1;
136 : }
137 300 : }
138 :
139 : Num(const char *c, word base = 10, char **endptr = NULL): neg(false){
140 : // read sign
141 : if (*c == '-'){
142 : c++;
143 : neg = true;
144 : }
145 : // read digits
146 : for (;*c; c++){
147 : mul_word(base);
148 : word b = char_to_word(*c);
149 : if (b >= base) break;
150 : add_word(b);
151 : }
152 : if (endptr) *endptr = const_cast<char*>(c);
153 : }
154 :
155 45651 : void resize(size_t n){
156 45651 : words.resize(n);
157 45651 : }
158 :
159 1614 : void pop_back(){
160 1614 : words.pop_back();
161 1614 : }
162 :
163 0 : void push_back(word b){
164 0 : words.push_back(b);
165 0 : }
166 :
167 : word& back(){
168 : return words.back();
169 : }
170 :
171 : const word& back() const {
172 : return words.back();
173 : }
174 :
175 590736 : size_t size() const {
176 590736 : return words.size();
177 : }
178 :
179 731094 : word& operator [] (size_t i){
180 731094 : return words[i];
181 : }
182 :
183 231341 : const word& operator [] (size_t i) const {
184 231341 : return words[i];
185 : }
186 :
187 600 : Num& set_neg(bool sign){
188 600 : this->neg = sign;
189 600 : return *this;
190 : }
191 :
192 68095 : Num& truncate(){
193 69709 : while (size() > 0 && words.back() == 0) pop_back();
194 68095 : return *this;
195 : }
196 :
197 424 : size_t bitlength() const {
198 424 : if (size() == 0) return 0;
199 424 : size_t last = size() - 1;
200 424 : while(last > 0 && (*this)[last] == 0) {
201 0 : --last;
202 : }
203 424 : size_t result = word_bitlength((*this)[last]) + last*word_bits();
204 424 : return result;
205 : }
206 :
207 : size_t count_trailing_zeros() const {
208 : for (size_t i = 0; i < size(); i++){
209 : word w = (*this)[i];
210 : if (w) return word_count_trailing_zeros(w) + i*word_bits();
211 : }
212 : return 0;
213 : }
214 :
215 45463 : static int cmp_abs(const Num &a, const Num &b){
216 45463 : size_t na = a.size(), nb = b.size();
217 45463 : if (na != nb){
218 849 : return na < nb ? -1 : +1;
219 : }
220 45082 : for (size_t i = na; i --> 0;){
221 45082 : word wa = a[i], wb = b[i];
222 45082 : if (wa != wb){
223 44614 : return wa < wb ? -1 : +1;
224 : }
225 : }
226 0 : return 0;
227 : }
228 :
229 : static int cmp(const Num &a, const Num &b){
230 : if (a.size() == 0 && b.size() == 0) return 0;
231 : if (!a.neg && !b.neg) return +cmp_abs(a, b);
232 : if ( a.neg && b.neg) return -cmp_abs(a, b);
233 : return a.neg && !b.neg ? -1 : +1;
234 : }
235 :
236 424 : static size_t word_bitlength(word a){
237 845 : for (int i = word_bits() - 1; i >= 0; i--) if ((a >> i) & 1) return i+1;
238 0 : return 0;
239 : }
240 :
241 : static size_t word_count_trailing_zeros(word a){
242 : for (int i = 0; i < (int)word_bits(); i++) if ((a >> i) & 1) return i;
243 : return word_bits();
244 : }
245 :
246 16200 : static word add_carry(word *a, word b){
247 16200 : return (*a += b) < b;
248 : }
249 :
250 226468 : static word sub_carry(word *a, word b){
251 226468 : word tmp = *a;
252 226468 : return (*a = tmp - b) > tmp;
253 : }
254 :
255 6400 : static word word_mul_hi(word a, word b){
256 6400 : size_t n = word_bits()/2;
257 6400 : word a_hi = a >> n;
258 6400 : word a_lo = a & word_half_mask();
259 6400 : word b_hi = b >> n;
260 6400 : word b_lo = b & word_half_mask();
261 6400 : word tmp = ((a_lo*b_lo) >> n) + a_hi*b_lo;
262 6400 : tmp = (tmp >> n) + ((a_lo*b_hi + (tmp & word_half_mask())) >> n);
263 6400 : return tmp + a_hi*b_hi;
264 : }
265 :
266 100 : static Num& add_unsigned_overwrite(Num &a, const Num &b){
267 100 : size_t i, na = a.size(), nb = b.size(), n = std::max(na, nb);
268 100 : a.resize(n);
269 100 : word carry = 0;
270 1800 : for (i = 0; i < nb; i++){
271 1700 : carry = add_carry(&a[i], carry);
272 1700 : carry += add_carry(&a[i], b[i]);
273 : }
274 100 : for (; i < n && carry; i++) carry = add_carry(&a[i], carry);
275 100 : if (carry) a.push_back(carry);
276 200 : return a.truncate();
277 : }
278 :
279 22556 : static Num& sub_unsigned_overwrite(Num &a, const Num &b){
280 : //assert(cmp_abs(a, b) >= 0);
281 22556 : size_t i, na = a.size(), nb = b.size();
282 22556 : word carry = 0;
283 135685 : for (i = 0; i < nb; i++){
284 113129 : carry = sub_carry(&a[i], carry);
285 113129 : carry += sub_carry(&a[i], b[i]);
286 : }
287 22766 : for (; i < na && carry; i++) carry = sub_carry(&a[i], carry);
288 : //assert(!carry);
289 22556 : return a.truncate();
290 : }
291 :
292 100 : static Num mul_long(const Num &a, const Num &b){
293 100 : size_t na = a.size(), nb = b.size(), nc = na + nb + 1;
294 100 : Num c(nc, 0, a.neg ^ b.neg), carries(nc, 0);
295 900 : for (size_t ia = 0; ia < na; ia++){
296 7200 : for (size_t ib = 0; ib < nb; ib++){
297 6400 : size_t i = ia + ib, j = i + 1;
298 : // WARNING: Might overflow if word size is chosen too small
299 6400 : carries[i + 1] += add_carry(&c[i], a[ia] * b[ib]);
300 6400 : carries[j + 1] += add_carry(&c[j], word_mul_hi(a[ia], b[ib]));
301 : }
302 : }
303 200 : return add_unsigned_overwrite(c, carries).truncate();
304 100 : }
305 :
306 0 : static Num mul_karatsuba(const Num &a, const Num &b){
307 0 : size_t na = a.size(), nb = b.size(), n = std::max(na, nb), m2 = n/2 + (n & 1);
308 0 : Num a_parts[2], b_parts[2];
309 0 : split(a, a_parts, 2, m2);
310 0 : split(b, b_parts, 2, m2);
311 0 : m2 *= word_bits();
312 0 : Num z0 = a_parts[0] * b_parts[0];
313 0 : Num z1 = (a_parts[0] + a_parts[1]) * (b_parts[0] + b_parts[1]);
314 0 : Num z2 = a_parts[1] * b_parts[1];
315 0 : Num result = z2;
316 0 : result <<= m2;
317 0 : result += z1 - z2 - z0;
318 0 : result <<= m2;
319 0 : result += z0;
320 0 : return result;
321 0 : }
322 :
323 100 : static Num mul(const Num &a, const Num &b){
324 100 : size_t karatsuba_threshold = 20;
325 100 : if (a.size() > karatsuba_threshold && b.size() > karatsuba_threshold){
326 0 : return mul_karatsuba(a, b);
327 : }
328 100 : return mul_long(a, b);
329 : }
330 :
331 0 : static Num add_signed(const Num &a, bool a_neg, const Num &b, bool b_neg){
332 0 : if (a_neg == b_neg) return add_unsigned(a, b).set_neg(a_neg);
333 0 : if (cmp_abs(a, b) >= 0) return sub_unsigned(a, b).set_neg(a_neg);
334 0 : return sub_unsigned(b, a).set_neg(b_neg);
335 : }
336 :
337 45163 : Num& operator >>= (size_t n_bits){
338 45163 : if (n_bits == 0) return *this;
339 45163 : size_t n_words = n_bits / word_bits();
340 45163 : if (n_words >= size()){
341 0 : resize(0);
342 0 : return *this;
343 : }
344 45163 : n_bits %= word_bits();
345 45163 : if (n_bits == 0){
346 0 : for (size_t i = 0; i < size() - n_words; i++){
347 0 : (*this)[i] = (*this)[i + n_words];
348 : }
349 : }else{
350 45163 : word hi, lo = (*this)[n_words];
351 225420 : for (size_t i = 0; i < size() - n_words - 1; i++){
352 180257 : hi = (*this)[i + n_words + 1];
353 180257 : (*this)[i] = (hi << (word_bits() - n_bits)) | (lo >> n_bits);
354 180257 : lo = hi;
355 : }
356 45163 : (*this)[size() - n_words - 1] = lo >> n_bits;
357 : }
358 45163 : resize(size() - n_words);
359 45163 : return truncate();
360 : }
361 :
362 212 : Num& operator <<= (size_t n_bits){
363 212 : if (n_bits == 0) return *this;
364 176 : size_t n_words = n_bits / word_bits();
365 176 : n_bits %= word_bits();
366 176 : size_t old_size = size();
367 176 : size_t n = old_size + n_words + (n_bits != 0);
368 176 : resize(n);
369 176 : if (n_bits == 0){
370 58 : for (size_t i = n; i --> n_words;){
371 29 : (*this)[i] = (*this)[i - n_words];
372 : }
373 : }else{
374 147 : word lo, hi = 0;
375 826 : for (size_t i = n - 1; i > n_words; i--){
376 679 : lo = (*this)[i - n_words - 1];
377 679 : (*this)[i] = (hi << n_bits) | (lo >> (word_bits() - n_bits));
378 679 : hi = lo;
379 : }
380 147 : (*this)[n_words] = hi << n_bits;
381 : }
382 843 : for (size_t i = 0; i < n_words; i++) (*this)[i] = 0;
383 176 : return truncate();
384 : }
385 :
386 300 : static void div_mod(const Num &numerator, Num denominator, Num "ient, Num &remainder){
387 300 : quotient = 0;
388 300 : remainder = numerator;
389 300 : if (cmp_abs(remainder, denominator) >= 0){
390 212 : int n = numerator.bitlength() - denominator.bitlength();
391 212 : denominator <<= n;
392 45375 : for (; n >= 0; n--){
393 45163 : if (cmp_abs(remainder, denominator) >= 0){
394 22556 : sub_unsigned_overwrite(remainder, denominator);
395 22556 : quotient.set_bit(n);
396 : }
397 45163 : denominator >>= 1;
398 : }
399 : }
400 300 : quotient.set_neg(numerator.neg ^ denominator.neg);
401 300 : remainder.set_neg(numerator.neg);
402 300 : }
403 :
404 : static void div_mod_half_word(const Num &numerator, word denominator, Num "ient, word &remainder){
405 : remainder = 0;
406 : Num dst(numerator.size(), 0);
407 :
408 : for (size_t i = numerator.size(); i --> 0;){
409 : word dst_word = 0;
410 : word src_word = numerator[i];
411 : word parts[2];
412 : parts[0] = src_word >> word_bits()/2;
413 : parts[1] = src_word & word_half_mask();
414 :
415 : for (size_t j = 0; j < 2; j++){
416 : remainder <<= word_bits()/2;
417 : remainder |= parts[j];
418 :
419 : word div_word = remainder / denominator;
420 : word mod_word = remainder % denominator;
421 : remainder = mod_word;
422 :
423 : dst_word <<= word_bits()/2;
424 : dst_word |= div_word;
425 : }
426 :
427 : dst[i] = dst_word;
428 : }
429 :
430 : quotient = dst.truncate().set_neg(numerator.neg);
431 : }
432 :
433 0 : static void split(const Num &a, Num *parts, size_t n_parts, size_t n){
434 0 : size_t i = 0;
435 0 : for (size_t k = 0; k < n_parts; k++){
436 0 : Num &part = parts[k];
437 0 : part.resize(n);
438 0 : for (size_t j = 0; j < n && i < a.size(); j++) part[j] = a[i++];
439 0 : part = part.truncate();
440 : }
441 0 : }
442 :
443 200 : static Num div(const Num &numerator, const Num& denominator){
444 200 : Num quotient, remainder;
445 200 : div_mod(numerator, denominator, quotient, remainder);
446 400 : return quotient;
447 200 : }
448 :
449 100 : static Num mod(const Num &numerator, const Num& denominator){
450 100 : Num quotient, remainder;
451 100 : div_mod(numerator, denominator, quotient, remainder);
452 200 : return remainder;
453 100 : }
454 :
455 0 : static Num add_unsigned(const Num &a, const Num &b){
456 0 : Num result(a);
457 0 : return add_unsigned_overwrite(result, b);
458 0 : }
459 :
460 0 : static Num sub_unsigned(const Num &a, const Num &b){
461 0 : Num result(a);
462 0 : return sub_unsigned_overwrite(result, b);
463 0 : }
464 :
465 0 : static Num add(const Num &a, const Num &b){
466 0 : Num result = add_signed(a, a.neg, b, b.neg);
467 0 : return result;
468 : }
469 :
470 0 : static Num sub(const Num &a, const Num &b){
471 0 : Num result = add_signed(a, a.neg, b, !b.neg);
472 0 : return result;
473 : }
474 :
475 : static Num gcd(const Num &a0, const Num &b0){
476 :
477 : if (a0.size() == 1 && b0.size() == 1){
478 : return Num(1, word_gcd(a0[0], b0[0]));
479 : }
480 :
481 : Num a(a0), b(b0);
482 : a.neg = b.neg = false;
483 :
484 : if (a.size() == 0) return b0;
485 : if (b.size() == 0) return a0;
486 :
487 : size_t n = a.count_trailing_zeros();
488 : size_t m = b.count_trailing_zeros();
489 : if (n > m) {
490 : std::swap(n, m);
491 : a.words.swap(b.words);
492 : }
493 :
494 : a >>= n;
495 : b >>= n;
496 :
497 : do {
498 : b >>= b.count_trailing_zeros();
499 : if (cmp_abs(a, b) > 0) a.words.swap(b.words);
500 : sub_unsigned_overwrite(b, a);
501 : } while (b.size() > 0);
502 :
503 : a <<= n;
504 :
505 : return a;
506 : }
507 :
508 : typedef void (*random_func)(uint8_t *bytes, size_t n_bytes);
509 :
510 : static Num random_bits(size_t n_bits, random_func func){
511 : if (n_bits == 0) return 0;
512 : size_t partial_bits = n_bits % word_bits();
513 : size_t n_words = n_bits / word_bits() + (partial_bits > 0);
514 : size_t n_bytes = n_words*sizeof(word);
515 : Num result(n_words, 0);
516 : uint8_t *bytes = (uint8_t*)&result[0];
517 : func(bytes, n_bytes);
518 : if (partial_bits){
519 : size_t too_many_bits = word_bits() - partial_bits;
520 : result.back() >>= too_many_bits;
521 : }
522 : return result;
523 : }
524 :
525 : static Num random_inclusive(const Num &inclusive, random_func func){
526 : size_t n_bits = inclusive.bitlength();
527 : while (true){
528 : Num result = random_bits(n_bits, func);
529 : if (result <= inclusive) return result;
530 : }
531 : }
532 :
533 : static Num random_exclusive(const Num &exclusive, random_func func){
534 : size_t n_bits = exclusive.bitlength();
535 : while (true){
536 : Num result = random_bits(n_bits, func);
537 : if (result < exclusive) return result;
538 : }
539 : }
540 :
541 : static Num random_second_exclusive(const Num &inclusive_min_val, const Num &exclusive_max_val, random_func func){
542 : return inclusive_min_val + random_exclusive(exclusive_max_val - inclusive_min_val, func);
543 : }
544 :
545 : static Num random_both_inclusive(const Num &inclusive_min_val, const Num &inclusive_max_val, random_func func){
546 : return inclusive_min_val + random_inclusive(inclusive_max_val - inclusive_min_val, func);
547 : }
548 :
549 22556 : Num& set_bit(size_t i){
550 22556 : size_t i_word = i / word_bits();
551 22556 : size_t i_bit = i % word_bits();
552 22556 : if (size() <= i_word) resize(i_word + 1);
553 22556 : (*this)[i_word] |= ((word)1) << i_bit;
554 22556 : return *this;
555 : }
556 :
557 : word get_bit(size_t i) const {
558 : size_t i_word = i / word_bits();
559 : size_t i_bit = i % word_bits();
560 : if (i_word >= size()) return 0;
561 : return ((*this)[i_word] >> i_bit) & 1;
562 : }
563 :
564 : void clr_bit(size_t i){
565 : size_t i_word = i / word_bits();
566 : size_t i_bit = i % word_bits();
567 : if (i_word >= size()) return;
568 : word mask = 1;
569 : mask <<= i_bit;
570 : (*this)[i_word] &= ~mask;
571 : }
572 :
573 : Num& mul_word(word b){
574 : word carry = 0;
575 : for (size_t i = 0; i < size(); i++){
576 : word a = (*this)[i];
577 : word tmp = a * b;
578 : carry = add_carry(&tmp, carry);
579 : carry += word_mul_hi(a, b);
580 : (*this)[i] = tmp;
581 : }
582 : if (carry) push_back(carry);
583 : return truncate();
584 : }
585 :
586 : Num& add_word(word carry, size_t i0 = 0){
587 : if (i0 >= size()) resize(i0 + 1);
588 : for (size_t i = i0; i < size() && carry; i++){
589 : carry = add_carry(&(*this)[i], carry);
590 : }
591 : if (carry) push_back(carry);
592 : return truncate();
593 : }
594 :
595 : void print(
596 : std::vector<char> &text,
597 : word base = 10,
598 : const char *alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
599 : ) const {
600 : if (size() == 0){
601 : text.push_back('0');
602 : }else{
603 : Num tmp(*this);
604 : while (tmp.size() > 0){
605 : word remainder;
606 : div_mod_half_word(tmp, base, tmp, remainder);
607 : text.push_back(alphabet[remainder]);
608 : }
609 : if (neg) text.push_back('-');
610 : std::reverse(text.begin(), text.end());
611 : }
612 : text.push_back('\0');
613 : }
614 :
615 : double to_double() const {
616 : if (size() == 0) return 0.0;
617 : double d = 0.0, base = ::pow(2.0, word_bits());
618 : for (size_t i = size(); i --> 0;) d = d * base + (*this)[i];
619 : return neg ? -d : d;
620 : }
621 :
622 : bool can_convert_to_int(int *result){
623 : if (*this < Num(INT_MIN) || *this > Num(INT_MAX)) return false;
624 :
625 : unsigned temp = 0;
626 :
627 : for (size_t i = words.size(); i --> 0;){
628 : temp <<= word_bits();
629 : temp += (*this)[i];
630 : }
631 :
632 : *result = neg ? -temp : temp;
633 :
634 : return true;
635 : }
636 :
637 : Num pow(size_t exponent) const {
638 : Num result(1), p(*this);
639 : for (; exponent; exponent >>= 1){
640 : if (exponent & 1){
641 : result = result * p;
642 : exponent--;
643 : }
644 : p = p*p;
645 : }
646 : return result;
647 : }
648 :
649 : Num mod_pow(Num exponent, const Num &modulus) const {
650 : Num result(1), base = (*this) % modulus;
651 : for (; exponent.size() > 0; exponent >>= 1){
652 : if (exponent.get_bit(0)){
653 : result = (result * base) % modulus;
654 : }
655 : base = (base * base) % modulus;
656 : }
657 : return result;
658 : }
659 :
660 : Num sqrt() const {
661 : Num n = *this;
662 : int bit = bitlength();
663 : if (bit & 1) bit ^= 1;
664 : Num result = 0;
665 : for (; bit >= 0; bit -= 2){
666 : Num tmp = result;
667 : tmp.set_bit(bit);
668 : if (n >= tmp){
669 : n -= tmp;
670 : result.set_bit(bit + 1);
671 : }
672 : result >>= 1;
673 : }
674 : return result;
675 : }
676 :
677 : Num& operator ++(){
678 : add_word(1);
679 : return *this;
680 : }
681 :
682 0 : Num& operator += (const Num &b){ return *this = add(*this, b); }
683 : Num& operator -= (const Num &b){ return *this = sub(*this, b); }
684 : Num& operator *= (const Num &b){ return *this = mul(*this, b); }
685 : Num& operator /= (const Num &b){ return *this = div(*this, b); }
686 : Num& operator %= (const Num &b){ return *this = mod(*this, b); }
687 :
688 : bool operator == (const Num &b) const { return cmp(*this, b) == 0; }
689 : bool operator != (const Num &b) const { return cmp(*this, b) != 0; }
690 : bool operator <= (const Num &b) const { return cmp(*this, b) <= 0; }
691 : bool operator >= (const Num &b) const { return cmp(*this, b) >= 0; }
692 : bool operator < (const Num &b) const { return cmp(*this, b) < 0; }
693 : bool operator > (const Num &b) const { return cmp(*this, b) > 0; }
694 :
695 0 : Num operator + (const Num &b) const { return add(*this, b); }
696 0 : Num operator - (const Num &b) const { return sub(*this, b); }
697 100 : Num operator * (const Num &b) const { return mul(*this, b); }
698 200 : Num operator / (const Num &b) const { return div(*this, b); }
699 100 : Num operator % (const Num &b) const { return mod(*this, b); }
700 : Num operator - ( ) const { return Num(*this).set_neg(!neg); }
701 :
702 : Num operator >> (size_t n_bits) const { return Num(*this) >>= n_bits; }
703 : Num operator << (size_t n_bits) const { return Num(*this) <<= n_bits; }
704 : };
705 :
706 : //#pragma GCC diagnostic pop
707 : // vim: ts=4 sw=4 et
|
