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 fn mod_div(x: Self::Inner, y: Self::Inner) -> Self::Inner {
33 Self::mod_mul(x, Self::mod_inv(y))
34 }
35 fn mod_neg(x: Self::Inner) -> Self::Inner {
36 if x == 0 { 0 } else { Self::get_mod() - x }
37 }
38 fn mod_inv(x: Self::Inner) -> Self::Inner {
39 let p = Self::get_mod() as i32;
40 let (mut a, mut b) = (x as i32, p);
41 let (mut u, mut x) = (1, 0);
42 while a != 0 {
43 let k = b / a;
44 x -= k * u;
45 b -= k * a;
46 std::mem::swap(&mut x, &mut u);
47 std::mem::swap(&mut b, &mut a);
48 }
49 Self::reduce((if x < 0 { x + p } else { x }) as u64 * Self::N3 as u64)
50 }
51 fn mod_inner(x: Self::Inner) -> Self::Inner {
52 Self::reduce(x as u64)
53 }
54}
55impl<M> MIntConvert<u32> for M
56where
57 M: MontgomeryReduction32,
58{
59 fn from(x: u32) -> Self::Inner {
60 Self::reduce(x as u64 * Self::N2 as u64)
61 }
62 fn into(x: Self::Inner) -> u32 {
63 Self::reduce(x as u64)
64 }
65 fn mod_into() -> u32 {
66 <Self as MIntBase>::get_mod()
67 }
68}
69impl<M> MIntConvert<u64> for M
70where
71 M: MontgomeryReduction32,
72{
73 fn from(x: u64) -> Self::Inner {
74 Self::reduce(x % Self::get_mod() as u64 * Self::N2 as u64)
75 }
76 fn into(x: Self::Inner) -> u64 {
77 Self::reduce(x as u64) as u64
78 }
79 fn mod_into() -> u64 {
80 <Self as MIntBase>::get_mod() as u64
81 }
82}
83impl<M> MIntConvert<usize> for M
84where
85 M: MontgomeryReduction32,
86{
87 fn from(x: usize) -> Self::Inner {
88 Self::reduce(x as u64 % Self::get_mod() as u64 * Self::N2 as u64)
89 }
90 fn into(x: Self::Inner) -> usize {
91 Self::reduce(x as u64) as usize
92 }
93 fn mod_into() -> usize {
94 <Self as MIntBase>::get_mod() as usize
95 }
96}
97impl<M> MIntConvert<i32> for M
98where
99 M: MontgomeryReduction32,
100{
101 fn from(x: i32) -> Self::Inner {
102 let x = x % <Self as MIntBase>::get_mod() as i32;
103 let x = if x < 0 {
104 (x + <Self as MIntBase>::get_mod() as i32) as u64
105 } else {
106 x as u64
107 };
108 Self::reduce(x * Self::N2 as u64)
109 }
110 fn into(x: Self::Inner) -> i32 {
111 Self::reduce(x as u64) as i32
112 }
113 fn mod_into() -> i32 {
114 <Self as MIntBase>::get_mod() as i32
115 }
116}
117impl<M> MIntConvert<i64> for M
118where
119 M: MontgomeryReduction32,
120{
121 fn from(x: i64) -> Self::Inner {
122 let x = x % <Self as MIntBase>::get_mod() as i64;
123 let x = if x < 0 {
124 (x + <Self as MIntBase>::get_mod() as i64) as u64
125 } else {
126 x as u64
127 };
128 Self::reduce(x * Self::N2 as u64)
129 }
130 fn into(x: Self::Inner) -> i64 {
131 Self::reduce(x as u64) as i64
132 }
133 fn mod_into() -> i64 {
134 <Self as MIntBase>::get_mod() as i64
135 }
136}
137impl<M> MIntConvert<isize> for M
138where
139 M: MontgomeryReduction32,
140{
141 fn from(x: isize) -> Self::Inner {
142 let x = x % <Self as MIntBase>::get_mod() as isize;
143 let x = if x < 0 {
144 (x + <Self as MIntBase>::get_mod() as isize) as u64
145 } else {
146 x as u64
147 };
148 Self::reduce(x * Self::N2 as u64)
149 }
150 fn into(x: Self::Inner) -> isize {
151 Self::reduce(x as u64) as isize
152 }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.