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 30)
29 fn mod_mul(x: Self::Inner, y: Self::Inner) -> Self::Inner {
30 Self::reduce(x as u64 * y as u64)
31 }
32
33 fn mod_div(x: Self::Inner, y: Self::Inner) -> Self::Inner {
34 Self::mod_mul(x, Self::mod_inv(y))
35 }
36 fn mod_neg(x: Self::Inner) -> Self::Inner {
37 if x == 0 { 0 } else { Self::get_mod() - x }
38 }
39 fn mod_inv(x: Self::Inner) -> Self::Inner {
40 let p = Self::get_mod() as i32;
41 let (mut a, mut b) = (x as i32, p);
42 let (mut u, mut x) = (1, 0);
43 while a != 0 {
44 let k = b / a;
45 x -= k * u;
46 b -= k * a;
47 std::mem::swap(&mut x, &mut u);
48 std::mem::swap(&mut b, &mut a);
49 }
50 Self::reduce((if x < 0 { x + p } else { x }) as u64 * Self::N3 as u64)
51 }
52 fn mod_inner(x: Self::Inner) -> Self::Inner {
53 Self::reduce(x as u64)
54 }
55}
56impl<M> MIntConvert<u32> for M
57where
58 M: MontgomeryReduction32,
59{
60 fn from(x: u32) -> Self::Inner {
61 Self::reduce(x as u64 * Self::N2 as u64)
62 }
63 fn into(x: Self::Inner) -> u32 {
64 Self::reduce(x as u64)
65 }
66 fn mod_into() -> u32 {
67 <Self as MIntBase>::get_mod()
68 }
69}
70impl<M> MIntConvert<u64> for M
71where
72 M: MontgomeryReduction32,
73{
74 fn from(x: u64) -> Self::Inner {
75 Self::reduce(x % Self::get_mod() as u64 * Self::N2 as u64)
76 }
77 fn into(x: Self::Inner) -> u64 {
78 Self::reduce(x as u64) as u64
79 }
80 fn mod_into() -> u64 {
81 <Self as MIntBase>::get_mod() as u64
82 }
83}
84impl<M> MIntConvert<usize> for M
85where
86 M: MontgomeryReduction32,
87{
88 fn from(x: usize) -> Self::Inner {
89 Self::reduce(x as u64 % Self::get_mod() as u64 * Self::N2 as u64)
90 }
91 fn into(x: Self::Inner) -> usize {
92 Self::reduce(x as u64) as usize
93 }
94 fn mod_into() -> usize {
95 <Self as MIntBase>::get_mod() as usize
96 }
97}
98impl<M> MIntConvert<i32> for M
99where
100 M: MontgomeryReduction32,
101{
102 fn from(x: i32) -> Self::Inner {
103 let x = x % <Self as MIntBase>::get_mod() as i32;
104 let x = if x < 0 {
105 (x + <Self as MIntBase>::get_mod() as i32) as u64
106 } else {
107 x as u64
108 };
109 Self::reduce(x * Self::N2 as u64)
110 }
111 fn into(x: Self::Inner) -> i32 {
112 Self::reduce(x as u64) as i32
113 }
114 fn mod_into() -> i32 {
115 <Self as MIntBase>::get_mod() as i32
116 }
117}
118impl<M> MIntConvert<i64> for M
119where
120 M: MontgomeryReduction32,
121{
122 fn from(x: i64) -> Self::Inner {
123 let x = x % <Self as MIntBase>::get_mod() as i64;
124 let x = if x < 0 {
125 (x + <Self as MIntBase>::get_mod() as i64) as u64
126 } else {
127 x as u64
128 };
129 Self::reduce(x * Self::N2 as u64)
130 }
131 fn into(x: Self::Inner) -> i64 {
132 Self::reduce(x as u64) as i64
133 }
134 fn mod_into() -> i64 {
135 <Self as MIntBase>::get_mod() as i64
136 }
137}
138impl<M> MIntConvert<isize> for M
139where
140 M: MontgomeryReduction32,
141{
142 fn from(x: isize) -> Self::Inner {
143 let x = x % <Self as MIntBase>::get_mod() as isize;
144 let x = if x < 0 {
145 (x + <Self as MIntBase>::get_mod() as isize) as u64
146 } else {
147 x as u64
148 };
149 Self::reduce(x * Self::N2 as u64)
150 }
151 fn into(x: Self::Inner) -> isize {
152 Self::reduce(x as u64) as isize
153 }More examples
crates/competitive/src/num/mint/montgomery_dot_product.rs (line 39)
26 fn dot_product(x: &[MInt<Self>], y: &[MInt<Self>]) -> MInt<Self> {
27 assert_eq!(x.len(), y.len());
28 // reduce() needs sum < modulus * 2^32 to return a canonical residue.
29 let modulus = <Self as MontgomeryReduction32>::MOD as u64;
30 let block = (((modulus << 32) - 1) / ((modulus - 1) * (modulus - 1))).min(16) as usize;
31 let mut result = 0;
32 for (x, y) in x.chunks(block).zip(y.chunks(block)) {
33 // SAFETY: MInt is transparent over u32 and both slices have equal lengths.
34 let sum = unsafe {
35 let a = std::slice::from_raw_parts(x.as_ptr().cast::<u32>(), x.len());
36 let b = std::slice::from_raw_parts(y.as_ptr().cast::<u32>(), y.len());
37 a.iter().zip(b).map(|(&a, &b)| a as u64 * b as u64).sum()
38 };
39 result = Self::mod_add(result, Self::reduce(sum));
40 }
41 MInt::new_unchecked(result)
42 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".