API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.04 KB | None | 0 0
raw download clone embed print report
  1. #pragma once
  2.  
  3. #include <vector>
  4. #include <string>
  5. #include <iostream>
  6.  
  7.  
  8. const unsigned int MaxNumber = 999999999;
  9. const unsigned int MaxLength = 9;
  10.  
  11. class BigInteger
  12. {
  13. public:
  14.     //constructors
  15.     BigInteger(int x);
  16.     BigInteger();
  17.     //operations
  18.     friend BigInteger operator+(const BigInteger& a, const BigInteger& x);
  19.     BigInteger& operator+=(const BigInteger& x);
  20.     friend BigInteger operator-(const BigInteger& a, const BigInteger& x);
  21.     BigInteger& operator-=(const BigInteger& x);
  22.     friend BigInteger operator*(const BigInteger& a, const BigInteger& x);
  23.     BigInteger& operator*=(const BigInteger& x);
  24.     friend BigInteger operator/(const BigInteger& a, const BigInteger& x);
  25.     BigInteger& operator/=(const BigInteger& x);
  26.     friend BigInteger operator%(const BigInteger& a, const BigInteger& x);
  27.     BigInteger& operator%=(const BigInteger& x);
  28.     //unar operations
  29.     BigInteger operator-() const;
  30.     BigInteger& operator++();
  31.     BigInteger operator++(int x);
  32.     BigInteger& operator--();
  33.     BigInteger operator--(int x);
  34.     //bool
  35.     friend bool operator==(const BigInteger& a, const BigInteger& x);
  36.     friend bool operator!=(const BigInteger& a, const BigInteger& x);
  37.     friend bool operator<(const BigInteger& a, const BigInteger& x);
  38.     friend bool operator<=(const BigInteger& a, const BigInteger& x);
  39.     friend bool operator>(const BigInteger& a, const BigInteger& x);
  40.     friend bool operator>=(const BigInteger& a, const BigInteger& x);
  41.     explicit operator bool();
  42.     //streams
  43.     friend std::istream& operator>>(std::istream& os, BigInteger& x);
  44.     friend std::ostream& operator<<(std::ostream& os, const BigInteger& x);
  45.     //miscellaneous
  46.     std::string toString() const;
  47. private:
  48.     std::vector<unsigned int> number;
  49.     int sign;
  50.     BigInteger operator>>(unsigned int x) const;
  51.     BigInteger mult(unsigned int x) const;
  52.     void summ(const BigInteger& x);
  53.     void sub(const BigInteger& x);
  54.     void set_sign();
  55. };
  56. BigInteger::BigInteger(int x):
  57.     number(0)
  58. {
  59.     if (x < 0)
  60.     {
  61.         x = -x;
  62.         sign = -1;
  63.     }
  64.     else
  65.         sign = 1;
  66.     number.push_back(x % (MaxNumber + 1));
  67.     x /= (MaxNumber + 1);
  68.     while (x > 0)
  69.     {
  70.         number.push_back(x % (MaxNumber + 1));
  71.         x /= (MaxNumber + 1);
  72.     }
  73. }
  74. BigInteger::BigInteger():
  75.     number(1, 0),
  76.     sign(1)
  77. {
  78. }
  79. BigInteger operator+(const BigInteger& a, const BigInteger& x)
  80. {
  81.     if (a.sign != x.sign)
  82.         return a - (-x);
  83.     BigInteger temp_a(a);
  84.     temp_a.summ(x);
  85.     return temp_a;
  86. }
  87. BigInteger& BigInteger::operator+=(const BigInteger& x)
  88. {
  89.     *this = *this + x;
  90.     return *this;
  91. }
  92. BigInteger operator-(const BigInteger& a, const BigInteger& x)
  93. {
  94.     if (a.sign != x.sign)
  95.     {
  96.         BigInteger temp_a(a);
  97.         temp_a.sign *= -1;
  98.         temp_a.summ(x);
  99.         temp_a.sign = a.sign;
  100.         temp_a.set_sign();
  101.         return temp_a;
  102.     }
  103.     BigInteger temp_a(a), temp_x(x);
  104.     temp_a.sign = 1;
  105.     temp_x.sign = 1;
  106.     if (temp_a < temp_x)
  107.     {
  108.         temp_x.sub(temp_a);
  109.         temp_x.sign = a.sign * (-1);
  110.         temp_x.set_sign();
  111.         return temp_x;
  112.     }
  113.     else
  114.     {
  115.         temp_a.sub(temp_x);
  116.         temp_a.sign = a.sign;
  117.         temp_a.set_sign();
  118.         return temp_a;
  119.     }
  120. }
  121. BigInteger& BigInteger::operator-=(const BigInteger& x)
  122. {
  123.     *this = *this - x;
  124.     return *this;
  125. }
  126. BigInteger operator*(const BigInteger& a, const BigInteger& x)
  127. {
  128.     BigInteger result(0), result1(0), result2(0), result3(0);
  129.     BigInteger a1, a2, x1, x2;
  130.     if (a.number.size() > 1) && (x.number.size() > 1) {
  131.         for (int i = 0; i<a.number.size()/2; i++) {
  132.             a1.push_back(a.numbers[i]);
  133.             a2.push_back(a.numbers[(a.number.size()/2) + 1])
  134.         }
  135.         for (int i = 0; i<x.number.size()/2; i++) {
  136.             x1.push_back(x.numbers[i]);
  137.             x2.push_back(x.numbers[(x.number.size()/2) + 1])
  138.         }
  139.     result1 = a1*x1;
  140.     result3 = a2*x2;
  141.     result2 = (a1+a2)*(x1+x2) - result1 - result3;
  142.     result1 = result1.mult(MaxNumber);
  143.     result = result1.mult(MaxNumber) + result2.mult(MaxNumber) + result3;
  144.     } else {
  145.     for (unsigned int i = 0; i < x.number.size(); i++)
  146.     {
  147.         result += a.mult(x.number[i]) >> i;
  148.     }
  149.     }
  150.     result.sign = a.sign * x.sign;
  151.     while ((result.number[result.number.size() - 1] == 0) && (result.number.size() > 1))
  152.         result.number.pop_back();
  153.     result.set_sign();
  154.     return result;
  155. }
  156. BigInteger& BigInteger::operator*=(const BigInteger& x)
  157. {
  158.     *this = *this * x;
  159.     return *this;
  160. }
  161. BigInteger operator/(const BigInteger& a, const BigInteger& x)
  162. {
  163.     if ((x.number.size() == 1) && (x.number[0] == 0))
  164.         return 0;
  165.     BigInteger result(0);
  166.     while (result.number.size() < a.number.size())
  167.         result.number.push_back(0);
  168.     result.sign = a.sign * x.sign;
  169.     BigInteger current = a;
  170.     current.sign = 1;
  171.     BigInteger temp_x = x;
  172.     temp_x.sign = 1;
  173.     for (int i = current.number.size() - temp_x.number.size(); (current >= temp_x) && (i >= 0); i--)
  174.     {
  175.         unsigned int max = MaxNumber;
  176.         unsigned int min = 0;
  177.         while (max - min > 1)
  178.         {
  179.             unsigned int median = (min + max) / 2;
  180.             BigInteger check = (temp_x.mult(median) >> i);
  181.             if (current >= check)
  182.                 min = median;
  183.             else
  184.                 max = median;
  185.         }
  186.         BigInteger check = (temp_x.mult(max) >> i);
  187.         if (current >= check)
  188.         {
  189.             result.number[i] = max;
  190.             current -= check;
  191.         }
  192.         else
  193.         {
  194.             result.number[i] = min;
  195.             current -= (temp_x.mult(min) >> i);
  196.         }
  197.     }
  198.     while ((result.number[result.number.size() - 1] == 0) && (result.number.size() > 1))
  199.         result.number.pop_back();
  200.     result.set_sign();
  201.     return result;
  202. }
  203. BigInteger& BigInteger::operator/=(const BigInteger& x)
  204. {
  205.     *this = *this / x;
  206.     return *this;
  207. }
  208. BigInteger operator%(const BigInteger& a, const BigInteger& x)
  209. {
  210.     BigInteger temp_a(a);
  211.     temp_a /= x;
  212.     temp_a *= x;
  213.     return a - temp_a;
  214. }
  215. BigInteger& BigInteger::operator%=(const BigInteger& x)
  216. {
  217.     *this = *this % x;
  218.     return *this;
  219. }
  220. BigInteger BigInteger::operator-() const
  221. {
  222.     BigInteger result = *this;
  223.     if ((result.number.size() == 1) && (result.number[0] == 0))
  224.         result.sign = 1;
  225.     else
  226.         result.sign *= -1;
  227.     return result;
  228. }
  229. BigInteger& BigInteger::operator++()
  230. {
  231.     *this += 1;
  232.     return *this;
  233. }
  234. BigInteger BigInteger::operator++(int x)
  235. {
  236.     BigInteger result = *this;
  237.     x = 0;
  238.     *this += 1 - x;
  239.     return result;
  240. }
  241. BigInteger& BigInteger::operator--()
  242. {
  243.     *this -= 1;
  244.     return *this;
  245. }
  246. BigInteger BigInteger::operator--(int x)
  247. {
  248.     BigInteger result = *this;
  249.     x = 0;
  250.     *this -= 1 - x;
  251.     return result;
  252. }
  253. bool operator==(const BigInteger& a, const BigInteger& x)
  254. {
  255.     if (a.number.size() != x.number.size())
  256.         return false;
  257.     if (a.sign != x.sign)
  258.         return false;
  259.     bool result = true;
  260.     for (unsigned int i = 0; (i < a.number.size()) && result; i++)
  261.     {
  262.         result = a.number[i] == x.number[i];
  263.     }
  264.     return result;
  265. }
  266. bool operator!=(const BigInteger& a, const BigInteger& x)
  267. {
  268.     return !(a == x);
  269. }
  270. bool operator<(const BigInteger& a, const BigInteger& x)
  271. {
  272.     if (a.sign != x.sign)
  273.         return a.sign < x.sign;
  274.     if (a.sign == -1)
  275.         return (-a) > (-x);
  276.     if (a.number.size() != x.number.size())
  277.         return a.number.size() < x.number.size();
  278.     int i = a.number.size() - 1;
  279.     for (i = a.number.size() - 1; (i > 0) && (a.number[i] == x.number[i]); i--);
  280.     return a.number[i] < x.number[i];
  281.     return false;
  282. }
  283. bool operator<=(const BigInteger& a, const BigInteger& x)
  284. {
  285.     return !(a > x);
  286. }
  287. bool operator>(const BigInteger& a, const BigInteger& x)
  288. {
  289.     if (a.sign != x.sign)
  290.         return a.sign > x.sign;
  291.     if (a.sign == -1)
  292.         return (-a) < (-x);
  293.     if (a.number.size() != x.number.size())
  294.         return a.number.size() > x.number.size();
  295.     int i = a.number.size() - 1;
  296.     for (i = a.number.size() - 1; (i > 0) && (a.number[i] == x.number[i]); i--);
  297.     return a.number[i] > x.number[i];
  298.     return false;
  299. }
  300. bool operator>=(const BigInteger& a, const BigInteger& x)
  301. {
  302.     return !(a < x);
  303. }
  304. BigInteger::operator bool()
  305. {
  306.     if (number.size() == 1)
  307.         return bool(number[0]);
  308.     return true;
  309. }
  310. std::istream& operator>>(std::istream& os, BigInteger& x)
  311. {
  312.     x = 0;
  313.     std::string s;
  314.     os >> s;
  315.     unsigned int i = 0;
  316.     int sign = 1;
  317.     if (s[0] == '-')
  318.     {
  319.         sign = -1;
  320.         i++;
  321.     }
  322.     for (; i < s.length(); i++)
  323.     {
  324.         x = (x * 10) + (s[i] - '0');
  325.     }
  326.     x.sign = sign;
  327.     return os;
  328. }
  329. std::ostream& operator<<(std::ostream& os, const BigInteger& x)
  330. {
  331.     std::string s = x.toString();
  332.     for (unsigned int i = 0; i < s.length(); i++)
  333.         os << s[i];
  334.     return os;
  335. }
  336. std::string BigInteger::toString() const
  337. {
  338.     if (this->number.size() == 0)
  339.         return "";
  340.     std::string result = "";
  341.     if (sign == -1)
  342.         result += '-';
  343.     result += std::to_string(number[number.size() - 1]);
  344.     for (int i = number.size() - 2; i >= 0; i--)
  345.     {
  346.         std::string next = std::to_string(number[i]);
  347.         while (next.length() < MaxLength)
  348.             next = '0' + next;
  349.         result += next;
  350.     }
  351.     return result;
  352. }
  353. BigInteger BigInteger::operator>>(unsigned int x) const
  354. {
  355.     BigInteger result(0);
  356.     result.number.clear();
  357.     result.sign = sign;
  358.     for (unsigned int i = 0; i < x; i++)
  359.         result.number.push_back(0);
  360.     for (unsigned int i = 0; i < number.size(); i++)
  361.         result.number.push_back(number[i]);
  362.     return result;
  363. }
  364. BigInteger BigInteger::mult(unsigned int x) const
  365. {
  366.     BigInteger result(0);
  367.     result.number.clear();
  368.     result.sign = sign;
  369.     unsigned long long int current = 0;
  370.     unsigned int remained = 0;
  371.     for (unsigned int i = 0; i < number.size() + 1; i++)
  372.     {
  373.         current = 0;
  374.         if (i < number.size())
  375.         {
  376.             current += number[i];
  377.             current *= x;
  378.         }
  379.         current += remained;
  380.         result.number.push_back(static_cast<unsigned int>(current % (MaxNumber + 1)));
  381.         remained = static_cast<unsigned int>(current / (MaxNumber + 1));
  382.     }
  383.     while ((result.number[result.number.size() - 1] == 0) && (result.number.size() > 1))
  384.         result.number.pop_back();
  385.     result.set_sign();
  386.     return result;
  387. }
  388. void BigInteger::summ(const BigInteger& x)
  389. {
  390.     unsigned int maxlength = 1;
  391.     if (x.number.size() > number.size())
  392.         maxlength = x.number.size();
  393.     else
  394.         maxlength = number.size();
  395.     while (number.size() < maxlength + 1)
  396.         number.push_back(0);
  397.     unsigned long long int current = 0;
  398.     unsigned int remained = 0;
  399.     for (unsigned int i = 0; i < maxlength + 1; i++)
  400.     {
  401.         current = 0;
  402.         if (i < number.size())
  403.             current += number[i];
  404.         if (i < x.number.size())
  405.             current += x.number[i];
  406.         current += remained;
  407.         number[i] = static_cast<unsigned int>(current % (MaxNumber + 1));
  408.         remained = static_cast<unsigned int>(current / (MaxNumber + 1));
  409.     }
  410.     while ((number[number.size() - 1] == 0) && (number.size() > 1))
  411.         number.pop_back();
  412.     set_sign();
  413. }
  414. void BigInteger::sub(const BigInteger& x)
  415. {
  416.     unsigned int maxlength = 1;
  417.     if (x.number.size() > number.size())
  418.         maxlength = x.number.size();
  419.     else
  420.         maxlength = number.size();
  421.     while (number.size() < maxlength + 1)
  422.         number.push_back(0);
  423.     long long int current = 0;
  424.     int remained = 0;
  425.     for (unsigned int i = 0; i < maxlength + 1; i++)
  426.     {
  427.         current = 0;
  428.         if (i < number.size())
  429.             current += number[i];
  430.         if (i < x.number.size())
  431.             current -= x.number[i];
  432.         current -= remained;
  433.         if (current < 0)
  434.         {
  435.             number[i] = static_cast<unsigned int>(MaxNumber + 1 + current);
  436.             remained = 1;
  437.         }
  438.         else
  439.         {
  440.             number[i] = static_cast<unsigned int>(current);
  441.             remained = 0;
  442.         }
  443.     }
  444.     while ((number[number.size() - 1] == 0) && (number.size() > 1))
  445.         number.pop_back();
  446.     set_sign();
  447. }
  448. void BigInteger::set_sign()
  449. {
  450.     if ((number.size() == 1) && (number[0] == 0))
  451.         sign = 1;
  452. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!