pub trait MontgomeryReduction32 {
const MOD: u32;
const R: u32 = _;
const N1: u32 = _;
const N2: u32 = _;
const N3: u32 = _;
// Provided method
fn reduce(x: u64) -> u32 { ... }
}Expand description
m is prime, n = 2^32
Required Associated Constants§
Provided Associated Constants§
Provided Methods§
Sourcefn reduce(x: u64) -> u32
fn reduce(x: u64) -> u32
n^{-1}x = (x + (xr mod n)m) / n
Examples found in repository?
crates/competitive/src/num/mint/montgomery.rs (line 36)
35 fn mod_mul(x: Self::Inner, y: Self::Inner) -> Self::Inner {
36 Self::reduce(x as u64 * y as u64)
37 }
38 #[inline]
39 fn mod_div(x: Self::Inner, y: Self::Inner) -> Self::Inner {
40 Self::mod_mul(x, Self::mod_inv(y))
41 }
42 #[inline]
43 fn mod_neg(x: Self::Inner) -> Self::Inner {
44 if x == 0 { 0 } else { Self::get_mod() - x }
45 }
46 fn mod_inv(x: Self::Inner) -> Self::Inner {
47 let p = Self::get_mod() as i32;
48 let (mut a, mut b) = (x as i32, p);
49 let (mut u, mut x) = (1, 0);
50 while a != 0 {
51 let k = b / a;
52 x -= k * u;
53 b -= k * a;
54 std::mem::swap(&mut x, &mut u);
55 std::mem::swap(&mut b, &mut a);
56 }
57 Self::reduce((if x < 0 { x + p } else { x }) as u64 * Self::N3 as u64)
58 }
59 fn mod_inner(x: Self::Inner) -> Self::Inner {
60 Self::reduce(x as u64)
61 }
62}
63impl<M> MIntConvert<u32> for M
64where
65 M: MontgomeryReduction32,
66{
67 #[inline]
68 fn from(x: u32) -> Self::Inner {
69 Self::reduce(x as u64 * Self::N2 as u64)
70 }
71 #[inline]
72 fn into(x: Self::Inner) -> u32 {
73 Self::reduce(x as u64)
74 }
75 #[inline]
76 fn mod_into() -> u32 {
77 <Self as MIntBase>::get_mod()
78 }
79}
80impl<M> MIntConvert<u64> for M
81where
82 M: MontgomeryReduction32,
83{
84 #[inline]
85 fn from(x: u64) -> Self::Inner {
86 Self::reduce(x % Self::get_mod() as u64 * Self::N2 as u64)
87 }
88 #[inline]
89 fn into(x: Self::Inner) -> u64 {
90 Self::reduce(x as u64) as u64
91 }
92 #[inline]
93 fn mod_into() -> u64 {
94 <Self as MIntBase>::get_mod() as u64
95 }
96}
97impl<M> MIntConvert<usize> for M
98where
99 M: MontgomeryReduction32,
100{
101 #[inline]
102 fn from(x: usize) -> Self::Inner {
103 Self::reduce(x as u64 % Self::get_mod() as u64 * Self::N2 as u64)
104 }
105 #[inline]
106 fn into(x: Self::Inner) -> usize {
107 Self::reduce(x as u64) as usize
108 }
109 #[inline]
110 fn mod_into() -> usize {
111 <Self as MIntBase>::get_mod() as usize
112 }
113}
114impl<M> MIntConvert<i32> for M
115where
116 M: MontgomeryReduction32,
117{
118 #[inline]
119 fn from(x: i32) -> Self::Inner {
120 let x = x % <Self as MIntBase>::get_mod() as i32;
121 let x = if x < 0 {
122 (x + <Self as MIntBase>::get_mod() as i32) as u64
123 } else {
124 x as u64
125 };
126 Self::reduce(x * Self::N2 as u64)
127 }
128 #[inline]
129 fn into(x: Self::Inner) -> i32 {
130 Self::reduce(x as u64) as i32
131 }
132 #[inline]
133 fn mod_into() -> i32 {
134 <Self as MIntBase>::get_mod() as i32
135 }
136}
137impl<M> MIntConvert<i64> for M
138where
139 M: MontgomeryReduction32,
140{
141 #[inline]
142 fn from(x: i64) -> Self::Inner {
143 let x = x % <Self as MIntBase>::get_mod() as i64;
144 let x = if x < 0 {
145 (x + <Self as MIntBase>::get_mod() as i64) as u64
146 } else {
147 x as u64
148 };
149 Self::reduce(x * Self::N2 as u64)
150 }
151 #[inline]
152 fn into(x: Self::Inner) -> i64 {
153 Self::reduce(x as u64) as i64
154 }
155 #[inline]
156 fn mod_into() -> i64 {
157 <Self as MIntBase>::get_mod() as i64
158 }
159}
160impl<M> MIntConvert<isize> for M
161where
162 M: MontgomeryReduction32,
163{
164 #[inline]
165 fn from(x: isize) -> Self::Inner {
166 let x = x % <Self as MIntBase>::get_mod() as isize;
167 let x = if x < 0 {
168 (x + <Self as MIntBase>::get_mod() as isize) as u64
169 } else {
170 x as u64
171 };
172 Self::reduce(x * Self::N2 as u64)
173 }
174 #[inline]
175 fn into(x: Self::Inner) -> isize {
176 Self::reduce(x as u64) as isize
177 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.