1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143 | #pragma once
#include <utility>
#include <limits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <concepts><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <type_traits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "snippet/aliases.hpp"
#include "internal/types.hpp"
#include "internal/concepts.hpp"
#include "numeric/bit.hpp"
#include "numeric/arithmetic.hpp"
#include "template/debug.hpp"
namespace uni {
namespace internal {
template<std::unsigned_integral Value, std::unsigned_integral Large>
requires has_double_digits_of<Large, Value>
struct barrett_reduction {
using value_type = Value;
using large_type = Large;
private:
large_type _mod = 0, _mi;
inline constexpr std::pair<large_type,value_type> _reduce(const large_type v) const noexcept(NO_EXCEPT) {
large_type x = multiply_high(v, this->_mi);
return { x, static_cast<value_type>(v - x * this->_mod) };
}
public:
static constexpr int digits = std::numeric_limits<value_type>::digits - 1;
static constexpr value_type max() noexcept { return (value_type{ 1 } << barrett_reduction::digits) - 1; }
inline constexpr value_type mod() const noexcept(NO_EXCEPT) { return this->_mod; }<--- Shadowed declaration
constexpr barrett_reduction() noexcept = default;
constexpr explicit inline barrett_reduction(const value_type mod)
: _mod(mod), _mi(std::numeric_limits<large_type>::max() / mod + 1)
{
assert(0 < mod && mod <= barrett_reduction::max());
}
inline constexpr large_type quotient(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
return static_cast<large_type>(this->_mod <= r ? x - 1 : x);
}
inline constexpr value_type reduce(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
return static_cast<value_type>(this->_mod <= r ? r + this->_mod : r);
}
inline constexpr std::pair<large_type,value_type> divide(const large_type v) const noexcept(NO_EXCEPT) {
const auto [ x, r ] = this->_reduce(v);
if(this->_mod <= r) return { static_cast<large_type>(x - 1), static_cast<value_type>(r + this->_mod) };
return { static_cast<large_type>(x), static_cast<value_type>(r) };
}
inline constexpr value_type add(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
x += y;
if(x >= this->_mod) x -= this->_mod;
return x;
}
inline constexpr value_type subtract(value_type x, const value_type y) const noexcept(NO_EXCEPT) {
if(x < y) x += this->_mod;
x -= y;
return x;
}
inline constexpr value_type multiply(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return this->reduce(static_cast<large_type>(x) * static_cast<large_type>(y));
}
template<std::integral K>
inline constexpr value_type pow(const large_type v, const K p) const noexcept(NO_EXCEPT) {
if constexpr(std::signed_integral<K>) assert(p >= 0);
if(this->_mod == 1) return 0;
return uni::pow(
this->reduce(v), p,
[&](const value_type x, const value_type y) noexcept(NO_EXCEPT) { return this->multiply(x, y); }
);
}
inline constexpr auto compare(const value_type x, const value_type y) const noexcept(NO_EXCEPT) {
return x <=> y;
}
constexpr value_type convert_raw(const value_type v) const noexcept(NO_EXCEPT) { return v; }
template<std::integral T>
constexpr value_type convert(T v) const noexcept(NO_EXCEPT) {
using common_type = std::common_type_t<T, value_type>;
const common_type mod = static_cast<common_type>(this->_mod);<--- Shadow variable
if(v > 0 && static_cast<common_type>(v) >= mod) {
if(static_cast<common_type>(v) <= barrett_reduction::max()) v = this->reduce(v);
else v %= mod;
}
if constexpr(std::signed_integral<T>) {
if(v < 0) {
if(static_cast<common_type>(-v) <= mod) v += mod;
else if(static_cast<common_type>(-v) <= barrett_reduction::max()) {
v = mod - this->reduce(static_cast<value_type>(-v - 1)) - 1;
}
else {
v %= mod;
if(v != 0) v += mod;
}
}
}
return static_cast<value_type>(v);
}
constexpr value_type revert(const value_type v) const noexcept(NO_EXCEPT) { return this->reduce(v); }
};
} // namespace internal
using barrett_reduction_32bit = internal::barrett_reduction<u32, u64>;
using barrett_reduction_64bit = internal::barrett_reduction<u64, u128>;
} // namespace uni
|