00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef BIGNUM_H_
00014 #define BIGNUM_H_
00015
00016 #include <gmp.h>
00017 #include <iostream>
00018 #include <assert.h>
00019 #include <stdlib.h>
00020 using namespace std;
00021
00022
00023 union data_type
00024 {
00025 long int d;
00026 mpz_t i;
00027 };
00028
00029
00030 class bignum
00031 {
00032 public:
00033 data_type data;
00034 bool infinite;
00035
00036 inline bignum()
00037 {
00038 data.d = 0;
00039 infinite = false;
00040 }
00041
00042 inline bignum(const bignum & other)
00043 {
00044 infinite = other.infinite;
00045 if(!infinite)
00046 {
00047 data.d = other.data.d;
00048 return;
00049 }
00050 mpz_init_set(data.i, other.data.i);
00051 }
00052
00053 inline bignum(long int i)
00054 {
00055 data.d = i;
00056 infinite = false;
00057 }
00058
00059 inline bignum(string &s)
00060 {
00061 infinite = true;
00062 mpz_init_set_str(data.i, s.c_str(), 10);
00063 }
00064
00065 inline bignum(const mpz_t & i)
00066 {
00067 infinite = true;
00068 mpz_init_set(data.i, i);
00069 }
00070
00071 inline ~bignum()
00072 {
00073 if(!infinite) return;
00074 mpz_clear(data.i);
00075 }
00076
00077 inline const bignum & operator=(const bignum & other)
00078 {
00079 if(!infinite && !other.infinite)
00080 {
00081 data.d = other.data.d;
00082 infinite = false;
00083 return *this;
00084 }
00085 if(!infinite && other.infinite)
00086 {
00087 mpz_init_set(data.i, other.data.i);
00088 infinite = true;
00089 return *this;
00090 }
00091 if(infinite && !other.infinite)
00092 {
00093 mpz_set_si(data.i, other.data.d);
00094 return *this;
00095 }
00096
00097 mpz_set(data.i, other.data.i);
00098 return *this;
00099
00100 }
00101
00102 inline bignum abs()
00103 {
00104 if(!infinite) return bignum(labs(data.d));
00105 bignum res;
00106 res.set_infinite();
00107 mpz_abs(res.data.i, data.i);
00108 return res;
00109 }
00110
00111 inline bool fits_long_int()
00112 {
00113 if(!infinite) return true;
00114 return mpz_fits_slong_p(data.i);
00115 }
00116
00117 inline long int to_int()
00118 {
00119 if(!infinite) return data.d;
00120 return mpz_get_si(data.i);
00121 }
00122 inline double to_double()
00123 {
00124 if(!infinite)
00125 return ((double)data.d);
00126 return mpz_get_d(data.i);
00127 }
00128
00129 inline double divide(bignum & other)
00130 {
00131 if(!infinite && !other.infinite){
00132 return ((double)data.d)/((double)other.data.d);
00133 }
00134 if(infinite && !other.infinite){
00135 double my_d = mpz_get_d(data.i);
00136 return my_d/((double)other.data.d);
00137 }
00138 if(!infinite && other.infinite){
00139 double other_d = mpz_get_d(other.data.i);
00140 return ((double)data.d)/other_d;
00141 }
00142 double my_d = mpz_get_d(data.i);
00143 double other_d = mpz_get_d(other.data.i);
00144 return my_d/other_d;
00145 }
00146
00147 inline bool divisible(bignum & other)
00148 {
00149 if(!infinite && !other.infinite)
00150 return data.d % other.data.d == 0;
00151
00152 if(infinite && !other.infinite){
00153 return mpz_divisible_ui_p(data.i, (unsigned long int)other.data.d);
00154 }
00155 if(!infinite && other.infinite){
00156 mpz_t me;
00157 mpz_init_set_si(me, data.d);
00158 bool res = mpz_divisible_p(me, other.data.i);
00159 mpz_clear(me);
00160 return res;
00161 }
00162 return mpz_divisible_p(data.i, other.data.i);
00163 }
00164
00165 inline bignum compute_gcd(const bignum & other)
00166 {
00167 if(!infinite && !other.infinite){
00168 return compute_int_gcd(data.d, other.data.d);
00169 }
00170 if(infinite && !other.infinite){
00171 mpz_t temp;
00172 mpz_init_set_si(temp, other.data.d);
00173 mpz_t gcd;
00174 mpz_init(gcd);
00175 mpz_gcd(gcd, temp, data.i);
00176 bignum b(gcd);
00177 mpz_clear(gcd);
00178 mpz_clear(temp);
00179 return b;
00180 }
00181 if(!infinite && other.infinite){
00182 mpz_t temp;
00183 mpz_init_set_si(temp, data.d);
00184 mpz_t gcd;
00185 mpz_init(gcd);
00186 mpz_gcd(gcd, temp, other.data.i);
00187 bignum b(gcd);
00188 mpz_clear(gcd);
00189 mpz_clear(temp);
00190 return b;
00191 }
00192 mpz_t gcd;
00193 mpz_init(gcd);
00194 mpz_gcd(gcd, data.i, other.data.i);
00195 bignum b(gcd);
00196 mpz_clear(gcd);
00197 return b;
00198
00199
00200 }
00201 inline bignum compute_lcm(const bignum & other)
00202 {
00203 bignum gcd = this->compute_gcd(other);
00204 bignum res = *this * other;
00205 res/=gcd;
00206 return res;
00207 }
00208
00209
00210
00211
00212 inline bignum compute_xgcd(bignum & other, bignum & p, bignum & q)
00213 {
00214 mpz_t a, b;
00215 if(infinite) mpz_init_set(a, data.i);
00216 else mpz_init_set_si(a, data.d);
00217
00218 if(other.infinite) mpz_init_set(b, other.data.i);
00219 else mpz_init_set_si(b, other.data.d);
00220
00221 mpz_t _p, _q, gcd;
00222 mpz_init(_p);
00223 mpz_init(_q);
00224 mpz_init(gcd);
00225 mpz_gcdext (gcd,_p, _q, a, b);
00226 bignum res_gcd;
00227
00228 bignum pp(_p);
00229 bignum qq(_q);
00230
00231 if(mpz_fits_slong_p(gcd))
00232 res_gcd = mpz_get_si(gcd);
00233 else res_gcd = gcd;
00234
00235 if(mpz_fits_slong_p(_p))
00236 p = mpz_get_si(_p);
00237 else p = _p;
00238
00239 if(mpz_fits_slong_p(_q))
00240 q = mpz_get_si(_q);
00241 else q = _q;
00242
00243 mpz_clear(a);
00244 mpz_clear(b);
00245 mpz_clear(_p);
00246 mpz_clear(_q);
00247 mpz_clear(gcd);
00248 return res_gcd;
00249 }
00250
00251 inline void operator*=(bignum& o1)
00252 {
00253 if(is_infinite() || o1.is_infinite())
00254 {
00255 make_infinite();
00256 o1.make_infinite();
00257 mpz_mul(data.i, data.i, o1.data.i);
00258 return;
00259 }
00260
00261 if(m_overflow(data.d, o1.data.d)) {
00262
00263 o1.make_infinite();
00264 make_infinite();
00265 mpz_mul(data.i, data.i, o1.data.i);
00266 return;
00267 }
00268
00269
00270 data.d*=o1.data.d;
00271 }
00272
00273
00274 inline bignum operator*(bignum o1)
00275 {
00276 bignum res;
00277 if(is_infinite() || o1.is_infinite())
00278 {
00279 res.set_infinite();
00280 make_infinite();
00281 o1.make_infinite();
00282 mpz_mul(res.data.i, data.i, o1.data.i);
00283 return res;
00284 }
00285
00286 if(m_overflow(data.d, o1.data.d)) {
00287 res.set_infinite();
00288 o1.make_infinite();
00289 make_infinite();
00290 mpz_mul(res.data.i, data.i, o1.data.i);
00291 return res;
00292 }
00293
00294
00295 res.data.d = data.d*o1.data.d;
00296 return res;
00297 }
00298
00299 inline bignum operator%(bignum o1)
00300 {
00301 bignum res;
00302 if(is_infinite() && o1.is_infinite())
00303 {
00304 res.set_infinite();
00305 mpz_tdiv_r(res.data.i, data.i, o1.data.i);
00306 if(mpz_fits_slong_p(res.data.i))
00307 {
00308 long int val = mpz_get_si(res.data.i);
00309 mpz_clear(res.data.i);
00310 res.infinite = false;
00311 res.data.d = val;
00312 }
00313 return res;
00314 }
00315 if(is_infinite() && !o1.is_infinite())
00316 {
00317 res.set_infinite();
00318 mpz_t other;
00319 mpz_init_set_si(other, o1.data.d);
00320 mpz_tdiv_r(res.data.i, data.i, other);
00321 mpz_clear(other);
00322 if(mpz_fits_slong_p(res.data.i))
00323 {
00324 long int val = mpz_get_si(res.data.i);
00325 mpz_clear(res.data.i);
00326 res.infinite = false;
00327 res.data.d = val;
00328 }
00329 return res;
00330 }
00331 if(!is_infinite() && o1.is_infinite())
00332 {
00333 res.set_infinite();
00334 mpz_t me;
00335 mpz_init_set_si(me, data.d);
00336 mpz_tdiv_r(res.data.i, me , o1.data.i);
00337 mpz_clear(me);
00338 if(mpz_fits_slong_p(res.data.i))
00339 {
00340 long int val = mpz_get_si(res.data.i);
00341 mpz_clear(res.data.i);
00342 res.infinite = false;
00343 res.data.d = val;
00344 }
00345 return res;
00346 }
00347 res.data.d = data.d%o1.data.d;
00348 return res;
00349 }
00350
00351 inline bignum operator/(bignum o1)
00352 {
00353 bignum res;
00354 if(is_infinite() && o1.is_infinite())
00355 {
00356 mpz_t temp;
00357 mpz_init(temp);
00358 mpz_tdiv_q(temp, data.i, o1.data.i);
00359 if(mpz_fits_slong_p(temp)){
00360 res.infinite = false;
00361 long int val = mpz_get_si(temp);
00362 mpz_clear(temp);
00363 res.data.d = val;
00364 return res;
00365 }
00366 res.set_infinite();
00367 mpz_set(res.data.i, temp);
00368 mpz_clear(temp);
00369 return res;
00370 }
00371 if(is_infinite() && !o1.is_infinite())
00372 {
00373 mpz_t temp;
00374 mpz_init(temp);
00375 mpz_t temp2;
00376 mpz_init_set_si(temp2, o1.data.d);
00377 mpz_tdiv_q(temp, data.i, temp2);
00378 if(mpz_fits_slong_p(temp)){
00379 res.infinite = false;
00380 long int val = mpz_get_si(temp);
00381 mpz_clear(temp);
00382 mpz_clear(temp2);
00383 res.data.d = val;
00384 return res;
00385 }
00386 res.set_infinite();
00387 mpz_set(res.data.i, temp);
00388 mpz_clear(temp);
00389 mpz_clear(temp2);
00390 return res;
00391 }
00392 if(!is_infinite() && o1.is_infinite())
00393 {
00394 mpz_t temp;
00395 mpz_init(temp);
00396 mpz_t temp2;
00397 mpz_init_set_si(temp2, data.d);
00398 mpz_tdiv_q(temp, temp2, o1.data.i);
00399 if(mpz_fits_slong_p(temp)){
00400 res.infinite = false;
00401 long int val = mpz_get_si(temp);
00402 mpz_clear(temp);
00403 mpz_clear(temp2);
00404 res.data.d = val;
00405 return res;
00406 }
00407 res.set_infinite();
00408 mpz_set(res.data.i, temp);
00409 mpz_clear(temp);
00410 mpz_clear(temp2);
00411 return res;
00412 }
00413 res.data.d = data.d/o1.data.d;
00414 return res;
00415 }
00416
00417
00418 inline bignum divexact(bignum & o1)
00419 {
00420 bignum res;
00421 if(is_infinite() && o1.is_infinite())
00422 {
00423 mpz_t temp;
00424 mpz_init(temp);
00425 mpz_divexact(temp, data.i, o1.data.i);
00426 if(mpz_fits_slong_p(temp)){
00427 res.infinite = false;
00428 long int val = mpz_get_si(temp);
00429 mpz_clear(temp);
00430 res.data.d = val;
00431 return res;
00432 }
00433 res.set_infinite();
00434 mpz_set(res.data.i, temp);
00435 mpz_clear(temp);
00436 return res;
00437 }
00438 if(is_infinite() && !o1.is_infinite())
00439 {
00440 mpz_t temp;
00441 mpz_init(temp);
00442 mpz_t temp2;
00443 mpz_init_set_si(temp2, o1.data.d);
00444 mpz_divexact(temp, data.i, temp2);
00445 if(mpz_fits_slong_p(temp)){
00446 res.infinite = false;
00447 long int val = mpz_get_si(temp);
00448 mpz_clear(temp);
00449 mpz_clear(temp2);
00450 res.data.d = val;
00451 return res;
00452 }
00453 res.set_infinite();
00454 mpz_set(res.data.i, temp);
00455 mpz_clear(temp);
00456 mpz_clear(temp2);
00457 return res;
00458 }
00459 if(!is_infinite() && o1.is_infinite())
00460 {
00461 mpz_t temp;
00462 mpz_init(temp);
00463 mpz_t temp2;
00464 mpz_init_set_si(temp2, data.d);
00465 mpz_divexact(temp, temp2, o1.data.i);
00466 if(mpz_fits_slong_p(temp)){
00467 res.infinite = false;
00468 long int val = mpz_get_si(temp);
00469 mpz_clear(temp);
00470 mpz_clear(temp2);
00471 res.data.d = val;
00472 return res;
00473 }
00474 res.set_infinite();
00475 mpz_set(res.data.i, temp);
00476 mpz_clear(temp);
00477 mpz_clear(temp2);
00478 return res;
00479 }
00480 res.data.d = data.d/o1.data.d;
00481 return res;
00482 }
00483
00484
00485 inline void operator/=(bignum& o1)
00486 {
00487 if(is_infinite() || o1.is_infinite())
00488 {
00489 make_infinite();
00490 o1.make_infinite();
00491 mpz_tdiv_q(data.i, data.i, o1.data.i);
00492 return;
00493 }
00494
00495
00496 data.d/=o1.data.d;
00497 }
00498
00499 inline void operator+=(bignum o1)
00500 {
00501
00502 if(is_infinite() || o1.is_infinite())
00503 {
00504 make_infinite();
00505 o1.make_infinite();
00506 mpz_add(data.i, data.i, o1.data.i);
00507 return;
00508 }
00509 if(a_overflow(data.d, o1.data.d)) {
00510 make_infinite();
00511 o1.make_infinite();
00512 mpz_add(data.i, data.i, o1.data.i);
00513 return;
00514 }
00515
00516
00517 data.d+=o1.data.d;
00518 }
00519
00520 inline bignum operator+(bignum o1)
00521 {
00522 bignum res;
00523 if(is_infinite() || o1.is_infinite())
00524 {
00525 res.set_infinite();
00526 make_infinite();
00527 o1.make_infinite();
00528 mpz_add(res.data.i, data.i, o1.data.i);
00529 return res;
00530 }
00531
00532 if(a_overflow(data.d, o1.data.d)) {
00533 res.set_infinite();
00534 o1.make_infinite();
00535 make_infinite();
00536 mpz_add(res.data.i, data.i, o1.data.i);
00537 return res;
00538 }
00539
00540
00541 res.data.d = data.d+o1.data.d;
00542 return res;
00543 }
00544
00545
00546
00547
00548 inline bignum operator-(bignum o1)
00549 {
00550 bignum res;
00551 if(is_infinite() || o1.is_infinite())
00552 {
00553 res.set_infinite();
00554 make_infinite();
00555 o1.make_infinite();
00556 mpz_sub(res.data.i, data.i, o1.data.i);
00557 return res;
00558
00559 }
00560
00561 res.data.d = data.d-o1.data.d;
00562 return res;
00563 }
00564
00565
00566 inline bignum operator-()
00567 {
00568 bignum res;
00569 if(is_infinite())
00570 {
00571 res.set_infinite();
00572 mpz_neg(res.data.i, data.i);
00573 return res;
00574
00575 }
00576
00577 res.data.d = -data.d;
00578 return res;
00579 }
00580
00581 inline void operator-=(bignum o1)
00582 {
00583 if(is_infinite() || o1.is_infinite())
00584 {
00585 make_infinite();
00586 o1.make_infinite();
00587 mpz_sub(data.i, data.i, o1.data.i);
00588 return;
00589
00590 }
00591
00592 data.d-=o1.data.d;
00593 }
00594
00595 inline bool operator!=(const bignum other)
00596 {
00597 return !(*this == other);
00598 }
00599
00600 inline bool operator!=(long int other)
00601 {
00602 return !(*this == other);
00603 }
00604
00605 inline bool operator==(const bignum& other)
00606 {
00607 if(!is_infinite() && !other.is_infinite()) {
00608 return data.d == other.data.d;
00609 }
00610 if(is_infinite() && !other.is_infinite()) {
00611 return mpz_cmp_si(data.i, other.data.d)==0;
00612 }
00613 if(!is_infinite() && other.is_infinite()) {
00614 return mpz_cmp_si(other.data.i, data.d)==0;
00615 }
00616 return mpz_cmp(data.i, other.data.i) == 0;
00617 }
00618
00619 inline bool operator==(long int i)
00620 {
00621 if(!is_infinite()) {
00622 return data.d == i;
00623 }
00624 return mpz_cmp_si(data.i, i)==0;
00625 }
00626
00627 inline bool operator<(const bignum& other) const
00628 {
00629 if(!is_infinite() && !other.is_infinite()) {
00630 return data.d < other.data.d;
00631 }
00632 if(is_infinite() && !other.is_infinite()) {
00633 return mpz_cmp_si(data.i, other.data.d)<0;
00634 }
00635 if(!is_infinite() && other.is_infinite()) {
00636 return mpz_cmp_si(other.data.i, data.d)>0;
00637 }
00638 return mpz_cmp(data.i, other.data.i) < 0;
00639 }
00640
00641 inline bool operator<(long int i)
00642 {
00643 if(!is_infinite()) {
00644 return data.d < i;
00645 }
00646 return mpz_cmp_si(data.i, i)<0;
00647 }
00648
00649 inline bool operator<=(const bignum& other)
00650 {
00651 if(!is_infinite() && !other.is_infinite()) {
00652 return data.d <= other.data.d;
00653 }
00654 if(is_infinite() && !other.is_infinite()) {
00655 return mpz_cmp_si(data.i, other.data.d)<=0;
00656 }
00657 if(!is_infinite() && other.is_infinite()) {
00658 return mpz_cmp_si(other.data.i, data.d)>=0;
00659 }
00660 return mpz_cmp(data.i, other.data.i) <= 0;
00661 }
00662 inline bool operator<=(long int i)
00663 {
00664 if(!is_infinite()) {
00665 return data.d <= i;
00666 }
00667 return mpz_cmp_si(data.i, i)<=0;
00668 }
00669
00670 inline bool operator>(const bignum& other)
00671 {
00672 if(!is_infinite() && !other.is_infinite()) {
00673 return data.d > other.data.d;
00674 }
00675 if(is_infinite() && !other.is_infinite()) {
00676 return mpz_cmp_si(data.i, other.data.d)>0;
00677 }
00678 if(!is_infinite() && other.is_infinite()) {
00679 return mpz_cmp_si(other.data.i, data.d)<0;
00680 }
00681 return mpz_cmp(data.i, other.data.i) > 0;
00682 }
00683
00684 inline bool operator>(long int i)
00685 {
00686 if(!is_infinite()) {
00687 return data.d > i;
00688 }
00689 return mpz_cmp_si(data.i, i)>0;
00690 }
00691
00692 inline bool operator>=(const bignum& other)
00693 {
00694 if(!is_infinite() && !other.is_infinite()) {
00695 return data.d >= other.data.d;
00696 }
00697 if(is_infinite() && !other.is_infinite()) {
00698 return mpz_cmp_si(data.i, other.data.d)>=0;
00699 }
00700 if(!is_infinite() && other.is_infinite()) {
00701 return mpz_cmp_si(other.data.i, data.d)<=0;
00702 }
00703 return mpz_cmp(data.i, other.data.i) >= 0;
00704 }
00705
00706 inline bool operator>=(long int i)
00707 {
00708 if(!is_infinite()) {
00709 return data.d >= i;
00710 }
00711 return mpz_cmp_si(data.i, i)>=0;
00712 }
00713
00714 string to_string()
00715 {
00716 if(!is_infinite()) {
00717 char temp[100];
00718 sprintf(temp, "%ld", data.d);
00719 return string(temp);
00720 }
00721 char* res = mpz_get_str(NULL, 10, data.i);
00722 string s(res);
00723 free(res);
00724 return s;
00725 }
00726
00727
00728
00729 friend ostream& operator <<(ostream &os,const bignum &obj);
00730
00731
00732
00733 static inline bool m_overflow(long int c, long int e)
00734 {
00735 int ci = c;
00736 int ei = e;
00737 return c != ((long int)ci) || e != ((long int)ei);
00738 }
00739
00740 static inline bool a_overflow(long int a, long int b)
00741 {
00742 long int res = a + b;
00743 if(b>=0){
00744 if(res<a)
00745 return true;
00746 }
00747 else if(res>a)
00748 return true;
00749 return false;
00750 }
00751
00752 static inline long int compute_int_gcd(long int _a, long int _b)
00753 {
00754 long int a = labs(_a);
00755 long int b = labs(_b);
00756
00757 long int t;
00758 while(b!=0){
00759 t = a;
00760 a = b;
00761 b = t % b;
00762 }
00763 return a;
00764 }
00765 private:
00766
00767 inline void set_normal()
00768 {
00769 infinite = false;
00770 }
00771 inline bool is_infinite() const
00772 {
00773 return infinite;
00774 }
00775
00776 inline void set_infinite()
00777 {
00778 if(infinite) return;
00779 mpz_init(data.i);
00780 infinite = true;
00781 }
00782
00783 inline void make_infinite()
00784 {
00785 if(is_infinite()) return;
00786 long int val = data.d;
00787 mpz_init_set_si(data.i, val);
00788 infinite = true;
00789 }
00790
00791
00792 };
00793
00794 ostream& operator <<(ostream &os,const bignum &_obj);
00795
00796
00797
00798 #endif
