SHARE
TWEET

Untitled

a guest Apr 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "big_integer.h"
  2. #include <string>
  3. #include <vector>
  4.  
  5. big_integer::big_integer() {
  6.     data.push_back(0);
  7.     sign = false;
  8. }
  9.  
  10. big_integer::big_integer(big_integer const &other) {
  11.     sign = other.sign;
  12.     data = other.data;
  13.     normalize();
  14. }
  15.  
  16. big_integer::big_integer(unsigned a) {
  17.     sign = 0;
  18.     data.push_back(a);
  19. }
  20.  
  21. big_integer::big_integer(int a) {
  22.     sign = a < 0;
  23.     data.push_back(a);
  24. }
  25.  
  26. big_integer::big_integer(std::string const &str) {
  27.     bool start_index = !(str.empty()) && str[0] == '-';
  28.     data.push_back(0);
  29.     sign = false;
  30.     for (size_t i = start_index; i < str.size(); ++i) {
  31.         (*this) *= 10;
  32.         (*this) += (str[i] - '0');
  33.     }
  34.     if (start_index) *this = -*this;
  35.     normalize();
  36. }
  37.  
  38. big_integer::~big_integer() {
  39.     data.clear();
  40. }
  41.  
  42. big_integer &big_integer::operator=(big_integer const &other) {
  43.     data = other.data;
  44.     sign = other.sign;
  45.     return *this;
  46. }
  47.  
  48. bool big_integer::operator==(big_integer const &other) const {
  49.     return data == other.data && sign == other.sign;
  50. }
  51.  
  52. bool big_integer::operator!=(big_integer const &other) const {
  53.     return !(*this == other);
  54. }
  55.  
  56. bool big_integer::operator<=(big_integer const &other) const {
  57.     if (sign != other.sign) return sign;
  58.     if (data.size() != other.data.size()) {
  59.         return sign ^ (data.size() < other.data.size());
  60.     }
  61.     for (size_t i = data.size() - 1; i < data.size(); --i) {
  62.         if (data[i] != other.data[i]) {
  63.             return sign ^ (data[i] < other.data[i]);
  64.         }
  65.     }
  66.     return true;
  67. }
  68.  
  69. bool big_integer::operator>(big_integer const &other) const {
  70.     return !(*this <= other);
  71. }
  72.  
  73. bool big_integer::operator<(big_integer const &other) const {
  74.     return (*this <= other) && (*this != other);
  75. }
  76.  
  77. bool big_integer::operator>=(big_integer const &other) const {
  78.     return !(*this < other);
  79. }
  80.  
  81. big_integer &big_integer::operator+=(big_integer const &other) {
  82.     ull carry = 0;
  83.     std::vector<unsigned> res(std::max(other.data.size(), data.size()) + 1);
  84.     for (size_t i = 0; i < res.size(); ++i) {
  85.         ull sum = carry + get_digit(i) + other.get_digit(i);
  86.         res[i] = static_cast<unsigned>(sum);
  87.         carry = sum / BASE;
  88.     }
  89.     data = res;
  90.     sign = data.back() & (1 << (BASE_SIZE - 1));
  91.     normalize();
  92.     return *this;
  93. }
  94.  
  95. big_integer &big_integer::operator-=(big_integer const &other) {
  96.     return *this += (-other);
  97. }
  98.  
  99.  
  100. big_integer &big_integer::operator*=(big_integer const &other) {
  101.     big_integer a(abs());
  102.     big_integer b(other.abs());
  103.     if (a == 0 || b == 0) {
  104.         *this = 0;
  105.         return *this;
  106.     }
  107.     big_integer res(0);
  108.     res.data.resize(a.length() + b.length() + 1, 0);
  109.     for (size_t i = 0; i < a.length(); ++i) {
  110.         unsigned carry = 0;
  111.         for (size_t j = 0; j < b.length(); ++j) {
  112.             ull sum = res.data[i + j] + static_cast<ull>(a.data[i]) * b.data[j] + carry;
  113.             res.data[i + j] = sum;
  114.             carry = sum / BASE;
  115.         }
  116.         size_t x = b.length();
  117.         while (carry != 0) {
  118.             ull sum = static_cast<ull>(res.data[i + x]) + carry;
  119.             res.data[i + x] = sum;
  120.             carry = sum / BASE;
  121.             x++;
  122.         }
  123.     }
  124.     if (sign ^ other.sign) {
  125.         *this = -res;
  126.     } else {
  127.         *this = res;
  128.     }
  129.     normalize();
  130.     return *this;
  131. }
  132.  
  133. big_integer &big_integer::operator/=(big_integer const &other) {
  134.     if (other == 0) {
  135.         throw std::runtime_error("Division by zero");
  136.     }
  137.     big_integer a = abs();
  138.     big_integer b = other.abs();
  139.     if (a < b) {
  140.         *this = 0;
  141.         return *this;
  142.     }
  143.     if (a == b) {
  144.         *this = 1;
  145.         return *this;
  146.     }
  147.     big_integer res(0), mod(0);
  148.     unsigned f = (BASE / (b.data.back() + 1ll));
  149.     a *= f;
  150.     b *= f;
  151.     size_t n = a.data.size(), m = b.data.size();
  152.     data.resize(n, 0);
  153.     std::vector<unsigned> data(n - m + 1);
  154.     mod = a >> ((n - m + 1) * BASE_SIZE);
  155.     ull top = b.data.back();
  156.     for (size_t i = 0; i <= n - m; ++i) {
  157.         size_t idx = n - m - i;
  158.         mod <<= BASE_SIZE;
  159.         mod.data[0] = a.data[idx];
  160.         ull mod_top = mod.data.back();
  161.         if (mod.data.size() > m) {
  162.             mod_top <<= BASE_SIZE;
  163.             mod_top += mod.data[mod.data.size() - 2];
  164.         }
  165.         unsigned guess = std::min(mod_top / top, BASE - 1);
  166.         big_integer res_guess = guess * b;
  167.         while (mod < res_guess) {
  168.             guess--;
  169.             res_guess -= b;
  170.         }
  171.         data[idx] = guess;
  172.         mod -= res_guess;
  173.     }
  174.     big_integer tmp(false, data);
  175.     tmp.normalize();
  176.     sign ^= other.sign;
  177.     if (sign) {
  178.         tmp = -tmp;
  179.     }
  180.     *this = tmp;
  181.     normalize();
  182.     return *this;
  183. }
  184.  
  185. big_integer &big_integer::operator&=(big_integer const &other) {
  186.     for (size_t i = 0; i < data.size(); ++i) {
  187.         data[i] &= other.get_digit(i);
  188.     }
  189.     sign &= other.sign;
  190.     normalize();
  191.     return *this;
  192. }
  193.  
  194. big_integer &big_integer::operator^=(big_integer const &other) {
  195.     for (size_t i = 0; i < std::max(data.size(), other.data.size()); ++i) {
  196.         if (i < data.size()) data[i] ^= other.get_digit(i);
  197.         else data.push_back(other.data[i]);
  198.     }
  199.     sign ^= other.sign;
  200.     normalize();
  201.     return *this;
  202. }
  203.  
  204. big_integer &big_integer::operator|=(big_integer const &other) {
  205.     for (size_t i = 0; i < std::max(data.size(), other.data.size()); ++i) {
  206.         if (i < data.size()) data[i] |= other.get_digit(i);
  207.         else data.push_back(other.data[i]);
  208.     }
  209.     sign |= other.sign;
  210.     normalize();
  211.     return *this;
  212. }
  213.  
  214. big_integer &big_integer::operator<<=(int a) {
  215.     if (a < 0) {
  216.         return (*this) >>= a;
  217.     }
  218.     size_t div = a >> 5;
  219.     size_t mod = a & (BASE_SIZE - 1);
  220.     size_t new_size = length() + div + 1;
  221.     std::vector<unsigned> temp(new_size);
  222.     temp[div] = static_cast<unsigned >(static_cast<ull>(get_digit(0)) << mod);
  223.     for (size_t i = div + 1; i < new_size; i++) {
  224.         unsigned x = static_cast<ull >(get_digit(i - div)) << mod;
  225.         unsigned y = static_cast<ull>(data[i - div - 1]) >> (BASE_SIZE - mod);
  226.         temp[i] = x | y;
  227.     }
  228.     data = temp;
  229.     normalize();
  230.     return *this;
  231. }
  232.  
  233. big_integer &big_integer::operator>>=(int a) {
  234.     if (a < 0) {
  235.         return (*this) <<= a;
  236.     }
  237.     size_t div = a >> 5;
  238.     unsigned mod = a & (BASE_SIZE - 1);
  239.     size_t new_size = 0;
  240.     if (div < (*this).length()) {
  241.         new_size = (*this).length() - div;
  242.     }
  243.     std::vector<unsigned> temp(new_size);
  244.     for (size_t i = 0; i < new_size; i++) {
  245.         unsigned x = static_cast<ull>(data[i + div]) >> mod;
  246.         unsigned y = static_cast<ull>(get_digit(i + div + 1)) << (BASE_SIZE - mod);
  247.         temp[i] = x | y;
  248.     }
  249.     data = temp;
  250.     normalize();
  251.     return *this;
  252. }
  253.  
  254.  
  255. big_integer &big_integer::operator%=(big_integer const &other) {
  256.     normalize();
  257.     big_integer a = (*this / other) * other;
  258.     return *this -= a;
  259. }
  260.  
  261. big_integer big_integer::operator-() const {
  262.     if (*this == 0) {
  263.         return *this;
  264.     }
  265.     big_integer tmp(*this);
  266.     tmp = ~tmp;
  267.     ++tmp;
  268.     tmp.sign = !sign;
  269.     return tmp;
  270. }
  271.  
  272. big_integer big_integer::operator+() const {
  273.     big_integer tmp(*this);
  274.     return tmp;
  275. }
  276.  
  277. big_integer &big_integer::operator++() {
  278.     normalize();
  279.     return *this += 1;
  280. }
  281.  
  282. big_integer big_integer::operator++(int) {
  283.     normalize();
  284.     big_integer tmp = *this;
  285.     ++(*this);
  286.     return tmp;
  287. }
  288.  
  289. big_integer &big_integer::operator--() {
  290.     normalize();
  291.     return *this -= 1;
  292. }
  293.  
  294. big_integer big_integer::operator--(int) {
  295.     normalize();
  296.     big_integer tmp(*this);
  297.     --(*this);
  298.     return tmp;
  299. }
  300.  
  301. big_integer big_integer::operator~() const {
  302.     big_integer tmp(*this);
  303.     for (size_t i = 0; i < tmp.data.size(); ++i) {
  304.         tmp.data[i] = ~data[i];
  305.     }
  306.     tmp.sign = !tmp.sign;
  307.     return tmp;
  308. }
  309.  
  310. big_integer big_integer::abs() const {
  311.     if (sign) return -(*this);
  312.     return *this;
  313. }
  314.  
  315. void big_integer::swap(big_integer &b) {
  316.     big_integer temp(*this);
  317.     sign = b.sign;
  318.     data = b.data;
  319.     b.sign = temp.sign;
  320.     b.data = temp.data;
  321.     normalize();
  322. }
  323.  
  324. const unsigned big_integer::get_digit(size_t i) const {
  325.     if (i < data.size()) return data[i];
  326.     if (sign) return MAX_VALUE;
  327.     return 0;
  328. }
  329.  
  330. bool big_integer::below_zero() const {
  331.     return sign;
  332. }
  333.  
  334. big_integer::big_integer(bool negate, std::vector<unsigned> const &data) {
  335.     this->data = data;
  336.     sign = negate;
  337.     normalize();
  338. }
  339.  
  340. void big_integer::normalize() {
  341.     while (data.size() > 1 && ((data.back() == 0 && !sign) || (data.back() == MAX_VALUE && sign))) {
  342.         data.pop_back();
  343.     }
  344. }
  345.  
  346. size_t big_integer::length() const {
  347.     return data.size();
  348. }
  349.  
  350. big_integer operator+(big_integer a, big_integer const &b) {
  351.     return a += b;
  352. }
  353.  
  354. big_integer operator-(big_integer a, big_integer const &b) {
  355.     return a -= b;
  356. }
  357.  
  358. big_integer operator*(big_integer a, big_integer const &b) {
  359.     return a *= b;
  360. }
  361.  
  362. big_integer operator/(big_integer a, big_integer const &b) {
  363.     return a /= b;
  364. }
  365.  
  366. big_integer operator%(big_integer a, big_integer const &b) {
  367.     return a %= b;
  368. }
  369.  
  370. big_integer operator&(big_integer a, big_integer const &b) {
  371.     return a &= b;
  372. }
  373.  
  374. big_integer operator^(big_integer a, big_integer const &b) {
  375.     return a ^= b;
  376. }
  377.  
  378. big_integer operator|(big_integer a, big_integer const &b) {
  379.     return a |= b;
  380. }
  381.  
  382. big_integer operator<<(big_integer a, int b) {
  383.     return a <<= b;
  384. }
  385.  
  386. big_integer operator>>(big_integer a, int b) {
  387.     return a >>= b;
  388. }
  389.  
  390. std::string to_string(big_integer const &value) {
  391.     big_integer a = value.abs();
  392.     if (value == 0) {
  393.         return "0";
  394.     }
  395.     std::string s;
  396.     while (a != 0) {
  397.         unsigned val = (a % 10).get_digit(0);
  398.         s.push_back(val + '0');
  399.         a /= 10;
  400.     }
  401.     if (value.below_zero()) {
  402.         s.push_back('-');
  403.     }
  404.     std::reverse(s.begin(), s.end());
  405.     return s;
  406. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top