InfInt.h (31070B)
1 // http://stackoverflow.com/a/6321977/414272 2 #ifdef __GNUC__ 3 // Avoid tons of warnings with root code 4 #pragma GCC system_header 5 #endif 6 /* 7 * InfInt - Arbitrary-Precision Integer Arithmetic Library 8 * Copyright (C) 2013 Sercan Tutar 9 * 10 * This Source Code Form is subject to the terms of the Mozilla Public 11 * License, v. 2.0. If a copy of the MPL was not distributed with this 12 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 13 * 14 * 15 * USAGE: 16 * It is pretty straight forward to use the library. Just create an instance of 17 * InfInt class and start using it. 18 * 19 * Useful methods: 20 * intSqrt: integer square root operation 21 * digitAt: returns digit at index 22 * numberOfDigits: returns number of digits 23 * size: returns size in bytes 24 * toString: converts it to a string 25 * 26 * There are also conversion methods which allow conversion to primitive types: 27 * toInt, toLong, toLongLong, toUnsignedInt, toUnsignedLong, toUnsignedLongLong. 28 * 29 * You may define INFINT_USE_EXCEPTIONS and library methods will start raising 30 * InfIntException in case of error instead of writing error messages using 31 * std::cerr. 32 * 33 * See ReadMe.txt for more info. 34 * 35 * 36 * No overflows, happy programmers! 37 * 38 */ 39 40 #ifndef INFINT_H_ 41 #define INFINT_H_ 42 43 #include <iostream> 44 #include <vector> 45 #include <sstream> 46 #include <iomanip> 47 48 //#include <limits.h> 49 //#include <stdlib.h> 50 51 #ifdef _WIN32 52 #define LONG_LONG_MIN LLONG_MIN 53 #define LONG_LONG_MAX LLONG_MAX 54 #define ULONG_LONG_MAX ULLONG_MAX 55 #endif 56 57 #ifdef INFINT_USE_EXCEPTIONS 58 #include <exception> 59 #endif 60 61 typedef int ELEM_TYPE; 62 typedef long long PRODUCT_TYPE; 63 static const ELEM_TYPE BASE = 1000000000; 64 static const ELEM_TYPE UPPER_BOUND = 999999999; 65 static const ELEM_TYPE DIGIT_COUNT = 9; 66 static const int powersOfTen[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 }; 67 68 #ifdef INFINT_USE_EXCEPTIONS 69 class InfIntException: public std::exception 70 { 71 public: 72 InfIntException(const std::string& txt) throw (); 73 ~InfIntException() throw (); 74 const char* what() const throw (); 75 private: 76 std::string txt; 77 }; 78 79 InfIntException::InfIntException(const std::string& txt) throw () : 80 std::exception(), txt(txt) 81 { 82 } 83 84 InfIntException::~InfIntException() throw () 85 { 86 } 87 88 const char* InfIntException::what() const throw () 89 { 90 return txt.c_str(); 91 } 92 #endif 93 94 inline static div_t my_div(int num, int denom) 95 { 96 div_t result; 97 result.quot = num / denom; 98 result.rem = num - denom * result.quot; 99 return result; 100 } 101 102 inline static ldiv_t my_ldiv(long num, long denom) 103 { 104 ldiv_t result; 105 result.quot = num / denom; 106 result.rem = num - denom * result.quot; 107 return result; 108 } 109 110 inline static lldiv_t my_lldiv(long long num, long long denom) 111 { 112 lldiv_t result; 113 result.quot = num / denom; 114 result.rem = num - denom * result.quot; 115 return result; 116 } 117 118 class InfInt 119 { 120 friend std::ostream& operator<<(std::ostream &s, const InfInt &n); 121 friend std::istream& operator>>(std::istream &s, InfInt &val); 122 123 public: 124 /* constructors */ 125 InfInt(); 126 InfInt(const char* c); 127 InfInt(const std::string& s); 128 InfInt(int l); 129 InfInt(long l); 130 InfInt(long long l); 131 InfInt(unsigned int l); 132 InfInt(unsigned long l); 133 InfInt(unsigned long long l); 134 InfInt(const InfInt& l); 135 136 /* assignment operators */ 137 const InfInt& operator=(const char* c); 138 const InfInt& operator=(const std::string& s); 139 const InfInt& operator=(int l); 140 const InfInt& operator=(long l); 141 const InfInt& operator=(long long l); 142 const InfInt& operator=(unsigned int l); 143 const InfInt& operator=(unsigned long l); 144 const InfInt& operator=(unsigned long long l); 145 const InfInt& operator=(const InfInt& l); 146 147 /* unary increment/decrement operators */ 148 const InfInt& operator++(); 149 const InfInt& operator--(); 150 InfInt operator++(int); 151 InfInt operator--(int); 152 153 /* operational assignments */ 154 const InfInt& operator+=(const InfInt& rhs); 155 const InfInt& operator-=(const InfInt& rhs); 156 const InfInt& operator*=(const InfInt& rhs); 157 const InfInt& operator/=(const InfInt& rhs); // throw 158 const InfInt& operator%=(const InfInt& rhs); // throw 159 const InfInt& operator*=(ELEM_TYPE rhs); 160 161 /* operations */ 162 InfInt operator-() const; 163 InfInt operator+(const InfInt& rhs) const; 164 InfInt operator-(const InfInt& rhs) const; 165 InfInt operator*(const InfInt& rhs) const; 166 InfInt operator/(const InfInt& rhs) const; // throw 167 InfInt operator%(const InfInt& rhs) const; // throw 168 InfInt operator*(ELEM_TYPE rhs) const; 169 170 /* relational operations */ 171 bool operator==(const InfInt& rhs) const; 172 bool operator!=(const InfInt& rhs) const; 173 bool operator<(const InfInt& rhs) const; 174 bool operator<=(const InfInt& rhs) const; 175 bool operator>(const InfInt& rhs) const; 176 bool operator>=(const InfInt& rhs) const; 177 178 /* integer square root */ 179 InfInt intSqrt() const; // throw 180 181 /* digit operations */ 182 char digitAt(size_t i) const; // throw 183 size_t numberOfDigits() const; 184 185 /* size in bytes */ 186 size_t size() const; 187 188 /* string conversion */ 189 std::string toString() const; 190 191 /* conversion to primitive types */ 192 int toInt() const; // throw 193 long toLong() const; // throw 194 long long toLongLong() const; // throw 195 unsigned int toUnsignedInt() const; // throw 196 unsigned long toUnsignedLong() const; // throw 197 unsigned long long toUnsignedLongLong() const; // throw 198 199 private: 200 static ELEM_TYPE dInR(const InfInt& R, const InfInt& D); 201 static void multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val); 202 203 void correct(bool justCheckLeadingZeros = false, bool hasValidSign = false); 204 void fromString(const std::string& s); 205 void optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const; 206 void truncateToBase(); 207 bool equalizeSigns(); 208 void removeLeadingZeros(); 209 210 std::vector<ELEM_TYPE> val; // number with base FACTOR 211 bool pos; // true if number is positive 212 }; 213 214 inline InfInt::InfInt() : pos(true) 215 { 216 //PROFINY_SCOPE 217 val.push_back((ELEM_TYPE) 0); 218 } 219 220 inline InfInt::InfInt(const char* c) 221 { 222 //PROFINY_SCOPE 223 fromString(c); 224 } 225 226 inline InfInt::InfInt(const std::string& s) 227 { 228 //PROFINY_SCOPE 229 fromString(s); 230 } 231 232 inline InfInt::InfInt(int l) : pos(l >= 0) 233 { 234 //PROFINY_SCOPE 235 bool subtractOne = false; 236 if (l == INT_MIN) 237 { 238 subtractOne = true; 239 ++l; 240 } 241 242 if (!pos) 243 { 244 l = -l; 245 } 246 do 247 { 248 div_t dt = my_div(l, BASE); 249 val.push_back((ELEM_TYPE) dt.rem); 250 l = dt.quot; 251 } while (l > 0); 252 253 if (subtractOne) 254 { 255 --*this; 256 } 257 } 258 259 inline InfInt::InfInt(long l) : pos(l >= 0) 260 { 261 //PROFINY_SCOPE 262 bool subtractOne = false; 263 if (l == LONG_MIN) 264 { 265 subtractOne = true; 266 ++l; 267 } 268 269 if (!pos) 270 { 271 l = -l; 272 } 273 do 274 { 275 ldiv_t dt = my_ldiv(l, BASE); 276 val.push_back((ELEM_TYPE) dt.rem); 277 l = dt.quot; 278 } while (l > 0); 279 280 if (subtractOne) 281 { 282 --*this; 283 } 284 } 285 286 inline InfInt::InfInt(long long l) : pos(l >= 0) 287 { 288 //PROFINY_SCOPE 289 bool subtractOne = false; 290 if (l == LONG_LONG_MIN) 291 { 292 subtractOne = true; 293 ++l; 294 } 295 296 if (!pos) 297 { 298 l = -l; 299 } 300 do 301 { 302 lldiv_t dt = my_lldiv(l, BASE); 303 val.push_back((ELEM_TYPE) dt.rem); 304 l = dt.quot; 305 } while (l > 0); 306 307 if (subtractOne) 308 { 309 --*this; 310 } 311 } 312 313 inline InfInt::InfInt(unsigned int l) : pos(true) 314 { 315 //PROFINY_SCOPE 316 do 317 { 318 val.push_back((ELEM_TYPE) (l % BASE)); 319 l = l / BASE; 320 } while (l > 0); 321 } 322 323 inline InfInt::InfInt(unsigned long l) : pos(true) 324 { 325 //PROFINY_SCOPE 326 do 327 { 328 val.push_back((ELEM_TYPE) (l % BASE)); 329 l = l / BASE; 330 } while (l > 0); 331 } 332 333 inline InfInt::InfInt(unsigned long long l) : pos(true) 334 { 335 //PROFINY_SCOPE 336 do 337 { 338 val.push_back((ELEM_TYPE) (l % BASE)); 339 l = l / BASE; 340 } while (l > 0); 341 } 342 343 inline InfInt::InfInt(const InfInt& l) : pos(l.pos), val(l.val) 344 { 345 //PROFINY_SCOPE 346 } 347 348 inline const InfInt& InfInt::operator=(const char* c) 349 { 350 //PROFINY_SCOPE 351 fromString(c); 352 return *this; 353 } 354 355 inline const InfInt& InfInt::operator=(const std::string& s) 356 { 357 //PROFINY_SCOPE 358 fromString(s); 359 return *this; 360 } 361 362 inline const InfInt& InfInt::operator=(int l) 363 { 364 //PROFINY_SCOPE 365 bool subtractOne = false; 366 if (l == INT_MIN) 367 { 368 subtractOne = true; 369 ++l; 370 } 371 372 pos = l >= 0; 373 val.clear(); 374 if (!pos) 375 { 376 l = -l; 377 } 378 do 379 { 380 div_t dt = my_div(l, BASE); 381 val.push_back((ELEM_TYPE) dt.rem); 382 l = dt.quot; 383 } while (l > 0); 384 385 return subtractOne ? --*this : *this; 386 } 387 388 inline const InfInt& InfInt::operator=(long l) 389 { 390 //PROFINY_SCOPE 391 bool subtractOne = false; 392 if (l == LONG_MIN) 393 { 394 subtractOne = true; 395 ++l; 396 } 397 398 pos = l >= 0; 399 val.clear(); 400 if (!pos) 401 { 402 l = -l; 403 } 404 do 405 { 406 ldiv_t dt = my_ldiv(l, BASE); 407 val.push_back((ELEM_TYPE) dt.rem); 408 l = dt.quot; 409 } while (l > 0); 410 411 return subtractOne ? --*this : *this; 412 } 413 414 inline const InfInt& InfInt::operator=(long long l) 415 { 416 //PROFINY_SCOPE 417 bool subtractOne = false; 418 if (l == LONG_LONG_MIN) 419 { 420 subtractOne = true; 421 ++l; 422 } 423 424 pos = l >= 0; 425 val.clear(); 426 if (!pos) 427 { 428 l = -l; 429 } 430 do 431 { 432 lldiv_t dt = my_lldiv(l, BASE); 433 val.push_back((ELEM_TYPE) dt.rem); 434 l = dt.quot; 435 } while (l > 0); 436 437 return subtractOne ? --*this : *this; 438 } 439 440 inline const InfInt& InfInt::operator=(unsigned int l) 441 { 442 //PROFINY_SCOPE 443 pos = true; 444 val.clear(); 445 do 446 { 447 val.push_back((ELEM_TYPE) (l % BASE)); 448 l = l / BASE; 449 } while (l > 0); 450 return *this; 451 } 452 453 inline const InfInt& InfInt::operator=(unsigned long l) 454 { 455 //PROFINY_SCOPE 456 pos = true; 457 val.clear(); 458 do 459 { 460 val.push_back((ELEM_TYPE) (l % BASE)); 461 l = l / BASE; 462 } while (l > 0); 463 return *this; 464 } 465 466 inline const InfInt& InfInt::operator=(unsigned long long l) 467 { 468 //PROFINY_SCOPE 469 pos = true; 470 val.clear(); 471 do 472 { 473 val.push_back((ELEM_TYPE) (l % BASE)); 474 l = l / BASE; 475 } while (l > 0); 476 return *this; 477 } 478 479 const InfInt& InfInt::operator=(const InfInt& l) 480 { 481 //PROFINY_SCOPE 482 pos = l.pos; 483 val = l.val; 484 return *this; 485 } 486 487 inline const InfInt& InfInt::operator++() 488 { 489 //PROFINY_SCOPE 490 val[0] += (pos ? 1 : -1); 491 this->correct(false, true); 492 return *this; 493 } 494 495 inline const InfInt& InfInt::operator--() 496 { 497 //PROFINY_SCOPE 498 val[0] -= (pos ? 1 : -1); 499 this->correct(false, true); 500 return *this; 501 } 502 503 inline InfInt InfInt::operator++(int) 504 { 505 //PROFINY_SCOPE 506 InfInt result = *this; 507 val[0] += (pos ? 1 : -1); 508 this->correct(false, true); 509 return result; 510 } 511 512 inline InfInt InfInt::operator--(int) 513 { 514 //PROFINY_SCOPE 515 InfInt result = *this; 516 val[0] -= (pos ? 1 : -1); 517 this->correct(false, true); 518 return result; 519 } 520 521 inline const InfInt& InfInt::operator+=(const InfInt& rhs) 522 { 523 //PROFINY_SCOPE 524 if (rhs.val.size() > val.size()) 525 { 526 val.resize(rhs.val.size(), 0); 527 } 528 for (size_t i = 0; i < val.size(); ++i) 529 { 530 val[i] = (pos ? val[i] : -val[i]) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0); 531 } 532 correct(); 533 return *this; 534 } 535 536 inline const InfInt& InfInt::operator-=(const InfInt& rhs) 537 { 538 //PROFINY_SCOPE 539 if (rhs.val.size() > val.size()) 540 { 541 val.resize(rhs.val.size(), 0); 542 } 543 for (size_t i = 0; i < val.size(); ++i) 544 { 545 val[i] = (pos ? val[i] : -val[i]) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0); 546 } 547 correct(); 548 return *this; 549 } 550 551 inline const InfInt& InfInt::operator*=(const InfInt& rhs) 552 { 553 //PROFINY_SCOPE 554 // TODO: optimize (do not use operator*) 555 *this = *this * rhs; 556 return *this; 557 } 558 559 inline const InfInt& InfInt::operator/=(const InfInt& rhs) 560 { 561 //PROFINY_SCOPE 562 if (rhs == 0) 563 { 564 #ifdef INFINT_USE_EXCEPTIONS 565 throw InfIntException("division by zero"); 566 #else 567 std::cerr << "Division by zero!" << std::endl; 568 return *this; 569 #endif 570 } 571 InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this); 572 bool oldpos = pos; 573 std::fill(val.begin(), val.end(), 0); 574 for (int i = (int) N.val.size() - 1; i >= 0; --i) 575 { 576 R.val.insert(R.val.begin(), N.val[i]); 577 R.correct(true); 578 ELEM_TYPE cnt = dInR(R, D); 579 R -= D * cnt; 580 val[i] += cnt; 581 } 582 correct(); 583 pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == rhs.pos); 584 return *this; 585 } 586 587 inline const InfInt& InfInt::operator%=(const InfInt& rhs) 588 { 589 //PROFINY_SCOPE 590 if (rhs == 0) 591 { 592 #ifdef INFINT_USE_EXCEPTIONS 593 throw InfIntException("division by zero"); 594 #else 595 std::cerr << "Division by zero!" << std::endl; 596 return *this; 597 #endif 598 } 599 InfInt D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this); 600 bool oldpos = pos; 601 val.clear(); 602 for (int i = (int) N.val.size() - 1; i >= 0; --i) 603 { 604 val.insert(val.begin(), N.val[i]); 605 correct(true); 606 *this -= D * dInR(*this, D); 607 } 608 correct(); 609 pos = (val.size() == 1 && val[0] == 0) ? true : oldpos; 610 return *this; 611 } 612 613 inline const InfInt& InfInt::operator*=(ELEM_TYPE rhs) 614 { 615 //PROFINY_SCOPE 616 ELEM_TYPE factor = rhs < 0 ? -rhs : rhs; 617 bool oldpos = pos; 618 multiplyByDigit(factor, val); 619 correct(); 620 pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == (rhs >= 0)); 621 return *this; 622 } 623 624 inline InfInt InfInt::operator-() const 625 { 626 //PROFINY_SCOPE 627 InfInt result = *this; 628 result.pos = !pos; 629 return result; 630 } 631 632 inline InfInt InfInt::operator+(const InfInt& rhs) const 633 { 634 //PROFINY_SCOPE 635 InfInt result; 636 result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0); 637 for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i) 638 { 639 result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0); 640 } 641 result.correct(); 642 return result; 643 } 644 645 inline InfInt InfInt::operator-(const InfInt& rhs) const 646 { 647 //PROFINY_SCOPE 648 InfInt result; 649 result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0); 650 for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i) 651 { 652 result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0); 653 } 654 result.correct(); 655 return result; 656 } 657 658 inline InfInt InfInt::operator*(const InfInt& rhs) const 659 { 660 //PROFINY_SCOPE 661 InfInt result; 662 result.val.resize(val.size() + rhs.val.size(), 0); 663 PRODUCT_TYPE carry = 0; 664 size_t digit = 0; 665 for (;; ++digit) 666 { 667 lldiv_t dt = my_lldiv(carry, BASE); 668 carry = dt.quot; 669 result.val[digit] = (ELEM_TYPE) dt.rem; 670 671 bool found = false; 672 for (size_t i = digit < rhs.val.size() ? 0 : digit - rhs.val.size() + 1; i < val.size() && i <= digit; ++i) 673 { 674 PRODUCT_TYPE pval = result.val[digit] + val[i] * (PRODUCT_TYPE) rhs.val[digit - i]; 675 if (pval >= BASE || pval <= -BASE) 676 { 677 lldiv_t dt = my_lldiv(pval, BASE); 678 carry += dt.quot; 679 pval = dt.rem; 680 } 681 result.val[digit] = (ELEM_TYPE) pval; 682 found = true; 683 } 684 if (!found) 685 { 686 break; 687 } 688 } 689 for (; carry > 0; ++digit) 690 { 691 lldiv_t dt = my_lldiv(carry, BASE); 692 result.val[digit] = (ELEM_TYPE) dt.rem; 693 carry = dt.quot; 694 } 695 result.correct(); 696 result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == rhs.pos); 697 return result; 698 } 699 700 inline InfInt InfInt::operator/(const InfInt& rhs) const 701 { 702 //PROFINY_SCOPE 703 if (rhs == 0) 704 { 705 #ifdef INFINT_USE_EXCEPTIONS 706 throw InfIntException("division by zero"); 707 #else 708 std::cerr << "Division by zero!" << std::endl; 709 return 0; 710 #endif 711 } 712 InfInt Q, R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this); 713 Q.val.resize(N.val.size(), 0); 714 for (int i = (int) N.val.size() - 1; i >= 0; --i) 715 { 716 R.val.insert(R.val.begin(), N.val[i]); 717 R.correct(true); 718 ELEM_TYPE cnt = dInR(R, D); 719 R -= D * cnt; 720 Q.val[i] += cnt; 721 } 722 Q.correct(); 723 Q.pos = (Q.val.size() == 1 && Q.val[0] == 0) ? true : (pos == rhs.pos); 724 return Q; 725 } 726 727 inline InfInt InfInt::operator%(const InfInt& rhs) const 728 { 729 //PROFINY_SCOPE 730 if (rhs == 0) 731 { 732 #ifdef INFINT_USE_EXCEPTIONS 733 throw InfIntException("division by zero"); 734 #else 735 std::cerr << "Division by zero!" << std::endl; 736 return 0; 737 #endif 738 } 739 InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this); 740 for (int i = (int) N.val.size() - 1; i >= 0; --i) 741 { 742 R.val.insert(R.val.begin(), N.val[i]); 743 R.correct(true); 744 R -= D * dInR(R, D); 745 } 746 R.correct(); 747 R.pos = (R.val.size() == 1 && R.val[0] == 0) ? true : pos; 748 return R; 749 } 750 751 inline InfInt InfInt::operator*(ELEM_TYPE rhs) const 752 { 753 //PROFINY_SCOPE 754 InfInt result = *this; 755 ELEM_TYPE factor = rhs < 0 ? -rhs : rhs; 756 multiplyByDigit(factor, result.val); 757 result.correct(); 758 result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == (rhs >= 0)); 759 return result; 760 } 761 762 inline bool InfInt::operator==(const InfInt& rhs) const 763 { 764 //PROFINY_SCOPE 765 if (pos != rhs.pos || val.size() != rhs.val.size()) 766 { 767 return false; 768 } 769 for (int i = (int) val.size() - 1; i >= 0; --i) 770 { 771 if (val[i] != rhs.val[i]) 772 { 773 return false; 774 } 775 } 776 return true; 777 } 778 779 inline bool InfInt::operator!=(const InfInt& rhs) const 780 { 781 //PROFINY_SCOPE 782 if (pos != rhs.pos || val.size() != rhs.val.size()) 783 { 784 return true; 785 } 786 for (int i = (int) val.size() - 1; i >= 0; --i) 787 { 788 if (val[i] != rhs.val[i]) 789 { 790 return true; 791 } 792 } 793 return false; 794 } 795 796 inline bool InfInt::operator<(const InfInt& rhs) const 797 { 798 //PROFINY_SCOPE 799 if (pos && !rhs.pos) 800 { 801 return false; 802 } 803 if (!pos && rhs.pos) 804 { 805 return true; 806 } 807 if (val.size() > rhs.val.size()) 808 { 809 return pos ? false : true; 810 } 811 if (val.size() < rhs.val.size()) 812 { 813 return pos ? true : false; 814 } 815 for (int i = (int) val.size() - 1; i >= 0; --i) 816 { 817 if (val[i] < rhs.val[i]) 818 { 819 return pos ? true : false; 820 } 821 if (val[i] > rhs.val[i]) 822 { 823 return pos ? false : true; 824 } 825 } 826 return false; 827 } 828 829 inline bool InfInt::operator<=(const InfInt& rhs) const 830 { 831 //PROFINY_SCOPE 832 if (pos && !rhs.pos) 833 { 834 return false; 835 } 836 if (!pos && rhs.pos) 837 { 838 return true; 839 } 840 if (val.size() > rhs.val.size()) 841 { 842 return pos ? false : true; 843 } 844 if (val.size() < rhs.val.size()) 845 { 846 return pos ? true : false; 847 } 848 for (int i = (int) val.size() - 1; i >= 0; --i) 849 { 850 if (val[i] < rhs.val[i]) 851 { 852 return pos ? true : false; 853 } 854 if (val[i] > rhs.val[i]) 855 { 856 return pos ? false : true; 857 } 858 } 859 return true; 860 } 861 862 inline bool InfInt::operator>(const InfInt& rhs) const 863 { 864 //PROFINY_SCOPE 865 if (pos && !rhs.pos) 866 { 867 return true; 868 } 869 if (!pos && rhs.pos) 870 { 871 return false; 872 } 873 if (val.size() > rhs.val.size()) 874 { 875 return pos ? true : false; 876 } 877 if (val.size() < rhs.val.size()) 878 { 879 return pos ? false : true; 880 } 881 for (int i = (int) val.size() - 1; i >= 0; --i) 882 { 883 if (val[i] < rhs.val[i]) 884 { 885 return pos ? false : true; 886 } 887 if (val[i] > rhs.val[i]) 888 { 889 return pos ? true : false; 890 } 891 } 892 return false; 893 } 894 895 inline bool InfInt::operator>=(const InfInt& rhs) const 896 { 897 //PROFINY_SCOPE 898 if (pos && !rhs.pos) 899 { 900 return true; 901 } 902 if (!pos && rhs.pos) 903 { 904 return false; 905 } 906 if (val.size() > rhs.val.size()) 907 { 908 return pos ? true : false; 909 } 910 if (val.size() < rhs.val.size()) 911 { 912 return pos ? false : true; 913 } 914 for (int i = (int) val.size() - 1; i >= 0; --i) 915 { 916 if (val[i] < rhs.val[i]) 917 { 918 return pos ? false : true; 919 } 920 if (val[i] > rhs.val[i]) 921 { 922 return pos ? true : false; 923 } 924 } 925 return true; 926 } 927 928 inline void InfInt::optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const 929 { 930 //PROFINY_SCOPE 931 InfInt hdn = 1; 932 for (int i = (int) this->numberOfDigits() / 2; i >= 2; --i) 933 { 934 hdn *= 10; 935 } 936 if (lo < hdn) 937 { 938 lo = hdn; 939 } 940 hdn *= 100; 941 if (hi > hdn) 942 { 943 hi = hdn; 944 } 945 } 946 947 inline InfInt InfInt::intSqrt() const 948 { 949 //PROFINY_SCOPE 950 if (*this <= 0) 951 { 952 #ifdef INFINT_USE_EXCEPTIONS 953 throw InfIntException("intSqrt called for non-positive integer"); 954 #else 955 std::cerr << "intSqrt called for non-positive integer: " << *this << std::endl; 956 return 0; 957 #endif 958 } 959 InfInt hi = *this / 2 + 1, lo = 0, mid, mid2; 960 optimizeSqrtSearchBounds(lo, hi); 961 do 962 { 963 mid = (hi + lo) / 2; // 8 factor 964 mid2 = mid * mid; // 1 factor 965 if (mid2 == *this) 966 { 967 lo = mid; 968 break; 969 } 970 else if (mid2 < *this) 971 { 972 lo = mid; 973 } 974 else 975 { 976 hi = mid; 977 } 978 } while (lo < hi - 1 && mid2 != *this); 979 return lo; 980 } 981 982 inline char InfInt::digitAt(size_t i) const 983 { 984 //PROFINY_SCOPE 985 if (numberOfDigits() <= i) 986 { 987 #ifdef INFINT_USE_EXCEPTIONS 988 throw InfIntException("invalid digit index"); 989 #else 990 std::cerr << "Invalid digit index: " << i << std::endl; 991 return -1; 992 #endif 993 } 994 return (val[i / DIGIT_COUNT] / powersOfTen[i % DIGIT_COUNT]) % 10; 995 } 996 997 inline size_t InfInt::numberOfDigits() const 998 { 999 //PROFINY_SCOPE 1000 return (val.size() - 1) * DIGIT_COUNT + 1001 (val.back() > 99999999 ? 9 : (val.back() > 9999999 ? 8 : (val.back() > 999999 ? 7 : (val.back() > 99999 ? 6 : 1002 (val.back() > 9999 ? 5 : (val.back() > 999 ? 4 : (val.back() > 99 ? 3 : (val.back() > 9 ? 2 : 1)))))))); 1003 } 1004 1005 inline std::string InfInt::toString() const 1006 { 1007 //PROFINY_SCOPE 1008 std::ostringstream oss; 1009 oss << *this; 1010 return oss.str(); 1011 } 1012 1013 inline size_t InfInt::size() const 1014 { 1015 //PROFINY_SCOPE 1016 return val.size() * sizeof(ELEM_TYPE) + sizeof(bool); 1017 } 1018 1019 inline int InfInt::toInt() const 1020 { 1021 //PROFINY_SCOPE 1022 if (*this > INT_MAX || *this < INT_MIN) 1023 { 1024 #ifdef INFINT_USE_EXCEPTIONS 1025 throw InfIntException("out of bounds"); 1026 #else 1027 std::cerr << "Out of INT bounds: " << *this << std::endl; 1028 #endif 1029 } 1030 int result = 0; 1031 for (int i = (int) val.size() - 1; i >= 0; --i) 1032 { 1033 result = result * BASE + val[i]; 1034 } 1035 return pos ? result : -result; 1036 } 1037 1038 inline long InfInt::toLong() const 1039 { 1040 //PROFINY_SCOPE 1041 if (*this > LONG_MAX || *this < LONG_MIN) 1042 { 1043 #ifdef INFINT_USE_EXCEPTIONS 1044 throw InfIntException("out of bounds"); 1045 #else 1046 std::cerr << "Out of LONG bounds: " << *this << std::endl; 1047 #endif 1048 } 1049 long result = 0; 1050 for (int i = (int) val.size() - 1; i >= 0; --i) 1051 { 1052 result = result * BASE + val[i]; 1053 } 1054 return pos ? result : -result; 1055 } 1056 1057 inline long long InfInt::toLongLong() const 1058 { 1059 //PROFINY_SCOPE 1060 if (*this > LONG_LONG_MAX || *this < LONG_LONG_MIN) 1061 { 1062 #ifdef INFINT_USE_EXCEPTIONS 1063 throw InfIntException("out of bounds"); 1064 #else 1065 std::cerr << "Out of LLONG bounds: " << *this << std::endl; 1066 #endif 1067 } 1068 long long result = 0; 1069 for (int i = (int) val.size() - 1; i >= 0; --i) 1070 { 1071 result = result * BASE + val[i]; 1072 } 1073 return pos ? result : -result; 1074 } 1075 1076 inline unsigned int InfInt::toUnsignedInt() const 1077 { 1078 //PROFINY_SCOPE 1079 if (!pos || *this > UINT_MAX) 1080 { 1081 #ifdef INFINT_USE_EXCEPTIONS 1082 throw InfIntException("out of bounds"); 1083 #else 1084 std::cerr << "Out of UINT bounds: " << *this << std::endl; 1085 #endif 1086 } 1087 unsigned int result = 0; 1088 for (int i = (int) val.size() - 1; i >= 0; --i) 1089 { 1090 result = result * BASE + val[i]; 1091 } 1092 return result; 1093 } 1094 1095 inline unsigned long InfInt::toUnsignedLong() const 1096 { 1097 //PROFINY_SCOPE 1098 if (!pos || *this > ULONG_MAX) 1099 { 1100 #ifdef INFINT_USE_EXCEPTIONS 1101 throw InfIntException("out of bounds"); 1102 #else 1103 std::cerr << "Out of ULONG bounds: " << *this << std::endl; 1104 #endif 1105 } 1106 unsigned long result = 0; 1107 for (int i = (int) val.size() - 1; i >= 0; --i) 1108 { 1109 result = result * BASE + val[i]; 1110 } 1111 return result; 1112 } 1113 1114 inline unsigned long long InfInt::toUnsignedLongLong() const 1115 { 1116 //PROFINY_SCOPE 1117 if (!pos || *this > ULONG_LONG_MAX) 1118 { 1119 #ifdef INFINT_USE_EXCEPTIONS 1120 throw InfIntException("out of bounds"); 1121 #else 1122 std::cerr << "Out of ULLONG bounds: " << *this << std::endl; 1123 #endif 1124 } 1125 unsigned long long result = 0; 1126 for (int i = (int) val.size() - 1; i >= 0; --i) 1127 { 1128 result = result * BASE + val[i]; 1129 } 1130 return result; 1131 } 1132 1133 inline void InfInt::truncateToBase() 1134 { 1135 //PROFINY_SCOPE 1136 for (size_t i = 0; i < val.size(); ++i) // truncate each 1137 { 1138 if (val[i] >= BASE || val[i] <= -BASE) 1139 { 1140 div_t dt = my_div(val[i], BASE); 1141 val[i] = dt.rem; 1142 if (i + 1 >= val.size()) 1143 { 1144 val.push_back(dt.quot); 1145 } 1146 else 1147 { 1148 val[i + 1] += dt.quot; 1149 } 1150 } 1151 } 1152 } 1153 1154 inline bool InfInt::equalizeSigns() 1155 { 1156 //PROFINY_SCOPE 1157 bool isPositive = true; 1158 int i = (int) ((val.size())) - 1; 1159 for (; i >= 0; --i) 1160 { 1161 if (val[i] != 0) 1162 { 1163 isPositive = val[i--] > 0; 1164 break; 1165 } 1166 } 1167 1168 if (isPositive) 1169 { 1170 for (; i >= 0; --i) 1171 { 1172 if (val[i] < 0) 1173 { 1174 int k = 0, index = i + 1; 1175 for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on left 1176 //if ((size_t)(index) < val.size() && val[index] > 0) 1177 { // number on the left is positive 1178 val[index] -= 1; 1179 val[i] += BASE; 1180 for (; k > 0; --k) 1181 { 1182 val[i + k] = UPPER_BOUND; 1183 } 1184 } 1185 } 1186 } 1187 } 1188 else 1189 { 1190 for (; i >= 0; --i) 1191 { 1192 if (val[i] > 0) 1193 { 1194 int k = 0, index = i + 1; 1195 for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on right 1196 //if ((size_t)(index) < val.size() && val[index] < 0) 1197 { // number on the left is negative 1198 val[index] += 1; 1199 val[i] -= BASE; 1200 for (; k > 0; --k) 1201 { 1202 val[i + k] = -UPPER_BOUND; 1203 } 1204 } 1205 } 1206 } 1207 } 1208 1209 return isPositive; 1210 } 1211 1212 inline void InfInt::removeLeadingZeros() 1213 { 1214 //PROFINY_SCOPE 1215 for (int i = (int) (val.size()) - 1; i > 0; --i) // remove leading 0's 1216 { 1217 if (val[i] != 0) 1218 { 1219 return; 1220 } 1221 else 1222 { 1223 val.erase(val.begin() + i); 1224 } 1225 } 1226 } 1227 1228 inline void InfInt::correct(bool justCheckLeadingZeros, bool hasValidSign) 1229 { 1230 //PROFINY_SCOPE 1231 if (!justCheckLeadingZeros) 1232 { 1233 truncateToBase(); 1234 1235 if (equalizeSigns()) 1236 { 1237 pos = ((val.size() == 1 && val[0] == 0) || !hasValidSign) ? true : pos; 1238 } 1239 else 1240 { 1241 pos = hasValidSign ? !pos : false; 1242 for (size_t i = 0; i < val.size(); ++i) 1243 { 1244 val[i] = abs(val[i]); 1245 } 1246 } 1247 } 1248 1249 removeLeadingZeros(); 1250 } 1251 1252 inline void InfInt::fromString(const std::string& s) 1253 { 1254 //PROFINY_SCOPE 1255 pos = true; 1256 val.clear(); 1257 val.reserve(s.size() / DIGIT_COUNT + 1); 1258 int i = (int) s.size() - DIGIT_COUNT; 1259 for (; i >= 0; i -= DIGIT_COUNT) 1260 { 1261 val.push_back(atoi(s.substr(i, DIGIT_COUNT).c_str())); 1262 } 1263 if (i > -DIGIT_COUNT) 1264 { 1265 std::string ss = s.substr(0, i + DIGIT_COUNT); 1266 if (ss.size() == 1 && ss[0] == '-') 1267 { 1268 pos = false; 1269 } 1270 else 1271 { 1272 val.push_back(atoi(ss.c_str())); 1273 } 1274 } 1275 if (val.back() < 0) 1276 { 1277 val.back() = -val.back(); 1278 pos = false; 1279 } 1280 correct(true); 1281 } 1282 1283 inline ELEM_TYPE InfInt::dInR(const InfInt& R, const InfInt& D) 1284 { 1285 //PROFINY_SCOPE 1286 ELEM_TYPE min = 0, max = UPPER_BOUND; 1287 while (max > min) 1288 { 1289 ELEM_TYPE avg = max + min; 1290 div_t dt = my_div(avg, 2); 1291 avg = dt.rem ? (dt.quot + 1) : dt.quot; 1292 InfInt prod = D * avg; 1293 if (R == prod) 1294 { 1295 return avg; 1296 } 1297 else if (R > prod) 1298 { 1299 min = avg; 1300 } 1301 else 1302 { 1303 max = avg - 1; 1304 } 1305 } 1306 return min; 1307 } 1308 1309 inline void InfInt::multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val) 1310 { 1311 //PROFINY_SCOPE 1312 ELEM_TYPE carry = 0; 1313 for (size_t i = 0; i < val.size(); ++i) 1314 { 1315 PRODUCT_TYPE pval = val[i] * (PRODUCT_TYPE) factor + carry; 1316 if (pval >= BASE || pval <= -BASE) 1317 { 1318 lldiv_t dt = my_lldiv(pval, BASE); 1319 carry = (ELEM_TYPE) dt.quot; 1320 pval = dt.rem; 1321 } 1322 else 1323 { 1324 carry = 0; 1325 } 1326 val[i] = (ELEM_TYPE) pval; 1327 } 1328 if (carry > 0) 1329 { 1330 val.push_back(carry); 1331 } 1332 } 1333 1334 /**************************************************************/ 1335 /******************** NON-MEMBER OPERATORS ********************/ 1336 /**************************************************************/ 1337 1338 inline std::istream& operator>>(std::istream &s, InfInt &n) 1339 { 1340 //PROFINY_SCOPE 1341 std::string str; 1342 s >> str; 1343 n.fromString(str); 1344 return s; 1345 } 1346 1347 inline std::ostream& operator<<(std::ostream &s, const InfInt &n) 1348 { 1349 //PROFINY_SCOPE 1350 if (!n.pos) 1351 { 1352 s << '-'; 1353 } 1354 bool first = true; 1355 for (int i = (int) n.val.size() - 1; i >= 0; --i) 1356 { 1357 if (first) 1358 { 1359 s << n.val[i]; 1360 first = false; 1361 } 1362 else 1363 { 1364 s << std::setfill('0') << std::setw(DIGIT_COUNT) << n.val[i]; 1365 } 1366 } 1367 return s; 1368 } 1369 1370 #endif