src/math/ds/mpi/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../conv/add/u128/lib.hpp" | ||
| 4 | #include "../../../fast/s2u/u32/lib.hpp" | ||
| 5 | #include "../../../util/strip/lib.hpp" | ||
| 6 | #include "../../../util/traits/others/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | |||
| 10 | struct mpi : vecu { | ||
| 11 | static CEXP u32 D = 1e8, lgD = 8, sqrtD = 1e4; | ||
| 12 | static_assert(sqrtD * sqrtD == D); | ||
| 13 | static CEXP u32 hex_lgD = 6, hex_D = 1u << 24; | ||
| 14 | |||
| 15 | private: | ||
| 16 | static CEXP arr<u32, hex_lgD + 1> hex_pow = {1u, 16u, 256u, 4096u, 65536u, 1048576u, hex_D}; | ||
| 17 | struct ict4 { | ||
| 18 | CEXP static auto num = [] { | ||
| 19 | arr<u32, sqrtD> num; | ||
| 20 | for (u32 e0 = (48 << 0), j = 0; e0 < (58 << 0); e0 += (1 << 0)) | ||
| 21 | for (u32 e1 = (48 << 8); e1 < (58 << 8); e1 += (1 << 8)) | ||
| 22 | for (u32 e2 = (48 << 16); e2 < (58 << 16); e2 += (1 << 16)) | ||
| 23 | for (u32 e3 = (48 << 24); e3 < (58 << 24); e3 += (1 << 24)) num[j++] = e0 ^ e1 ^ e2 ^ e3; | ||
| 24 | return num; | ||
| 25 | }(); | ||
| 26 | 44649796 | static auto get(u32 x) NE { return (chr CP)(num.data() + x); } | |
| 27 | }; | ||
| 28 | |||
| 29 | bool neg = false, hmd_ = false; | ||
| 30 | vecu hbits_; | ||
| 31 | |||
| 32 | #define vec_like std::derived_from<vecu> auto | ||
| 33 | // name starts with u ==> ignore sign | ||
| 34 | 2004552 | static CEXP auto ucmp(vec_like CR a, vec_like CR b) NE { | |
| 35 |
10/12auto tifa_libs::mpi::ucmp<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 2 taken 166379 times.
✓ Branch 3 taken 1569923 times.
✓ Branch 6 taken 166379 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 155368 times.
✓ Branch 9 taken 11011 times.
auto tifa_libs::mpi::ucmp<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 2 taken 170576 times.
✓ Branch 3 taken 97674 times.
✓ Branch 6 taken 170576 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 115537 times.
✓ Branch 9 taken 55039 times.
|
2004552 | if (a.size() != b.size()) return a.size() <=> b.size(); |
| 36 | 1667597 | return std::lexicographical_compare_three_way(a.rbegin(), a.rend(), b.rbegin(), b.rend()); | |
| 37 | } | ||
| 38 | 179 | static CEXP auto cmp(mpi CR a, mpi CR b) NE { | |
| 39 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 179 times.
|
179 | if (a.neg) { |
| 40 | ✗ | retif_((b.neg), ucmp(b, a), std::strong_ordering::less); | |
| 41 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 179 times.
|
179 | } else retif_((b.neg), std::strong_ordering::greater, ucmp(a, b)); |
| 42 | } | ||
| 43 | 20801316 | static CEXP bool is_0(vec_like CR a) NE { return a.empty(); } | |
| 44 |
8/8bool tifa_libs::mpi::is_pm1<std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 519119 times.
✓ Branch 2 taken 520347 times.
✓ Branch 4 taken 13601 times.
✓ Branch 5 taken 505518 times.
bool tifa_libs::mpi::is_pm1<tifa_libs::mpi>(tifa_libs::mpi const&):
✓ Branch 1 taken 3079171 times.
✓ Branch 2 taken 3225663 times.
✓ Branch 4 taken 804783 times.
✓ Branch 5 taken 2274388 times.
|
7344300 | static CEXP bool is_pm1(vec_like CR a) NE { return a.size() == 1 && a[0] == 1; } |
| 45 | static CEXP bool is_1(mpi CR a) NE { return !a.neg && is_pm1(a); } | ||
| 46 | 5106897 | static CEXP void shrink_(vec_like& a) NE { | |
| 47 | 21449731 | auto [_, r] = rstrip_view(a, [](u32 x) { return !x; }); | |
| 48 | 5106897 | a.erase(r, a.end()); | |
| 49 | 5106897 | } | |
| 50 | template <int_c T> | ||
| 51 | 2759088 | static CEXP vecu int2vecu(T x) NE { | |
| 52 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2759088 times.
|
2759088 | if CEXP (sint_c<T>) assert(x >= 0); |
| 53 | 2759088 | vecu res; | |
| 54 |
2/2✓ Branch 1 taken 2296245 times.
✓ Branch 2 taken 2759088 times.
|
5055333 | while (x) res.push_back(u32(x % D)), x /= D; |
| 55 | 2759088 | return res; | |
| 56 | } | ||
| 57 | 1413639 | static CEXP i64 uvec2i64(vec_like CR a) NE { | |
| 58 | 1413639 | i64 res = 0; | |
| 59 |
4/4long tifa_libs::mpi::uvec2i64<std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 2 taken 2984 times.
✓ Branch 3 taken 2896 times.
long tifa_libs::mpi::uvec2i64<tifa_libs::mpi>(tifa_libs::mpi const&):
✓ Branch 2 taken 1693720 times.
✓ Branch 3 taken 1410743 times.
|
3110343 | for (u32 i = (u32)a.size() - 1; ~i; --i) res = res * D + a[i]; |
| 60 | 1413639 | return res; | |
| 61 | } | ||
| 62 | |||
| 63 | public: | ||
| 64 | 5582641 | CEXP mpi() NE = default; | |
| 65 | CEXP mpi(bool n, itlu x) NE : vecu(x), neg(n) {} | ||
| 66 | 22588995 | CEXP mpi(bool n, spnu d) NE : vecu(d.begin(), d.end()), neg(n) {} | |
| 67 | template <int_c T> | ||
| 68 | 1834365 | CEXP mpi(T x) NE : mpi() { | |
| 69 | if CEXP (sint_c<T>) | ||
| 70 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 917396 times.
|
917396 | if (x < 0) neg = true, x = -x; |
| 71 |
6/6tifa_libs::mpi::mpi<int>(int):
✓ Branch 1 taken 917396 times.
✓ Branch 2 taken 917396 times.
tifa_libs::mpi::mpi<unsigned int>(unsigned int):
✓ Branch 1 taken 65 times.
✓ Branch 2 taken 65 times.
tifa_libs::mpi::mpi<unsigned long>(unsigned long):
✓ Branch 1 taken 916896 times.
✓ Branch 2 taken 916904 times.
|
3668722 | while (x) push_back(u32(to_uint_t<T>(x) % D)), x /= (T)D; |
| 72 | 1834365 | } | |
| 73 | 3748276 | CEXP mpi(strn s) NE : mpi() { | |
| 74 |
3/4✗ Branch 1 not taken.
✓ Branch 2 taken 3748276 times.
✓ Branch 5 taken 194630 times.
✓ Branch 6 taken 3553646 times.
|
3748276 | if (assert(!s.empty()); s.size() == 1u) { |
| 75 |
2/2✓ Branch 1 taken 18083 times.
✓ Branch 2 taken 176547 times.
|
371177 | if (s[0] == '0') return; |
| 76 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 176547 times.
|
176547 | assert(isdigit(s[0])), push_back(s[0] & 15); |
| 77 | 176547 | return; | |
| 78 | } | ||
| 79 | 3553646 | u32 l = 0; | |
| 80 |
2/2✓ Branch 1 taken 453449 times.
✓ Branch 2 taken 3100197 times.
|
3553646 | if (s[0] == '-') ++l, neg = true; |
| 81 | 3553646 | u32 _ = 0; | |
| 82 |
2/2✓ Branch 1 taken 3299712 times.
✓ Branch 2 taken 253934 times.
|
3553646 | if (cu32 ofs = u32(s.size() - l) & 7; ofs) { |
| 83 |
2/2✓ Branch 1 taken 11463270 times.
✓ Branch 2 taken 3299712 times.
|
14762982 | flt_ (u32, i, l, l + ofs) _ = _ * 10 + (s[i] & 15); |
| 84 | 3299712 | l += ofs; | |
| 85 | } | ||
| 86 |
2/2✓ Branch 0 taken 3350697 times.
✓ Branch 1 taken 202949 times.
|
3553646 | if (l) s = s.substr(l); |
| 87 |
2/2✓ Branch 1 taken 31170774 times.
✓ Branch 2 taken 3553646 times.
|
34724420 | for (u32 ie = (u32)s.size(); ie >= lgD; ie -= lgD) |
| 88 | 31170774 | push_back(str2uint_si64(s.data() + ie - lgD)); | |
| 89 |
2/2✓ Branch 0 taken 3299712 times.
✓ Branch 1 taken 253934 times.
|
3553646 | if (_) push_back(_); |
| 90 | } | ||
| 91 | 3016452 | CEXP static mpi from_hex_str(strn s) NE { | |
| 92 | 3016452 | mpi res; | |
| 93 | 3016452 | res.hmd_ = true; | |
| 94 |
7/8✗ Branch 1 not taken.
✓ Branch 2 taken 3016452 times.
✓ Branch 5 taken 111346 times.
✓ Branch 6 taken 2905106 times.
✓ Branch 8 taken 8842 times.
✓ Branch 9 taken 102504 times.
✓ Branch 10 taken 8842 times.
✓ Branch 11 taken 3007610 times.
|
3016452 | if (assert(!s.empty()); s.size() == 1u && s[0] == '0') return res; |
| 95 | 3007610 | u32 l = 0; | |
| 96 |
2/2✓ Branch 1 taken 373235 times.
✓ Branch 2 taken 2634375 times.
|
3007610 | if (s[0] == '-') ++l, res.neg = true; |
| 97 |
4/10✓ Branch 1 taken 2885882 times.
✓ Branch 2 taken 121728 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2885882 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✓ Branch 13 taken 3007610 times.
|
3007610 | if (l + 1 < s.size() && s[l] == '0' && (s[l + 1] == 'x' || s[l + 1] == 'X')) l += 2; |
| 98 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3007610 times.
|
3007610 | assert(l < s.size()); |
| 99 |
2/2✓ Branch 1 taken 28702271 times.
✓ Branch 2 taken 3007610 times.
|
31709881 | for (u32 r = (u32)s.size(); l < r;) { |
| 100 |
2/2✓ Branch 0 taken 25736056 times.
✓ Branch 1 taken 2966215 times.
|
28702271 | cu32 is = r > lgD ? r - lgD : l; |
| 101 | 28702271 | u32 x = 0; | |
| 102 |
2/2✓ Branch 2 taken 217250236 times.
✓ Branch 3 taken 28702271 times.
|
245952507 | flt_ (u32, i, is, r) x = (x << 4) | hex_to_u32_(s[i]); |
| 103 | 28702271 | res.hbits_.push_back(x), r = is; | |
| 104 | } | ||
| 105 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 3007610 times.
|
3007610 | if (h_shrink_(res.hbits_); res.hbits_.empty()) res.neg = false; |
| 106 | 3007610 | return res; | |
| 107 | } | ||
| 108 | |||
| 109 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
|
20 | CEXP void set_neg(bool s) NE { neg = is_zero() ? false : s; } |
| 110 | 20 | ND CEXP bool is_neg() CNE { return neg; } | |
| 111 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3288218 times.
|
3288218 | ND CEXP bool is_zero() CNE { return hmd_ ? hbits_.empty() : is_0(*this); } |
| 112 | CEXP void shrink() NE { | ||
| 113 | if (hmd_) h_shrink_(hbits_); | ||
| 114 | else shrink_(*this); | ||
| 115 | if (is_zero()) neg = false; | ||
| 116 | } | ||
| 117 | ✗ | friend CEXP mpi abs(mpi m) NE { | |
| 118 | ✗ | m.neg = false; | |
| 119 | ✗ | return m; | |
| 120 | } | ||
| 121 | |||
| 122 | 1358347 | friend CEXP mpi operator+(mpi CR l, mpi CR r) NE { | |
| 123 |
3/4✓ Branch 0 taken 201242 times.
✓ Branch 1 taken 1157105 times.
✓ Branch 2 taken 201242 times.
✗ Branch 3 not taken.
|
1358347 | if (l.hmd_ && r.hmd_) { |
| 124 |
2/2✓ Branch 0 taken 96419 times.
✓ Branch 1 taken 104823 times.
|
201242 | if (l.neg == r.neg) return make_hex_(l.neg, h_add_(l.hbits_, r.hbits_)); |
| 125 | 104823 | ci32 ccmp = h_cmp_mag_(l.hbits_, r.hbits_); | |
| 126 |
2/2✓ Branch 0 taken 2537 times.
✓ Branch 1 taken 102286 times.
|
104823 | if (!ccmp) return make_hex_(false, {}); |
| 127 |
2/2✓ Branch 0 taken 49964 times.
✓ Branch 1 taken 52322 times.
|
102286 | if (ccmp < 0) { |
| 128 | 49964 | auto c = h_sub_(r.hbits_, l.hbits_); | |
| 129 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 49964 times.
|
49964 | bool const n = c.empty() ? false : r.neg; |
| 130 | 49964 | return make_hex_(n, std::move(c)); | |
| 131 | 49964 | } | |
| 132 | 52322 | auto c = h_sub_(l.hbits_, r.hbits_); | |
| 133 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 52322 times.
|
52322 | bool const n = c.empty() ? false : l.neg; |
| 134 | 52322 | return make_hex_(n, std::move(c)); | |
| 135 | 52322 | } | |
| 136 | 1157105 | auto ld = l.as_dec_(), rd = r.as_dec_(); | |
| 137 |
2/2✓ Branch 0 taken 1032017 times.
✓ Branch 1 taken 125088 times.
|
1157105 | if (ld.neg == rd.neg) return {ld.neg, uadd(ld, rd)}; |
| 138 |
2/2✓ Branch 3 taken 63462 times.
✓ Branch 4 taken 61626 times.
|
125088 | if (std::is_lteq(ucmp(ld, rd))) { |
| 139 | 63462 | auto c = usub(rd, ld); | |
| 140 |
2/2✓ Branch 1 taken 1539 times.
✓ Branch 2 taken 61923 times.
|
63462 | return {is_0(c) ? false : rd.neg, c}; |
| 141 | 63462 | } | |
| 142 | 61626 | auto c = usub(ld, rd); | |
| 143 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 61626 times.
|
61626 | return {is_0(c) ? false : ld.neg, c}; |
| 144 | 1157105 | } | |
| 145 | 173 | friend CEXP mpi operator-(mpi CR l, mpi CR r) NE { return l + (-r); } | |
| 146 | 3727188 | friend CEXP mpi operator*(mpi CR l, mpi CR r) NE { | |
| 147 |
3/4✓ Branch 0 taken 183088 times.
✓ Branch 1 taken 3544100 times.
✓ Branch 2 taken 183088 times.
✗ Branch 3 not taken.
|
3727188 | if (l.hmd_ && r.hmd_) { |
| 148 | 183088 | auto c = h_mul_(l.hbits_, r.hbits_); | |
| 149 |
2/2✓ Branch 1 taken 7423 times.
✓ Branch 2 taken 175665 times.
|
183088 | bool const n = c.empty() ? false : bool(l.neg ^ r.neg); |
| 150 | 183088 | return make_hex_(n, std::move(c)); | |
| 151 | 183088 | } | |
| 152 | 3544100 | auto ld = l.as_dec_(), rd = r.as_dec_(); | |
| 153 | 3544100 | auto c = umul(ld, rd); | |
| 154 |
2/2✓ Branch 1 taken 10300 times.
✓ Branch 2 taken 3533800 times.
|
3544100 | bool const n = is_0(c) ? false : (ld.neg ^ rd.neg); |
| 155 | 3544100 | return {n, c}; | |
| 156 | 3544100 | } | |
| 157 | 2538126 | friend CEXP ptt<mpi> divmod(mpi CR l, mpi CR r) NE { | |
| 158 |
3/4✓ Branch 0 taken 1123896 times.
✓ Branch 1 taken 1414230 times.
✓ Branch 2 taken 1123896 times.
✗ Branch 3 not taken.
|
2538126 | if (l.hmd_ && r.hmd_) { |
| 159 | 1123896 | const auto dm = h_divmod_(l.hbits_, r.hbits_); | |
| 160 |
4/4✓ Branch 1 taken 533429 times.
✓ Branch 2 taken 590467 times.
✓ Branch 4 taken 66491 times.
✓ Branch 5 taken 1057405 times.
|
1123896 | const bool qn = dm.first.empty() ? false : (l.neg != r.neg), rn = dm.second.empty() ? false : l.neg; |
| 161 | 1123896 | return {make_hex_(qn, dm.first), make_hex_(rn, dm.second)}; | |
| 162 | 1123896 | } | |
| 163 | 1414230 | auto ld = l.as_dec_(), rd = r.as_dec_(); | |
| 164 | 1414230 | auto dm = udivmod(ld, rd); | |
| 165 |
4/4✓ Branch 1 taken 387203 times.
✓ Branch 2 taken 1027027 times.
✓ Branch 6 taken 133125 times.
✓ Branch 7 taken 1281105 times.
|
1414230 | return {mpi{is_0(dm.first) ? false : ld.neg != rd.neg, dm.first}, mpi{is_0(dm.second) ? false : ld.neg, dm.second}}; |
| 166 | 1414230 | } | |
| 167 | 288 | friend CEXP mpi operator/(mpi CR l, mpi CR r) NE { return divmod(l, r).first; } | |
| 168 | 50 | friend CEXP mpi operator%(mpi CR l, mpi CR r) NE { return divmod(l, r).second; } | |
| 169 | 916808 | CEXP mpi& operator+=(mpi CR r) NE { return (*this) = (*this) + r; } | |
| 170 | CEXP mpi& operator-=(mpi CR r) NE { return (*this) = (*this) - r; } | ||
| 171 | 71 | CEXP mpi& operator*=(mpi CR r) NE { return (*this) = (*this) * r; } | |
| 172 | CEXP mpi& operator/=(mpi CR r) NE { return (*this) = (*this) / r; } | ||
| 173 | CEXP mpi& operator%=(mpi CR r) NE { return (*this) = (*this) % r; } | ||
| 174 | 173 | CEXP mpi operator-() CNE { | |
| 175 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 171 times.
|
173 | if (is_zero()) return *this; |
| 176 | 171 | auto ret = *this; | |
| 177 | 171 | ret.neg = !ret.neg; | |
| 178 | 171 | return ret; | |
| 179 | 171 | } | |
| 180 | CEXP mpi operator+() CNE { return *this; } | ||
| 181 | 179 | friend CEXP auto operator<=>(mpi CR l, mpi CR r) NE { | |
| 182 |
1/4✗ Branch 0 not taken.
✓ Branch 1 taken 179 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
179 | if (l.hmd_ && r.hmd_) { |
| 183 | ✗ | if (l.neg != r.neg) return l.neg ? std::strong_ordering::less : std::strong_ordering::greater; | |
| 184 | ✗ | if (h_eq_(l.hbits_, r.hbits_)) return std::strong_ordering::equal; | |
| 185 | ✗ | return l.neg ^ h_lt_(l.hbits_, r.hbits_) ? std::strong_ordering::less : std::strong_ordering::greater; | |
| 186 | } | ||
| 187 | 179 | return cmp(l.as_dec_(), r.as_dec_()); | |
| 188 | } | ||
| 189 | 96 | friend CEXP bool operator==(mpi CR l, mpi CR r) NE { return std::is_eq(l <=> r); } | |
| 190 | |||
| 191 | 3288025 | ND CEXP strn to_str() CNE { | |
| 192 |
2/2✓ Branch 1 taken 531842 times.
✓ Branch 2 taken 2756183 times.
|
4351709 | if (is_zero()) return "0"; |
| 193 | 2756183 | strn r; | |
| 194 |
2/2✓ Branch 2 taken 223937 times.
✓ Branch 3 taken 2532246 times.
|
2756183 | if (r.reserve(size() * 8 + 1); neg) r.push_back('-'); |
| 195 | // NOLINTNEXTLINE(modernize-avoid-c-arrays) | ||
| 196 | chr int_buf[11]; | ||
| 197 | 2756183 | auto res = std::to_chars(int_buf, int_buf + 11, back()); | |
| 198 | 2756183 | r.append(int_buf, u32(res.ptr - int_buf)); | |
| 199 |
2/2✓ Branch 7 taken 22324898 times.
✓ Branch 8 taken 2756183 times.
|
25081081 | for (u32 i = (u32)size() - 2; ~i; --i) r.append(ict4::get((*this)[i] / 10000u), 4), r.append(ict4::get((*this)[i] % 10000u), 4); |
| 200 | 2756183 | return r; | |
| 201 | 2756183 | } | |
| 202 | 2632122 | ND CEXP strn to_hex_str() CNE { | |
| 203 |
1/2✓ Branch 0 taken 2632122 times.
✗ Branch 1 not taken.
|
2632122 | if (hmd_) { |
| 204 |
2/2✓ Branch 1 taken 609882 times.
✓ Branch 2 taken 2022240 times.
|
3851886 | if (hbits_.empty()) return "0"; |
| 205 | 2022240 | strn res; | |
| 206 |
2/2✓ Branch 0 taken 184421 times.
✓ Branch 1 taken 1837819 times.
|
2022240 | if (neg) res.push_back('-'); |
| 207 |
2/2✓ Branch 6 taken 20126699 times.
✓ Branch 7 taken 2022240 times.
|
22148939 | for (u32 i = (u32)hbits_.size() - 1; ~i; --i) res += h_u32_to_hex_(hbits_[i], i + 1 != hbits_.size()); |
| 208 | 2022240 | return res; | |
| 209 | 2022240 | } | |
| 210 | ✗ | if (is_zero()) return "0"; | |
| 211 | ✗ | mpi x = abs(*this); | |
| 212 | ✗ | vecu rems; | |
| 213 | ✗ | rems.reserve((x.size() * 27 + 23) / 24); | |
| 214 | ✗ | while (!x.is_zero()) { | |
| 215 | ✗ | auto [q, r] = udivmod_1e8(x, vecu{hex_D}); | |
| 216 | ✗ | x = mpi{false, q}, rems.push_back(r.empty() ? 0 : r[0]); | |
| 217 | ✗ | } | |
| 218 | ✗ | strn res; | |
| 219 | ✗ | if (res.reserve(neg + rems.size() * hex_lgD); neg) res.push_back('-'); | |
| 220 | ✗ | res += u32_to_hex_(rems.back(), false); | |
| 221 | ✗ | for (u32 i = (u32)rems.size() - 1; i; --i) res += u32_to_hex_(rems[i - 1], true); | |
| 222 | ✗ | return res; | |
| 223 | ✗ | } | |
| 224 | ND CEXP mpi as_mpi() CNE { return *this; } | ||
| 225 | ✗ | ND CEXP i64 to_i64() CNE { retif_((ci64 res = uvec2i64(*this); neg), -res, res); } | |
| 226 | ND CEXP i128 to_i128() CNE { | ||
| 227 | i128 res = 0; | ||
| 228 | for (u32 i = (u32)size() - 1; ~i; --i) res = res * D + (*this)[i]; | ||
| 229 | retif_((neg), -res, res); | ||
| 230 | } | ||
| 231 | 3748266 | friend auto& operator>>(istream_c auto& is, mpi& m) NE { | |
| 232 | 3748266 | strn s; | |
| 233 | 3748266 | is >> s, m = mpi{s}; | |
| 234 | 7496532 | return is; | |
| 235 | 3748266 | } | |
| 236 | 3288025 | friend auto& operator<<(ostream_c auto& os, mpi CR m) NE { return os << m.to_str(); } | |
| 237 | |||
| 238 | private: | ||
| 239 | 2632122 | static CEXP mpi make_hex_(bool n, vecu bits) NE { | |
| 240 | 2632122 | mpi x; | |
| 241 |
2/2✓ Branch 4 taken 609882 times.
✓ Branch 5 taken 2022240 times.
|
2632122 | x.hmd_ = true, x.hbits_ = std::move(bits), h_shrink_(x.hbits_), x.neg = x.hbits_.empty() ? false : n; |
| 242 | 2632122 | return x; | |
| 243 | 2022240 | } | |
| 244 | 12231228 | ND CEXP mpi as_dec_() CNE { | |
| 245 |
1/2✓ Branch 0 taken 12231228 times.
✗ Branch 1 not taken.
|
12231228 | if (!hmd_) return *this; |
| 246 | ✗ | mpi r; | |
| 247 | ✗ | r.neg = neg; | |
| 248 | ✗ | for (u32 i = (u32)hbits_.size() - 1; ~i; --i) umuladd_(r, 65536u, 0), umuladd_(r, 65536u, hbits_[i] >> 16), umuladd_(r, 65536u, hbits_[i] & 65535u); | |
| 249 | ✗ | if (r.empty()) r.neg = false; | |
| 250 | ✗ | return r; | |
| 251 | ✗ | } | |
| 252 | |||
| 253 | 217250236 | static CEXP u32 hex_to_u32_(chr c) NE { return (c & 15) + ((c & 64) >> 6) * 9; } | |
| 254 | ✗ | static CEXP strn u32_to_hex_(u32 x, bool pad0) NE { | |
| 255 | arr<chr, hex_lgD> buf; | ||
| 256 | ✗ | flt_ (u32, i, 0, hex_lgD) { | |
| 257 | ✗ | cu32 d = x & 15; | |
| 258 | ✗ | buf[hex_lgD - 1 - i] = chr(d + (d < 10 ? 48 : 55)), x >>= 4; | |
| 259 | } | ||
| 260 | ✗ | if (pad0) return {buf.begin(), buf.end()}; | |
| 261 | ✗ | u32 l = 0; | |
| 262 | ✗ | while (l + 1 < hex_lgD && buf[l] == '0') ++l; | |
| 263 | ✗ | return {buf.begin() + l, buf.end()}; | |
| 264 | } | ||
| 265 | 20126699 | static CEXP strn h_u32_to_hex_(u32 x, bool pad0) NE { | |
| 266 | 20126699 | strn res; | |
| 267 | 20126699 | res.reserve(8); | |
| 268 |
2/2✓ Branch 0 taken 161013592 times.
✓ Branch 1 taken 20126699 times.
|
181140291 | flt_ (u32, _, 0, 8) { |
| 269 | 161013592 | cu32 d = x & 15; | |
| 270 |
2/2✓ Branch 0 taken 104253575 times.
✓ Branch 1 taken 56760017 times.
|
161013592 | res.push_back(chr(d + (d < 10 ? 48 : 55))), x >>= 4; |
| 271 | } | ||
| 272 |
2/2✓ Branch 0 taken 2022240 times.
✓ Branch 1 taken 18104459 times.
|
20126699 | if (!pad0) { |
| 273 |
5/6✓ Branch 2 taken 12711369 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 10689129 times.
✓ Branch 6 taken 2022240 times.
✓ Branch 7 taken 10689129 times.
✓ Branch 8 taken 2022240 times.
|
12711369 | while (!res.empty() && res.back() == '0') res.pop_back(); |
| 274 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2022240 times.
|
2022240 | if (res.empty()) res.push_back('0'); |
| 275 | } | ||
| 276 | 20126699 | reverse(res); | |
| 277 | 20126699 | return res; | |
| 278 | } | ||
| 279 | ✗ | static CEXP void umuladd_(vecu& a, u32 mul, u32 add) NE { | |
| 280 | ✗ | if (a.empty() && !add) return; | |
| 281 | ✗ | u64 carry = add; | |
| 282 | ✗ | flt_ (u32, i, 0, (u32)a.size()) a[i] = u32((carry += (u64)a[i] * mul) % D), carry /= D; | |
| 283 | ✗ | while (carry) a.push_back(u32(carry % D)), carry /= D; | |
| 284 | } | ||
| 285 | |||
| 286 | using iter = u32*; | ||
| 287 | using citer = u32 CP; | ||
| 288 | |||
| 289 | 28318048 | static CEXP usz h_nz_size_(vecu CR a) NE { | |
| 290 | 28318048 | usz n = a.size(); | |
| 291 |
6/6✓ Branch 0 taken 28340047 times.
✓ Branch 1 taken 6533 times.
✓ Branch 3 taken 28532 times.
✓ Branch 4 taken 28311515 times.
✓ Branch 5 taken 28532 times.
✓ Branch 6 taken 28318048 times.
|
28346580 | while (n && !a[n - 1]) --n; |
| 292 | 28318048 | return n; | |
| 293 | } | ||
| 294 | 5509648 | static CEXP bool h_eq_(vecu CR a, vecu CR b) NE { | |
| 295 | 5509648 | usz const asz = h_nz_size_(a); | |
| 296 |
2/2✓ Branch 1 taken 816955 times.
✓ Branch 2 taken 4692693 times.
|
5509648 | if (asz != h_nz_size_(b)) return false; |
| 297 |
2/2✓ Branch 0 taken 5621420 times.
✓ Branch 1 taken 5709 times.
|
5627129 | flt_ (usz, i, 0, asz) |
| 298 |
2/2✓ Branch 2 taken 4686984 times.
✓ Branch 3 taken 934436 times.
|
5621420 | if (a[i] != b[i]) return false; |
| 299 | 5709 | return true; | |
| 300 | } | ||
| 301 | 6076197 | static CEXP bool h_is0_(vecu CR a) NE { return a.empty(); } | |
| 302 |
4/4✓ Branch 1 taken 2437839 times.
✓ Branch 2 taken 2502731 times.
✓ Branch 4 taken 1942 times.
✓ Branch 5 taken 2435897 times.
|
4940570 | static CEXP bool h_is_one_(vecu CR a) NE { return a.size() == 1 && a[0] == 1; } |
| 303 | 17948259 | static CEXP void h_shrink_(vecu& a) NE { | |
| 304 |
6/6✓ Branch 2 taken 34693445 times.
✓ Branch 3 taken 1331839 times.
✓ Branch 5 taken 18077025 times.
✓ Branch 6 taken 16616420 times.
✓ Branch 7 taken 18077025 times.
✓ Branch 8 taken 17948259 times.
|
36025284 | while (!a.empty() && !a.back()) a.pop_back(); |
| 305 | 17948259 | } | |
| 306 | 342062 | static CEXP bool h_lt_(citer a, citer a_end, citer b, citer b_end) NE { | |
| 307 | 342062 | usz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 308 |
2/2✓ Branch 0 taken 213137 times.
✓ Branch 1 taken 128925 times.
|
342062 | if (asz != bsz) { |
| 309 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 213137 times.
|
213137 | if (asz < bsz) { |
| 310 | ✗ | if (find_if(b + asz, b_end, [](u32 x) { return x; }) != b_end) return true; | |
| 311 | } else { | ||
| 312 |
2/2✓ Branch 1 taken 68952 times.
✓ Branch 2 taken 144185 times.
|
682031 | if (find_if(a + bsz, a_end, [](u32 x) { return x; }) != a_end) return false; |
| 313 | 144185 | asz = bsz; | |
| 314 | } | ||
| 315 | } | ||
| 316 |
2/2✓ Branch 0 taken 2804295 times.
✓ Branch 1 taken 8490 times.
|
2812785 | for (usz i = asz - 1; ~i; --i) |
| 317 |
2/2✓ Branch 0 taken 264620 times.
✓ Branch 1 taken 2539675 times.
|
2804295 | if (a[i] != b[i]) return a[i] < b[i]; |
| 318 | 8490 | return false; | |
| 319 | } | ||
| 320 | 8544553 | static CEXP bool h_lt_(vecu CR a, vecu CR b) NE { | |
| 321 | 8544553 | cusz asz = h_nz_size_(a), bsz = h_nz_size_(b); | |
| 322 |
2/2✓ Branch 0 taken 818043 times.
✓ Branch 1 taken 7726510 times.
|
8544553 | if (asz != bsz) return asz < bsz; |
| 323 |
2/2✓ Branch 0 taken 13447435 times.
✓ Branch 1 taken 2361 times.
|
13449796 | for (usz i = asz - 1; ~i; --i) |
| 324 |
2/2✓ Branch 2 taken 7724149 times.
✓ Branch 3 taken 5723286 times.
|
13447435 | if (a[i] != b[i]) return a[i] < b[i]; |
| 325 | 2361 | return false; | |
| 326 | } | ||
| 327 |
4/4✓ Branch 1 taken 5503939 times.
✓ Branch 2 taken 5709 times.
✓ Branch 4 taken 3145131 times.
✓ Branch 5 taken 2358808 times.
|
5509648 | static CEXP bool h_leq_(vecu CR a, vecu CR b) NE { return h_eq_(a, b) || h_lt_(a, b); } |
| 328 | 104823 | static CEXP i32 h_cmp_mag_(vecu CR a, vecu CR b) NE { | |
| 329 | 104823 | cusz asz = h_nz_size_(a), bsz = h_nz_size_(b); | |
| 330 |
2/2✓ Branch 0 taken 64077 times.
✓ Branch 1 taken 40746 times.
|
104823 | if (asz != bsz) { |
| 331 |
2/2✓ Branch 0 taken 30808 times.
✓ Branch 1 taken 33269 times.
|
64077 | retif_((asz < bsz), -1, 1); |
| 332 | } | ||
| 333 |
2/2✓ Branch 0 taken 238842 times.
✓ Branch 1 taken 2537 times.
|
241379 | for (usz i = asz - 1; ~i; --i) |
| 334 |
2/2✓ Branch 2 taken 38209 times.
✓ Branch 3 taken 200633 times.
|
238842 | if (a[i] != b[i]) { |
| 335 |
2/2✓ Branch 2 taken 19156 times.
✓ Branch 3 taken 19053 times.
|
38209 | retif_((a[i] < b[i]), -1, 1); |
| 336 | } | ||
| 337 | 2537 | return 0; | |
| 338 | } | ||
| 339 | |||
| 340 | 3560835 | static CEXP void h_add_(citer a, citer a_end, citer b, citer b_end, iter c, iter c_end) NE { | |
| 341 |
2/2✓ Branch 0 taken 28896 times.
✓ Branch 1 taken 3531939 times.
|
3560835 | if (a_end - a < b_end - b) std::swap(a, b), std::swap(a_end, b_end); |
| 342 | 3560835 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 343 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3560835 times.
|
3560835 | assert(std::cmp_less_equal(asz, c_end - c)); |
| 344 | 3560835 | u32 carry = 0; | |
| 345 | u64 v; | ||
| 346 |
2/2✓ Branch 0 taken 586721813 times.
✓ Branch 1 taken 3560835 times.
|
590282648 | flt_ (usz, i, 0, bsz) c[i] = u32(v = (u64)a[i] + b[i] + carry), carry = u32(v >> 32); |
| 347 |
2/2✓ Branch 0 taken 3150151 times.
✓ Branch 1 taken 3560835 times.
|
6710986 | flt_ (usz, i, bsz, asz) c[i] = u32(v = (u64)a[i] + carry), carry = u32(v >> 32); |
| 348 |
2/2✓ Branch 0 taken 540846 times.
✓ Branch 1 taken 3019989 times.
|
3560835 | if (carry) c[asz] = carry; |
| 349 | 3560835 | } | |
| 350 | 1766100 | static CEXP void h_add_(iter a, iter a_end, citer b, citer b_end) NE { | |
| 351 | 1766100 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 352 | 1766100 | u32 carry = 0; | |
| 353 | u64 v; | ||
| 354 |
2/2✓ Branch 0 taken 590802317 times.
✓ Branch 1 taken 1766100 times.
|
592568417 | flt_ (usz, i, 0, bsz) a[i] = u32(v = (u64)a[i] + b[i] + carry), carry = u32(v >> 32); |
| 355 |
3/4✓ Branch 0 taken 693859 times.
✓ Branch 1 taken 1766100 times.
✓ Branch 2 taken 693859 times.
✗ Branch 3 not taken.
|
2459959 | for (usz i = bsz; carry && i < asz; ++i) a[i] = u32(v = (u64)a[i] + carry), carry = u32(v >> 32); |
| 356 | 1766100 | } | |
| 357 | 96419 | static CEXP vecu h_add_(vecu CR a, vecu CR b) NE { | |
| 358 | 96419 | vecu c(max(a.size(), b.size()) + 1); | |
| 359 | 96419 | h_add_(a.data(), a.data() + a.size(), b.data(), b.data() + b.size(), c.data(), c.data() + c.size()), h_shrink_(c); | |
| 360 | 96419 | return c; | |
| 361 | } | ||
| 362 | |||
| 363 | 6762086 | static CEXP void h_sub_(iter a, iter a_end, citer b, citer b_end) NE { | |
| 364 | 6762086 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 365 | 6762086 | i32 carry = 0; | |
| 366 | i64 v; | ||
| 367 |
2/2✓ Branch 0 taken 1352035528 times.
✓ Branch 1 taken 6762086 times.
|
1358797614 | flt_ (usz, i, 0, bsz) a[i] = u32(v = (i64)a[i] - b[i] + carry), carry = i32(v >> 32); |
| 368 |
3/4✓ Branch 0 taken 1422860 times.
✓ Branch 1 taken 6762086 times.
✓ Branch 2 taken 1422860 times.
✗ Branch 3 not taken.
|
8184946 | for (usz i = bsz; carry && i < asz; ++i) a[i] = u32(v = (i64)a[i] + carry), carry = i32(v >> 32); |
| 369 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6762086 times.
|
6762086 | assert(!carry); |
| 370 | 6762086 | } | |
| 371 | 3146870 | static CEXP vecu h_sub_(vecu CR a, vecu CR b) NE { | |
| 372 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3146870 times.
|
3146870 | assert(h_leq_(b, a)); |
| 373 | 3146870 | vecu c = a; | |
| 374 | 3146870 | h_sub_(c.data(), c.data() + c.size(), b.data(), b.data() + b.size()), h_shrink_(c); | |
| 375 | 3146870 | return c; | |
| 376 | } | ||
| 377 | |||
| 378 | 6047476 | static CEXP void h_mul_naive_(citer a, citer a_end, citer b, citer b_end, iter c, iter c_end) NE { | |
| 379 | 6047476 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 380 |
2/4✓ Branch 0 taken 6047476 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 6047476 times.
|
6047476 | if (!asz || !bsz) return; |
| 381 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6047476 times.
|
6047476 | assert(usz(c_end - c) == asz + bsz); |
| 382 |
2/2✓ Branch 0 taken 422746472 times.
✓ Branch 1 taken 6047476 times.
|
428793948 | flt_ (usz, i, 0, asz) { |
| 383 | 422746472 | u32 carry = 0; | |
| 384 | u64 p; | ||
| 385 |
2/2✓ Branch 0 taken 29338502583 times.
✓ Branch 1 taken 422746472 times.
|
29761249055 | flt_ (usz, j, 0, bsz) c[i + j] = u32(p = (u64)a[i] * b[j] + carry + c[i + j]), carry = u32(p >> 32); |
| 386 | 422746472 | c[i + bsz] = carry; | |
| 387 | } | ||
| 388 | } | ||
| 389 | 7779572 | static CEXP void h_mul_(citer a, citer a_end, citer b, citer b_end, iter c, iter c_end) NE { | |
| 390 |
2/2✓ Branch 0 taken 51617 times.
✓ Branch 1 taken 7727955 times.
|
7779572 | if (a_end - a < b_end - b) std::swap(a, b), std::swap(a_end, b_end); |
| 391 | 7779572 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 392 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7779572 times.
|
7779572 | assert(usz(c_end - c) == asz + bsz); |
| 393 |
2/2✓ Branch 0 taken 6047476 times.
✓ Branch 1 taken 1732096 times.
|
7780213 | if (bsz <= 128) return h_mul_naive_(a, a_end, b, b_end, c, c_end); |
| 394 | 1732096 | usz const n = (asz + 1) >> 1; | |
| 395 |
2/2✓ Branch 0 taken 641 times.
✓ Branch 1 taken 1731455 times.
|
1732096 | if (bsz <= n) { |
| 396 | 641 | h_mul_(a, a + n, b, b_end, c, c + (n + bsz)); | |
| 397 | 641 | vecu carry(c + n, c + (n + bsz)); | |
| 398 | 641 | fill(c + n, c + (n + bsz), 0), h_mul_(a + n, a_end, b, b_end, c + n, c_end), h_add_(c + n, c_end, carry.data(), carry.data() + carry.size()); | |
| 399 | 641 | return; | |
| 400 | 641 | } | |
| 401 | 8657275 | vecu a1(n + 1), b1(n + 1), z1(2 * n + 2); | |
| 402 | 1731455 | h_mul_(a, a + n, b, b + n, c, c + (n + n)), h_mul_(a + n, a_end, b + n, b_end, c + (n + n), c_end), h_add_(a, a + n, a + n, a_end, a1.data(), a1.data() + a1.size()), h_add_(b, b + n, b + n, b_end, b1.data(), b1.data() + b1.size()), h_mul_(a1.data(), a1.data() + a1.size(), b1.data(), b1.data() + b1.size(), z1.data(), z1.data() + z1.size()), h_sub_(z1.data(), z1.data() + z1.size(), c, c + (n + n)), h_sub_(z1.data(), z1.data() + z1.size(), c + (n + n), c_end), h_shrink_(z1), h_add_(c + n, c_end, z1.data(), z1.data() + z1.size()); | |
| 403 | 1731455 | } | |
| 404 | 2478000 | static CEXP vecu h_mul_(vecu CR a, vecu CR b) NE { | |
| 405 |
6/6✓ Branch 1 taken 2474301 times.
✓ Branch 2 taken 3699 times.
✓ Branch 4 taken 3724 times.
✓ Branch 5 taken 2470577 times.
✓ Branch 6 taken 7423 times.
✓ Branch 7 taken 2470577 times.
|
2478000 | if (h_is0_(a) || h_is0_(b)) return {}; |
| 406 |
2/2✓ Branch 1 taken 584 times.
✓ Branch 2 taken 2469993 times.
|
2470577 | if (h_is_one_(a)) return b; |
| 407 |
2/2✓ Branch 1 taken 1358 times.
✓ Branch 2 taken 2468635 times.
|
2469993 | if (h_is_one_(b)) return a; |
| 408 | 2468635 | vecu c(a.size() + b.size()); | |
| 409 | 2468635 | h_mul_(a.data(), a.data() + a.size(), b.data(), b.data() + b.size(), c.data(), c.data() + c.size()), h_shrink_(c); | |
| 410 | 2468635 | return c; | |
| 411 | 2468635 | } | |
| 412 | |||
| 413 | 157716 | static CEXP u64 h_it2u64_(citer it, citer end) NE { | |
| 414 | 157716 | u64 res = 0; | |
| 415 | 157716 | u32 sh = 0; | |
| 416 |
2/2✓ Branch 0 taken 315432 times.
✓ Branch 1 taken 157716 times.
|
473148 | while (it != end) res |= ((u64)*it++) << sh, sh += 32; |
| 417 | 157716 | return res; | |
| 418 | } | ||
| 419 | 157716 | static CEXP void h_u642it_(u64 x, iter it, iter end) NE { | |
| 420 |
2/2✓ Branch 0 taken 190602 times.
✓ Branch 1 taken 157716 times.
|
348318 | while (x) { |
| 421 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 190602 times.
|
190602 | assert(it < end); |
| 422 | 190602 | *it++ = (u32)x, x >>= 32; | |
| 423 | } | ||
| 424 | 157716 | } | |
| 425 | 135132 | static CEXP void h_lsh_(iter a, iter a_end, int shift) NE { | |
| 426 |
2/2✓ Branch 0 taken 111706 times.
✓ Branch 1 taken 23426 times.
|
135132 | if (!shift) return; |
| 427 | 23426 | csint back = 32 - shift; | |
| 428 | 23426 | u32 carry = 0, v; | |
| 429 |
2/2✓ Branch 0 taken 5985533 times.
✓ Branch 1 taken 23426 times.
|
6008959 | flt_ (iter, it, a, a_end) v = (*it << shift) | carry, carry = (*it >> back), *it = v; |
| 430 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 23426 times.
|
23426 | assert(!carry); |
| 431 | } | ||
| 432 | 67566 | static CEXP void h_rsh_(iter a, iter a_end, int shift) NE { | |
| 433 |
2/2✓ Branch 0 taken 55853 times.
✓ Branch 1 taken 11713 times.
|
67566 | if (!shift) return; |
| 434 | 11713 | csint back = 32 - shift; | |
| 435 | 11713 | u32 carry = 0, v; | |
| 436 |
2/2✓ Branch 0 taken 1432260 times.
✓ Branch 1 taken 11713 times.
|
1443973 | for (iter it = a_end - 1; a <= it; --it) v = (*it >> shift) | carry, carry = (*it << back), *it = v; |
| 437 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 11713 times.
|
11713 | assert(!carry); |
| 438 | } | ||
| 439 | |||
| 440 | static CEXP u32 h_div_naive_th_ = 64; | ||
| 441 | 1179874 | static CEXP void h_divmod_naive_(citer a, citer a_end, citer b, citer b_end, iter quo, iter quo_end, iter rem, iter rem_end) NE { | |
| 442 | 1179874 | cusz asz = usz(a_end - a), bsz = usz(b_end - b); | |
| 443 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1179874 times.
|
1179874 | assert(bsz > 0); |
| 444 |
2/2✓ Branch 0 taken 1026550 times.
✓ Branch 1 taken 153324 times.
|
1179874 | if (bsz == 1) { |
| 445 | 1026550 | u64 carry = 0, v; | |
| 446 |
2/2✓ Branch 0 taken 1314783 times.
✓ Branch 1 taken 1026550 times.
|
2341333 | for (usz i = asz - 1; ~i; --i) quo[i] = u32((v = (carry << 32) | a[i]) / (*b)), carry = v - quo[i] * (*b); |
| 447 | 1026550 | *rem = (u32)carry; | |
| 448 | 1115013 | return; | |
| 449 | } | ||
| 450 |
2/2✓ Branch 1 taken 78858 times.
✓ Branch 2 taken 74466 times.
|
153324 | if (max(asz, bsz) <= 2) { |
| 451 | 78858 | cu64 a64 = h_it2u64_(a, a_end), b64 = h_it2u64_(b, b_end); | |
| 452 | 78858 | h_u642it_(a64 / b64, quo, quo_end), h_u642it_(a64 % b64, rem, rem_end); | |
| 453 | 78858 | return; | |
| 454 | } | ||
| 455 |
2/2✓ Branch 1 taken 9605 times.
✓ Branch 2 taken 64861 times.
|
74466 | if (h_lt_(a, a_end, b, b_end)) { |
| 456 |
2/2✓ Branch 0 taken 4817 times.
✓ Branch 1 taken 4788 times.
|
9605 | if (asz > bsz) a_end = a + bsz; |
| 457 | 9605 | copy(a, a_end, rem); | |
| 458 | 9605 | return; | |
| 459 | } | ||
| 460 | 64861 | auto sh = std::countl_zero(*(b_end - 1)); | |
| 461 | 194583 | vecu x(asz + (std::countl_zero(*(a_end - 1)) < sh)), y(usz(b_end - b)); | |
| 462 | 64861 | copy(a, a_end, x.begin()), copy(b, b_end, y.data()), h_lsh_(x.data(), x.data() + x.size(), sh), h_lsh_(y.data(), y.data() + y.size(), sh); | |
| 463 | 64861 | cu32 yb = y.back(); | |
| 464 | 194583 | vecu qv(x.size() - y.size() + 1), rv(x.end() - (int)y.size(), x.end()); | |
| 465 |
2/2✓ Branch 1 taken 2487429 times.
✓ Branch 2 taken 64861 times.
|
2552290 | for (usz i = (u32)qv.size() - 1; ~i; --i) { |
| 466 |
2/2✓ Branch 2 taken 67866 times.
✓ Branch 3 taken 2419563 times.
|
2487429 | if (rv.size() == y.size()) { |
| 467 |
2/2✓ Branch 1 taken 3970 times.
✓ Branch 2 taken 63896 times.
|
67866 | if (h_leq_(y, rv)) qv[i] = 1, rv = h_sub_(rv, y); |
| 468 |
2/2✓ Branch 2 taken 2294912 times.
✓ Branch 3 taken 124651 times.
|
2419563 | } else if (rv.size() > y.size()) { |
| 469 | 2294912 | u64 q = (((u64)rv[rv.size() - 1] << 32) | rv[rv.size() - 2]) / yb; | |
| 470 |
2/2✓ Branch 1 taken 37011 times.
✓ Branch 2 taken 2257901 times.
|
2294912 | if (q > (u64)-1_u32) q = (u64)-1_u32; |
| 471 | 4589824 | vecu yq = h_mul_(y, vecu{(u32)q}); | |
| 472 |
2/2✓ Branch 4 taken 745702 times.
✓ Branch 5 taken 2294912 times.
|
3040614 | while (h_lt_(rv, yq)) --q, yq = h_sub_(yq, y); |
| 473 | 2294912 | rv = h_sub_(rv, yq); | |
| 474 |
1/2✗ Branch 4 not taken.
✓ Branch 5 taken 2294912 times.
|
2294912 | while (h_leq_(y, rv)) ++q, rv = h_sub_(rv, y); |
| 475 | 2294912 | qv[i] = (u32)q; | |
| 476 | 2294912 | } | |
| 477 |
2/2✓ Branch 0 taken 2422568 times.
✓ Branch 1 taken 64861 times.
|
2487429 | if (i) rv.insert(rv.begin(), x[i - 1]); |
| 478 | 2487429 | h_shrink_(rv); | |
| 479 | } | ||
| 480 | 64861 | h_shrink_(qv), h_rsh_(rv.data(), rv.data() + rv.size(), sh), h_shrink_(rv), copy(qv.data(), qv.data() + qv.size(), quo), copy(rv.data(), rv.data() + rv.size(), rem); | |
| 481 | 64861 | } | |
| 482 | |||
| 483 | 118331 | static CEXP void h_divmod_d2n1n_(citer a, citer a_end, citer b, citer b_end, iter quo, iter quo_end, iter rem, iter rem_end) { | |
| 484 | 118331 | usz const n = usz(b_end - b); | |
| 485 |
4/4✓ Branch 0 taken 92202 times.
✓ Branch 1 taken 26129 times.
✓ Branch 2 taken 33804 times.
✓ Branch 3 taken 58398 times.
|
118331 | if ((n & 1) || n <= h_div_naive_th_) { |
| 486 | 59933 | h_divmod_naive_(a, a_end, b, b_end, quo, quo_end, rem, rem_end); | |
| 487 | 59933 | return; | |
| 488 | } | ||
| 489 | 58398 | usz const half = n >> 1; | |
| 490 |
1/2✓ Branch 1 taken 58398 times.
✗ Branch 2 not taken.
|
58398 | vecu r1(n + half + 1); |
| 491 |
3/6✓ Branch 2 taken 58398 times.
✗ Branch 3 not taken.
✓ Branch 8 taken 58398 times.
✗ Branch 9 not taken.
✓ Branch 14 taken 58398 times.
✗ Branch 15 not taken.
|
58398 | copy(a, a + half, r1.data()), h_divmod_d3n2n_impl_(a + half, a_end, b, b_end, quo + half, quo_end, r1.data() + half, r1.data() + r1.size()), h_divmod_d3n2n_impl_(r1.data(), r1.data() + r1.size() - 1, b, b_end, quo, quo + half, rem, rem_end); |
| 492 | 58398 | } | |
| 493 | 116796 | static CEXP void h_divmod_d3n2n_impl_(citer a, citer a_end, citer b, citer b_end, iter quo, iter quo_end, iter rem, iter rem_end) { | |
| 494 | 116796 | usz const n = usz(b_end - b) >> 1; | |
| 495 |
1/2✓ Branch 1 taken 116796 times.
✗ Branch 2 not taken.
|
116796 | vecu d(2 * n); |
| 496 |
3/4✓ Branch 1 taken 115290 times.
✓ Branch 2 taken 1506 times.
✓ Branch 4 taken 115290 times.
✗ Branch 5 not taken.
|
116796 | if (h_lt_(a + (n + n), a_end, b + n, b_end)) h_divmod_d2n1n_(a + n, a_end, b + n, b_end, quo, quo_end, rem + n, rem_end), h_mul_(quo, quo_end, b, b + n, d.data(), d.data() + d.size()); |
| 497 |
2/4✓ Branch 2 taken 1506 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 1506 times.
✗ Branch 8 not taken.
|
1506 | else fill(quo, quo_end, -1_u32), h_add_(a + n, a + (n + n), b + n, b_end, rem + n, rem_end), copy(b, b + n, d.data() + n), h_sub_(d.data(), d.data() + d.size(), b, b + n); |
| 498 |
1/2✓ Branch 1 taken 116796 times.
✗ Branch 2 not taken.
|
116796 | copy(a, a + n, rem); |
| 499 |
2/2✓ Branch 4 taken 34004 times.
✓ Branch 5 taken 116796 times.
|
150800 | while (h_lt_(rem, rem_end, d.data(), d.data() + d.size())) { |
| 500 |
1/2✓ Branch 1 taken 34004 times.
✗ Branch 2 not taken.
|
68008 | vecu one{1}; |
| 501 | 34004 | h_add_(rem, rem_end, b, b_end), h_sub_(quo, quo_end, one.data(), one.data() + one.size()); | |
| 502 | 34004 | } | |
| 503 | 116796 | h_sub_(rem, rem_end, d.data(), d.data() + d.size()); | |
| 504 | 116796 | } | |
| 505 | |||
| 506 | 1122646 | static CEXP void h_divmod_(citer a, citer a_end, citer b, citer b_end, iter q, iter q_end, iter r, iter r_end) NE { | |
| 507 | 1122646 | cusz asz = usz(a_end - a), bsz = usz(b_end - b), rsz = usz(r_end - r); | |
| 508 |
2/2✓ Branch 1 taken 1119941 times.
✓ Branch 2 taken 2705 times.
|
1122646 | if (std::min(asz - bsz, bsz) <= h_div_naive_th_) return h_divmod_naive_(a, a_end, b, b_end, q, q_end, r, r_end); |
| 509 | usz n; | ||
| 510 | { | ||
| 511 | 2705 | usz m = (bsz + h_div_naive_th_ - 1) / h_div_naive_th_; | |
| 512 |
1/2✓ Branch 0 taken 2705 times.
✗ Branch 1 not taken.
|
2705 | if (m > 1) m = 1_usz << (32 - std::countl_zero(u32(m - 1))); |
| 513 | 2705 | n = ((bsz + m - 1) / m) * m; | |
| 514 | } | ||
| 515 | 2705 | csint sd = (int)n - (int)bsz, ssh = std::countl_zero(*(b_end - 1)); | |
| 516 | 18935 | vecu x(asz + (usz)sd + (std::countl_zero(*(a_end - 1)) <= ssh)), y(n), rr(n + 1), z(2 * n); | |
| 517 | 2705 | copy(a, a_end, x.begin() + sd), copy(b, b_end, y.begin() + sd), h_lsh_(x.data() + sd, x.data() + x.size(), ssh), h_lsh_(y.data() + sd, y.data() + y.size(), ssh); | |
| 518 | 2705 | usz const t = max(2_usz, (x.size() + n - 1) / n); | |
| 519 | 2705 | copy(x.data() + ((t - 2) * n), x.data() + x.size(), z.data()); | |
| 520 |
2/2✓ Branch 0 taken 1249 times.
✓ Branch 1 taken 1456 times.
|
2705 | if (usz const q_ulen = usz(q_end - (q + ((t - 2) * n))); q_ulen < n) { |
| 521 | 1249 | vecu qq(n); | |
| 522 | 1249 | h_divmod_d2n1n_(z.data(), z.data() + z.size(), y.data(), y.data() + y.size(), qq.data(), qq.data() + qq.size(), rr.data(), rr.data() + rr.size()), copy(qq.data(), qq.data() + q_ulen, q + ((t - 2) * n)); | |
| 523 | 2705 | } else h_divmod_d2n1n_(z.data(), z.data() + z.size(), y.data(), y.data() + y.size(), q + ((t - 2) * n), q + ((t - 1) * n), rr.data(), rr.data() + rr.size()); | |
| 524 |
2/2✓ Branch 22 taken 336 times.
✓ Branch 23 taken 2705 times.
|
3041 | for (u32 i = (u32)t - 3; ~i; --i) copy(x.data() + i * n, x.data() + (i + 1) * n, z.data()), copy(rr.data(), rr.data() + n, z.data() + n), fill(rr.data(), rr.data() + rr.size(), 0), h_divmod_d2n1n_(z.data(), z.data() + z.size(), y.data(), y.data() + y.size(), q + i * n, q + (i + 1) * n, rr.data(), rr.data() + rr.size()); |
| 525 | 2705 | h_shrink_(rr), copy(rr.data() + sd, rr.data() + sd + rsz, r), h_rsh_(r, r_end, ssh); | |
| 526 | 2705 | } | |
| 527 | |||
| 528 | 1123896 | static CEXP ptt<vecu> h_divmod_(vecu CR a, vecu CR b) NE { | |
| 529 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1123896 times.
|
1123896 | assert(!h_is0_(b)); |
| 530 |
2/2✓ Branch 2 taken 1250 times.
✓ Branch 3 taken 1122646 times.
|
1123896 | if (a.size() < b.size()) return {{}, a}; |
| 531 | 3367938 | vecu q(a.size() - b.size() + 1), r(b.size()); | |
| 532 | 1122646 | h_divmod_(a.data(), a.data() + a.size(), b.data(), b.data() + b.size(), q.data(), q.data() + q.size(), r.data(), r.data() + r.size()), h_shrink_(q), h_shrink_(r); | |
| 533 | 1122646 | return {q, r}; | |
| 534 | 1122646 | } | |
| 535 | |||
| 536 | 1039303 | static CEXP vecu uadd(vec_like CR a, vec_like CR b) NE { | |
| 537 | 1039303 | vecu c(max(a.size(), b.size()) + 1); | |
| 538 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 3802115 times.
✓ Branch 4 taken 7286 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 5395994 times.
✓ Branch 4 taken 1032017 times.
|
10237412 | flt_ (u32, i, 0, (u32)a.size()) c[i] += a[i]; |
| 539 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 3705227 times.
✓ Branch 4 taken 7286 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 4974761 times.
✓ Branch 4 taken 1032017 times.
|
9719291 | flt_ (u32, i, 0, (u32)b.size()) c[i] += b[i]; |
| 540 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 3802115 times.
✓ Branch 2 taken 7286 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 6046646 times.
✓ Branch 2 taken 1032017 times.
|
10888064 | flt_ (u32, i, 0, (u32)c.size() - 1) |
| 541 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 1713875 times.
✓ Branch 2 taken 2088240 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::uadd<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 1993818 times.
✓ Branch 2 taken 4052828 times.
|
9848761 | if (c[i] >= D) c[i] -= D, ++c[i + 1]; |
| 542 | 1039303 | shrink_(c); | |
| 543 | 1039303 | return c; | |
| 544 | } | ||
| 545 | 747926 | static CEXP vecu usub(vec_like CR a, vec_like CR b) NE { | |
| 546 |
2/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 3 not taken.
✓ Branch 4 taken 622838 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 3 not taken.
✓ Branch 4 taken 125088 times.
|
747926 | assert(std::is_lteq(ucmp(b, a))); |
| 547 | 747926 | vecu c = a; | |
| 548 | 747926 | u32 borrow = 0; | |
| 549 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 125550388 times.
✓ Branch 2 taken 622838 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 3518350 times.
✓ Branch 2 taken 125088 times.
|
129816664 | flt_ (u32, i, 0, (u32)a.size()) { |
| 550 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 124801184 times.
✓ Branch 2 taken 749204 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 2398534 times.
✓ Branch 2 taken 1119816 times.
|
129068738 | if (i < b.size()) borrow += b[i]; |
| 551 |
4/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 2 taken 63068293 times.
✓ Branch 3 taken 62482095 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 2 taken 1512984 times.
✓ Branch 3 taken 2005366 times.
|
129068738 | if (c[i] -= borrow, borrow = 0; (i32)c[i] < 0) c[i] += D, borrow = 1; |
| 552 | } | ||
| 553 |
2/4std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 622838 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::usub<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 125088 times.
|
747926 | assert(!borrow); |
| 554 | 747926 | shrink_(c); | |
| 555 | 747926 | return c; | |
| 556 | } | ||
| 557 | 30280 | static CEXP vecu umul_3ntt(vec_like CR a, vec_like CR b) NE { | |
| 558 |
6/18std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 21050 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 21050 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 21050 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 9230 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 9230 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 9230 times.
|
30280 | if (a.empty() || b.empty()) return {}; |
| 559 | 30280 | auto m = conv_u128(a, b); | |
| 560 | 30280 | vecu c; | |
| 561 | 30280 | c.reserve(m.size() + 3); | |
| 562 | 30280 | u128 x = 0; | |
| 563 | 30280 | for (u32 i = 0;; ++i) { | |
| 564 |
12/18std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 30026 times.
✓ Branch 2 taken 33924547 times.
✓ Branch 3 taken 21050 times.
✓ Branch 4 taken 8976 times.
✓ Branch 5 taken 21050 times.
✓ Branch 6 taken 33933523 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 14170 times.
✓ Branch 2 taken 8659031 times.
✓ Branch 3 taken 9230 times.
✓ Branch 4 taken 4940 times.
✓ Branch 5 taken 9230 times.
✓ Branch 6 taken 8663971 times.
|
42627774 | if (i >= m.size() && !x) break; |
| 565 |
4/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 33924547 times.
✓ Branch 2 taken 8976 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_3ntt<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 8659031 times.
✓ Branch 2 taken 4940 times.
|
42597494 | if (i < m.size()) x += m[i]; |
| 566 | 42597494 | c.push_back(u32(x % D)), x /= D; | |
| 567 | } | ||
| 568 | 30280 | shrink_(c); | |
| 569 | 30280 | return c; | |
| 570 | 30280 | } | |
| 571 | 3225305 | static CEXP vecu umul_bf(vec_like CR a, vec_like CR b) NE { | |
| 572 |
9/24std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 467826 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 467826 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 467826 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 37692 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 37692 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 2719787 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 2719787 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 2719787 times.
|
3225305 | if (a.empty() || b.empty()) return {}; |
| 573 | 3225305 | vecuu prod(a.size() + b.size() - 1 + 1); | |
| 574 |
6/8std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 83949472 times.
✓ Branch 2 taken 467826 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 8575198 times.
✓ Branch 2 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 5640613 times.
✓ Branch 2 taken 2719787 times.
|
101390588 | flt_ (u32, i, 0, (u32)a.size()) |
| 575 |
6/8std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 83949472 times.
✓ Branch 2 taken 83949472 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 8575198 times.
✓ Branch 2 taken 8575198 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 11738726 times.
✓ Branch 2 taken 5640613 times.
|
202428679 | flt_ (u32, j, 0, (u32)b.size()) |
| 576 |
4/8std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 4 not taken.
✓ Branch 5 taken 83949472 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 4 not taken.
✗ Branch 5 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 4 not taken.
✓ Branch 5 taken 8575198 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 4 taken 10337 times.
✓ Branch 5 taken 11728389 times.
|
104263396 | if ((prod[i + j] += (u64)a[i] * b[j]) >= 4_u64 * D * D) prod[i + j] -= 4_u64 * D * D, prod[i + j + 1] += 4_u64 * D; |
| 577 | 3225305 | vecu c(prod.size() + 1); | |
| 578 | 3225305 | u64 x = 0; | |
| 579 | 3225305 | u32 i = 0; | |
| 580 |
6/8std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 84417298 times.
✓ Branch 4 taken 467826 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 3 not taken.
✗ Branch 4 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 8612890 times.
✓ Branch 4 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 10167229 times.
✓ Branch 4 taken 2719787 times.
|
106422722 | for (; i < prod.size(); ++i) x += prod[i], c[i] = u32(x % D), x /= D; |
| 581 |
4/8std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 9375 times.
✓ Branch 2 taken 467826 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<std::vector<unsigned int, std::allocator<unsigned int> >, tifa_libs::mpi>(std::vector<unsigned int, std::allocator<unsigned int> > const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 2719787 times.
|
3234680 | while (x) c[i] = u32(x % D), x /= D, ++i; |
| 582 | 3225305 | shrink_(c); | |
| 583 | 3225305 | return c; | |
| 584 | 3225305 | } | |
| 585 | 4084269 | static CEXP vecu umul(vec_like CR a, vec_like CR b) NE { | |
| 586 |
12/18std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 499297 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 499297 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 499297 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 40872 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 40872 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 40872 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 3538853 times.
✓ Branch 2 taken 5247 times.
✓ Branch 4 taken 5053 times.
✓ Branch 5 taken 3533800 times.
✓ Branch 6 taken 10300 times.
✓ Branch 7 taken 3533800 times.
|
4084269 | if (is_0(a) || is_0(b)) return {}; |
| 587 |
4/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 499297 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 40872 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 803638 times.
✓ Branch 2 taken 2730162 times.
|
4073969 | if (is_pm1(a)) return b; |
| 588 |
6/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 10421 times.
✓ Branch 2 taken 488876 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 3180 times.
✓ Branch 2 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 1145 times.
✓ Branch 2 taken 2729017 times.
|
3270331 | if (is_pm1(b)) return a; |
| 589 |
5/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 467826 times.
✓ Branch 4 taken 21050 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 3 taken 37692 times.
✗ Branch 4 not taken.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 2719787 times.
✓ Branch 4 taken 9230 times.
|
3255585 | if (min(a.size(), b.size()) <= CONV_NAIVE_THRESHOLD) { |
| 590 |
4/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 467826 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 37692 times.
std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::mpi::umul<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 2 taken 602461 times.
✓ Branch 3 taken 2117326 times.
|
3225305 | retif_((a.size() < b.size()), umul_bf(b, a), umul_bf(a, b)); |
| 591 | 30280 | } else return umul_3ntt(a, b); | |
| 592 | } | ||
| 593 | // 0 <= A < 1e16, 1 <= B < 1e8 | ||
| 594 | 1345449 | static CEXP ptt<vecu> udivmod_li(vec_like CR a, vec_like CR b) NE { | |
| 595 |
4/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_li<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 2896 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2896 times.
✗ Branch 5 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_li<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_li<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 1342553 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1342553 times.
✗ Branch 5 not taken.
|
1345449 | assert(a.size() <= 2 && b.size() == 1); |
| 596 | 1345449 | ci64 va = uvec2i64(a); | |
| 597 | 1345449 | cu32 vb = b[0]; | |
| 598 | 1345449 | return {int2vecu(va / vb), int2vecu(va % vb)}; | |
| 599 | } | ||
| 600 | // 0 <= A < 1e16, 1 <= B < 1e16 | ||
| 601 | 34095 | static CEXP ptt<vecu> udivmod_ll(vec_like CR a, vec_like CR b) NE { | |
| 602 |
3/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_ll<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_ll<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 34095 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 34095 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 34095 times.
✗ Branch 8 not taken.
|
34095 | assert(a.size() <= 2 && b.size() && b.size() <= 2); |
| 603 | 34095 | ci64 va = uvec2i64(a), vb = uvec2i64(b); | |
| 604 | 34095 | return {int2vecu(va / vb), int2vecu(va % vb)}; | |
| 605 | } | ||
| 606 | // 1 <= B < 1e8 | ||
| 607 | 1382676 | static CEXP ptt<vecu> udivmod_1e8(vec_like CR a, vec_like CR b) NE { | |
| 608 |
6/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 23699 times.
✓ Branch 5 taken 4853 times.
✓ Branch 6 taken 18846 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 1358977 times.
✓ Branch 5 taken 15689 times.
✓ Branch 6 taken 1343288 times.
|
1382676 | if (assert(b.size() == 1); b[0] == 1) return {a, {}}; |
| 609 |
4/6std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 2896 times.
✓ Branch 2 taken 15950 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 1342553 times.
✓ Branch 2 taken 735 times.
|
1362134 | if (a.size() <= 2) return udivmod_li(a, b); |
| 610 | 16685 | vecu quo(a.size()); | |
| 611 | 16685 | u64 d = 0; | |
| 612 | 16685 | cu32 b0 = b[0]; | |
| 613 |
6/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 1895922 times.
✓ Branch 6 taken 1895922 times.
✓ Branch 7 taken 15950 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 17422 times.
✓ Branch 6 taken 17422 times.
✓ Branch 7 taken 735 times.
|
1930029 | for (u32 i = (u32)a.size() - 1; ~i; --i) d = d * D + a[i], assert(d < (u64)D * b0), quo[i] = u32(d / b0), d = d % b0; |
| 614 | 16685 | shrink_(quo); | |
| 615 |
6/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 15950 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 15950 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, std::vector<unsigned int, std::allocator<unsigned int> > >(tifa_libs::mpi const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_1e8<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 0 taken 692 times.
✓ Branch 1 taken 43 times.
✓ Branch 6 taken 692 times.
✓ Branch 7 taken 43 times.
|
17377 | return {quo, d ? vecu{u32(d)} : vecu{}}; |
| 616 | 16685 | } | |
| 617 | // 0 <= A, 1 <= B | ||
| 618 | 1414230 | static CEXP ptt<vecu> udivmod_bf(vec_like CR a, vec_like CR b) NE { | |
| 619 |
7/12std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 3263 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3263 times.
✗ Branch 5 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 1410967 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1410967 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 1358977 times.
✓ Branch 9 taken 51990 times.
|
1414230 | if (assert(!is_0(b) && b.size()); b.size() == 1) return udivmod_1e8(a, b); |
| 620 |
3/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 3 not taken.
✓ Branch 4 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 34095 times.
✓ Branch 4 taken 17895 times.
|
55253 | if (max(a.size(), b.size()) <= 2) return udivmod_ll(a, b); |
| 621 |
3/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 3 not taken.
✓ Branch 4 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 722 times.
✓ Branch 4 taken 17173 times.
|
21158 | if (std::is_lt(ucmp(a, b))) return {{}, a}; |
| 622 | // B >= 1e8, A >= B | ||
| 623 | 20436 | cu32 norm = D / (b.back() + 1); | |
| 624 | 81744 | vecu x = umul(a, vecu{norm}), y = umul(b, vecu{norm}); | |
| 625 | 20436 | cu32 yb = y.back(); | |
| 626 | 61308 | vecu quo(x.size() - y.size() + 1), rem(x.end() - (int)y.size(), x.end()); | |
| 627 |
4/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 1 taken 156153 times.
✓ Branch 2 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 1 taken 393678 times.
✓ Branch 2 taken 17173 times.
|
570267 | for (u32 i = (u32)quo.size() - 1; ~i; --i) { |
| 628 |
4/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 2 taken 3536 times.
✓ Branch 3 taken 152617 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 2 taken 17174 times.
✓ Branch 3 taken 376504 times.
|
549831 | if (rem.size() == y.size()) { |
| 629 |
3/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 3 not taken.
✓ Branch 4 taken 3536 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 3 taken 89 times.
✓ Branch 4 taken 17085 times.
|
20710 | if (std::is_lteq(ucmp(y, rem))) quo[i] = 1, rem = usub(rem, y); |
| 630 |
3/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 2 taken 95217 times.
✓ Branch 3 taken 57400 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 2 taken 376504 times.
✗ Branch 3 not taken.
|
529121 | } else if (rem.size() > y.size()) { |
| 631 |
2/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 95217 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 2 not taken.
✓ Branch 3 taken 376504 times.
|
471721 | assert(y.size() + 1 == rem.size()); |
| 632 | 471721 | u32 q = u32(((u64)rem[rem.size() - 1] * D + rem[rem.size() - 2]) / yb); | |
| 633 | 943442 | vecu yq = umul(y, vecu{q}); | |
| 634 |
4/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 6 taken 24979 times.
✓ Branch 7 taken 95217 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 6 taken 113540 times.
✓ Branch 7 taken 376504 times.
|
610240 | while (std::is_lt(ucmp(rem, yq))) --q, yq = usub(yq, y); |
| 635 | 471721 | rem = usub(rem, yq); | |
| 636 |
2/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 6 not taken.
✓ Branch 7 taken 95217 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 6 not taken.
✓ Branch 7 taken 376504 times.
|
471721 | while (std::is_lteq(ucmp(y, rem))) ++q, rem = usub(rem, y); |
| 637 | 471721 | quo[i] = q; | |
| 638 | 471721 | } | |
| 639 |
4/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✓ Branch 0 taken 152890 times.
✓ Branch 1 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✓ Branch 0 taken 376505 times.
✓ Branch 1 taken 17173 times.
|
549831 | if (i) rem.insert(rem.begin(), x[i - 1]); |
| 640 | } | ||
| 641 | 20436 | shrink_(quo), shrink_(rem); | |
| 642 | 61308 | auto [q2, r2] = udivmod_1e8(rem, vecu{norm}); | |
| 643 |
2/4std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > >(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 3263 times.
std::pair<std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<unsigned int, std::allocator<unsigned int> > > tifa_libs::mpi::udivmod_bf<tifa_libs::mpi, tifa_libs::mpi>(tifa_libs::mpi const&, tifa_libs::mpi const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 17173 times.
|
20436 | assert(is_0(r2)); |
| 644 | 20436 | return {quo, q2}; | |
| 645 | 20436 | } | |
| 646 | // 1 / a, abserr = B^{-deg} | ||
| 647 | 3263 | static CEXP vecu inv_(vec_like CR a, u32 deg) { | |
| 648 |
3/6✓ Branch 1 taken 3263 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3263 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3263 times.
✗ Branch 8 not taken.
|
3263 | assert(!a.empty() && D / 2 <= a.back() && a.back() < D); |
| 649 | 3263 | u32 k = deg, c = (u32)a.size(); | |
| 650 |
2/2✓ Branch 0 taken 7262 times.
✓ Branch 1 taken 3263 times.
|
10525 | while (k > 64) k = (k + 1) / 2; |
| 651 |
1/2✓ Branch 1 taken 3263 times.
✗ Branch 2 not taken.
|
3263 | vecu z(c + k + 1); |
| 652 | 3263 | z.back() = 1, z = udivmod_bf(z, a).first; | |
| 653 |
2/2✓ Branch 4 taken 7262 times.
✓ Branch 5 taken 3263 times.
|
17787 | while (k < deg) { |
| 654 | 7262 | vecu s = umul(z, z); | |
| 655 |
1/2✓ Branch 3 taken 7262 times.
✗ Branch 4 not taken.
|
7262 | s.insert(s.begin(), 0); |
| 656 | 7262 | cu32 d = min(c, 2 * k + 1); | |
| 657 |
1/2✓ Branch 4 taken 7262 times.
✗ Branch 5 not taken.
|
21786 | cvecu t{a.end() - d, a.end()}, w2 = uadd(z, z); |
| 658 |
1/2✓ Branch 2 taken 7262 times.
✗ Branch 3 not taken.
|
14524 | vecu u = umul(s, t), w(k + 1); |
| 659 |
3/6✓ Branch 6 taken 7262 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 7262 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 7262 times.
✗ Branch 13 not taken.
|
7262 | u.erase(u.begin(), u.begin() + d), copy(w2, std::back_inserter(w)); |
| 660 |
1/2✓ Branch 5 taken 7262 times.
✗ Branch 6 not taken.
|
7262 | (z = usub(w, u)).erase(z.begin()), k *= 2; |
| 661 | } | ||
| 662 |
1/2✓ Branch 7 taken 3263 times.
✗ Branch 8 not taken.
|
3263 | z.erase(z.begin(), z.begin() + k - deg); |
| 663 | 6526 | return z; | |
| 664 | ✗ | } | |
| 665 | 1414230 | static CEXP ptt<vecu> udivmod(vec_like CR a, vec_like CR b) NE { | |
| 666 |
3/4✗ Branch 1 not taken.
✓ Branch 2 taken 1414230 times.
✓ Branch 5 taken 1409896 times.
✓ Branch 6 taken 4334 times.
|
1414230 | if (assert(!is_0(b)); b.size() <= 64) return udivmod_bf(a, b); |
| 667 |
2/2✓ Branch 2 taken 1071 times.
✓ Branch 3 taken 3263 times.
|
4334 | if ((int)(a.size() - b.size()) <= 64) return udivmod_bf(a, b); |
| 668 | 3263 | cu32 norm = D / (b.back() + 1); | |
| 669 | 13052 | cvecu x = umul(a, vecu{norm}), y = umul(b, vecu{norm}); | |
| 670 | 3263 | cu32 s = (u32)x.size(), t = (u32)y.size(), deg = s + 2 - t; | |
| 671 | 3263 | cvecu z = inv_(y, deg); | |
| 672 | 3263 | vecu q = umul(x, z); | |
| 673 | 3263 | q.erase(q.begin(), q.begin() + t + deg); | |
| 674 | 3263 | vecu yq = umul(y, vecu{q}); | |
| 675 |
2/2✓ Branch 11 taken 980 times.
✓ Branch 12 taken 3263 times.
|
5223 | while (std::is_lt(ucmp(x, yq))) q = usub(q, vecu{1}), yq = usub(yq, y); |
| 676 | 3263 | vecu r = usub(x, yq); | |
| 677 |
2/2✓ Branch 11 taken 24 times.
✓ Branch 12 taken 3263 times.
|
3311 | while (std::is_lteq(ucmp(y, r))) q = uadd(q, vecu{1}), r = usub(r, y); |
| 678 | 3263 | shrink_(q), shrink_(r); | |
| 679 | 9789 | auto [q2, r2] = udivmod_1e8(r, vecu{norm}); | |
| 680 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3263 times.
|
3263 | assert(is_0(r2)); |
| 681 | 3263 | return {q, q2}; | |
| 682 | 3263 | } | |
| 683 | |||
| 684 | #undef vec_like | ||
| 685 | }; | ||
| 686 | |||
| 687 | } // namespace tifa_libs | ||
| 688 |