Advertisement
Bisqwit

Big integer multiply challenge

Mar 21st, 2019
1,095
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. #include <vector>
  2. #include <string>
  3. #include <iostream>
  4. #include <algorithm>
  5. class Big
  6. {
  7.     using Hand = unsigned long;
  8.     static constexpr unsigned HandBits = sizeof(Hand)*8;
  9.     std::vector<Hand> hands;
  10. public:
  11.     Big() : hands{} {}
  12.     Big(Hand val) : hands{val} {}
  13.     Big(std::string_view val) { for(char c: val) { *this *= 10; *this += Hand(c-'0'); } }
  14.     Big& operator>>=(unsigned n)
  15.     {
  16.         unsigned nwords = n/HandBits, c=nwords,d=c+1; n%=HandBits;
  17.         for(std::size_t a=0; a<hands.size(); ++a)
  18.             hands[a] = (((a+c) < hands.size() ? hands[a+c] : 0) >> n)
  19.                 | (n ? (((a+d) < hands.size() ? hands[a+d] : 0) << (HandBits-n)) : 0);
  20.         return *this;
  21.     }
  22.     template<typename F1,typename F2>
  23.     Big& SubAdd(const Big& b, F1 op,F2 comp)
  24.     {
  25.         hands.resize(std::max(hands.size(), b.hands.size()));
  26.         Hand carry = 0, orig;
  27.         for(std::size_t a=0; a<hands.size(); ++a)
  28.         {
  29.             hands[a] = op(orig = hands[a], b.hands[a] + carry);
  30.             carry = comp(hands[a], orig) || (hands[a]==orig && b.hands[a] != 0);
  31.         }
  32.         if(carry) hands.push_back(1);
  33.         return *this;
  34.     }
  35.     Big& operator-=(const Big& b) { return SubAdd(b, std::minus{}, std::greater{}); }
  36.     Big& operator+=(const Big& b) { return SubAdd(b, std::plus{}, std::less{}); }
  37.     bool operator<(const Big& b) const
  38.     {
  39.         return (Big(*this) -= b).hands.size() > std::max(hands.size(), b.hands.size());
  40.         //for(std::size_t n=std::max(hands.size(), b.hands.size()); n-- > 0; )
  41.         //    if(Hand x = (n<hands.size()?hands[n]:0), y = (n<b.hands.size()?b.hands[n]:0);
  42.         //       x != y) return x < y;
  43.         //return false;
  44.     }
  45.     Big& operator*=(const Big& b)
  46.     {
  47.         for(Big a=std::move(*this), c=b; Big{} < a; a>>=1, c+=c) { if(a.hands[0]&1) *this += c; }
  48.         return *this;
  49.     }
  50.     static Big DivMod(Big& result, Big&& divisor)
  51.     {
  52.         for(Big remain = std::move(result), multiple=1; ; divisor+=divisor,multiple+=multiple)
  53.             if(!(divisor < remain))
  54.             {
  55.                 do if(!(remain < divisor)) { remain -= divisor; result += multiple; }
  56.                 while(divisor>>=1, Big{} < (multiple>>=1));
  57.                 return remain;
  58.             }
  59.     }
  60.     std::string to_string() const
  61.     {
  62.         std::string str;
  63.         Big value = *this, remain;
  64.         while(Big{} < value) { str.insert(0, 1, '0' + (remain = DivMod(value, 10)).hands[0]); }
  65.         if(str.empty()) str += '0';
  66.         return str;
  67.     }
  68. };
  69. int main(int argc, char** argv)
  70. {
  71.     Big a(argv[1]), b(argv[2]);
  72.     a *= b;
  73.     std::cout << a.to_string() << '\n';
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement