src/math/qpow/rpow/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../nt/mod/barrett/lib.hpp" | ||
| 4 | #include "../../../util/alias/others/lib.hpp" | ||
| 5 | #include "../../mul_mod/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | class rpow { | ||
| 10 | vecuu b0, b1; | ||
| 11 | u64 b_, m_; | ||
| 12 | |||
| 13 | public: | ||
| 14 | 6672 | CEXP rpow() NE : b0(65536), b1(65536), b_{}, m_{} {} | |
| 15 | CEXP rpow(u64 base_, u32 mod_) NE : rpow() { reset(base_, mod_); } | ||
| 16 | |||
| 17 | 2142 | CEXP void reset(u64 base, u32 mod) NE { | |
| 18 |
3/4✓ Branch 0 taken 636 times.
✓ Branch 1 taken 1506 times.
✓ Branch 2 taken 636 times.
✗ Branch 3 not taken.
|
2142 | if (b_ == base % mod && m_ == mod) return; |
| 19 | 1506 | b_ = base % mod, m_ = mod, b0[0] = b1[0] = 1; | |
| 20 | 1506 | barrett<0> brt(m_, b_); | |
| 21 |
2/2✓ Branch 3 taken 98695710 times.
✓ Branch 4 taken 1506 times.
|
98697216 | flt_ (u32, i, 1, 65536) b0[i] = brt.reduce(b0[i - 1]); |
| 22 | 1506 | cu64 _ = brt.reduce(b0.back()); | |
| 23 | 1506 | brt.reset(m_, _); | |
| 24 |
2/2✓ Branch 3 taken 98695710 times.
✓ Branch 4 taken 1506 times.
|
98697216 | flt_ (u32, i, 1, 65536) b1[i] = brt.reduce(b1[i - 1]); |
| 25 | } | ||
| 26 | 171 | CEXP void swap(rpow& r) NE { | |
| 27 | 171 | b0.swap(r.b0), b1.swap(r.b1); | |
| 28 | 171 | std::swap(b_, r.b_), std::swap(m_, r.m_); | |
| 29 | 171 | } | |
| 30 | 1071 | ND CEXP u64 base() CNE { return b_; } | |
| 31 | ND CEXP u64 mod() CNE { return m_; } | ||
| 32 | 1196949438 | CEXP u64 operator()(u32 x) CNE { return mul_mod_u(b0[x & 65535], b1[x >> 16], m_); } | |
| 33 | }; | ||
| 34 | |||
| 35 | } // namespace tifa_libs | ||
| 36 |