SHARE
TWEET

BigNumbers

a guest Sep 20th, 2016 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class BigNumber
  2. {
  3.     BigNumber subNumber(int n) //used for long division, gets the number composed by the first n most significant digits
  4.     {
  5.         BigNumber s;
  6.         for (int i = _container.size() - n; i < _container.size(); i++)
  7.         {
  8.             s._container.push_back(_container[i]);
  9.         }
  10.         return s;
  11.     }
  12.     vector<int> _container;
  13. public:
  14.     BigNumber(){};
  15.     BigNumber(int x)
  16.     {
  17.         while (x > 0)
  18.         {
  19.             _container.push_back(x % 10);
  20.             x /= 10;
  21.         }
  22.     }
  23.     BigNumber(string s) //assumes base 10
  24.     {
  25.         for (int i = s.size() - 1; i >= 0; i--)
  26.         {
  27.             _container.push_back(s[i] - '0');
  28.         }
  29.     }
  30.  
  31.     vector<int> getContainer()
  32.     {
  33.         return  _container;
  34.     }
  35.  
  36.     BigNumber operator+(const BigNumber& other)
  37.     {
  38.         BigNumber result(0);
  39.         int resultLength = max(_container.size(), other._container.size());
  40.         int carry = 0;
  41.         for (int i = 0; i < resultLength; i++)
  42.         {
  43.             int addResult = (i < _container.size() ? _container[i] : 0) + (i < other._container.size() ? other._container[i] : 0);
  44.             result._container.push_back((addResult + carry) % 10);
  45.             carry = (addResult + carry) / 10;
  46.         }
  47.         while (carry > 0)
  48.         {
  49.             result._container.push_back(carry % 10);
  50.             carry /= 10;
  51.         }
  52.         return result;
  53.     }
  54.  
  55.     BigNumber operator-(const BigNumber& other)
  56.     {
  57.         BigNumber result(0);
  58.         if (this->operator<(other))
  59.         {
  60.             return result;
  61.         }
  62.         int carry = 0;
  63.         for (int i = 0; i < _container.size(); i++)
  64.         {
  65.             int subResult = (_container[i] - carry) - (i < other._container.size() ? other._container[i] : 0);
  66.             if (subResult < 0)
  67.             {
  68.                 subResult += 10;
  69.                 carry = 1;
  70.             }
  71.             else
  72.             {
  73.                 carry = 0;
  74.             }
  75.             result._container.push_back(subResult);
  76.         }
  77.         while (result._container.back() == 0 && result._container.size() > 1)
  78.         {
  79.             result._container.pop_back();
  80.         }
  81.         return result;
  82.     }
  83.  
  84.     BigNumber operator*(const BigNumber& other)
  85.     {
  86.         BigNumber result(0);
  87.         vector<int> min = _container.size() < other._container.size() ? this->_container : other._container;
  88.         vector<int> max = _container.size() < other._container.size() ? other._container : this->_container;
  89.  
  90.         for (int i = 0; i < min.size(); i++)
  91.         {
  92.             BigNumber sum(0);
  93.             int carry = 0;
  94.             for (int j = 0; j < i; j++)
  95.             {
  96.                 sum._container.push_back(0);
  97.             }
  98.             for (int j = 0; j < max.size(); j++)
  99.             {
  100.                 int mulRes = min[i] * max[j];
  101.                 sum._container.push_back((mulRes + carry) % 10);
  102.                 carry = (mulRes + carry) / 10;
  103.             }
  104.             while (carry > 0)
  105.             {
  106.                 sum._container.push_back(carry % 10);
  107.                 carry /= 10;
  108.             }
  109.             result = result + sum;
  110.         }
  111.         return result;
  112.     }
  113.  
  114.     BigNumber operator/(BigNumber& other) // a div b using the long division algorithm, b must be lower than MAX_INT so that I can use int division instead of repeated subtraction
  115.     {
  116.         BigNumber result = 0;
  117.         int dividend = other.to_int();
  118.         if (this->operator<(other))
  119.         {
  120.             return BigNumber(0);
  121.         }
  122.         int current = other._container.size();
  123.         BigNumber partial = this->subNumber(current);
  124.  
  125.         if (partial < other)
  126.         {
  127.             current++;
  128.             partial = (partial * BigNumber(10)) + BigNumber(_container[_container.size() - current]);
  129.         }
  130.  
  131.         while (current <= _container.size())
  132.         {
  133.             //add next digit
  134.             int val = partial.to_int() / dividend;
  135.             result._container.insert(result._container.begin(), val);
  136.             partial = partial - BigNumber(val * dividend);
  137.             current++;
  138.             if (current > _container.size())
  139.             {
  140.                 break;
  141.             }
  142.             partial = (partial * BigNumber(10)) + BigNumber(_container[_container.size() - current]);
  143.         }
  144.  
  145.         return result;
  146.     }
  147.  
  148.     BigNumber convertToBase(int base) // converts the number from base 10 to another base
  149.     {
  150.         BigNumber result;
  151.         BigNumber baseBig(base);
  152.  
  153.         BigNumber q = *this;
  154.         if (q < BigNumber(1))
  155.         {
  156.             return BigNumber(0);
  157.         }
  158.         BigNumber q2 = this -> operator/(baseBig);
  159.  
  160.         while (q > 0)
  161.         {
  162.             BigNumber r = q - (q2 * baseBig);
  163.             result._container.push_back(r.to_int());
  164.             q = q2;
  165.             q2 = q / baseBig;
  166.         }
  167.         return result;
  168.     }
  169.  
  170.     bool operator >(const BigNumber& other)
  171.     {
  172.         if (_container.size() != other._container.size())
  173.         {
  174.             return _container.size() > other._container.size();
  175.         }
  176.         else
  177.         {
  178.             for (int i = _container.size() - 1; i >= 0; i--)
  179.             {
  180.                 if (_container[i] == other._container[i])
  181.                 {
  182.                     continue;
  183.                 }
  184.                 if (_container[i] > other._container[i])
  185.                 {
  186.                     return true;
  187.                 }
  188.                 else
  189.                 {
  190.                     return false;
  191.                 }
  192.             }
  193.             return false;
  194.         }
  195.     }
  196.  
  197.     bool operator <(const BigNumber& other)
  198.     {
  199.         return !(this->operator> (other)) && !(this->operator==(other));
  200.     }
  201.  
  202.     bool operator ==(const BigNumber& other)
  203.     {
  204.         return _container == other._container;
  205.     }
  206.  
  207.     bool operator >=(const BigNumber& other)
  208.     {
  209.         return this->operator> (other) || this->operator== (other);
  210.     }
  211.     bool operator <=(const BigNumber& other)
  212.     {
  213.         return this->operator<(other) || this->operator==(other);
  214.     }
  215.  
  216.     int to_int()
  217.     {
  218.         int result = 0;
  219.         int p = 0;
  220.         for (int i = _container.size() - 1; i >= 0; i--)
  221.         {
  222.             result = result * 10 + _container[i];
  223.         }
  224.         return result;
  225.     }
  226. };
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