# Big integer multiply challenge

Mar 21st, 2019
903
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }