Xorshift

competitive::tools

Struct Xorshift 

Source 
pub struct Xorshift { /* private fields */ }

Implementations§

Source§

impl Xorshift

Source

pub fn random<T, R>(&mut self, spec: R) -> T
where R: RandomSpec<T>,

Examples found in repository?
crates/competitive/src/tools/random_generator.rs (line 75)
74    fn rand(&self, rng: &mut Xorshift) -> i128 {
75        rng.random::<u128, _>(..) as i128
76    }
77}
78
79macro_rules! impl_random_spec_ranges {
80    ($($u:ident $i:ident)*) => {
81        $(
82            impl RandomSpec<$u> for Range<$u> {
83                fn rand(&self, rng: &mut Xorshift) -> $u {
84                    assert!(self.start < self.end);
85                    let len = self.end - self.start;
86                    (self.start + rng.random::<$u, _>(..) % len)
87                }
88            }
89            impl RandomSpec<$i> for Range<$i> {
90                fn rand(&self, rng: &mut Xorshift) -> $i {
91                    assert!(self.start < self.end);
92                    let len = self.end.abs_diff(self.start);
93                    self.start.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
94                }
95            }
96            impl RandomSpec<$u> for RangeFrom<$u> {
97                fn rand(&self, rng: &mut Xorshift) -> $u {
98                    let len = ($u::MAX - self.start).wrapping_add(1);
99                    let x = rng.random::<$u, _>(..);
100                    self.start + if len != 0 { x % len } else { x }
101                }
102            }
103            impl RandomSpec<$i> for RangeFrom<$i> {
104                fn rand(&self, rng: &mut Xorshift) -> $i {
105                    let len = ($i::MAX.abs_diff(self.start)).wrapping_add(1);
106                    let x = rng.random::<$u, _>(..);
107                    self.start.wrapping_add_unsigned(if len != 0 { x % len } else { x })
108                }
109            }
110            impl RandomSpec<$u> for RangeInclusive<$u> {
111                fn rand(&self, rng: &mut Xorshift) -> $u {
112                    assert!(self.start() <= self.end());
113                    let len = (self.end() - self.start()).wrapping_add(1);
114                    let x = rng.random::<$u, _>(..);
115                    self.start() + if len != 0 { x % len } else { x }
116                }
117            }
118            impl RandomSpec<$i> for RangeInclusive<$i> {
119                fn rand(&self, rng: &mut Xorshift) -> $i {
120                    assert!(self.start() <= self.end());
121                    let len = (self.end().abs_diff(*self.start())).wrapping_add(1);
122                    let x = rng.random::<$u, _>(..);
123                    self.start().wrapping_add_unsigned(if len != 0 { x % len } else { x })
124                }
125            }
126            impl RandomSpec<$u> for RangeTo<$u> {
127                fn rand(&self, rng: &mut Xorshift) -> $u {
128                    let len = self.end;
129                    rng.random::<$u, _>(..) % len
130                }
131            }
132            impl RandomSpec<$i> for RangeTo<$i> {
133                fn rand(&self, rng: &mut Xorshift) -> $i {
134                    let len = self.end.abs_diff($i::MIN);
135                    $i::MIN.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
136                }
137            }
138            impl RandomSpec<$u> for RangeToInclusive<$u> {
139                fn rand(&self, rng: &mut Xorshift) -> $u {
140                    let len = (self.end).wrapping_add(1);
141                    let x = rng.random::<$u, _>(..);
142                    if len != 0 { x % len } else { x }
143                }
144            }
145            impl RandomSpec<$i> for RangeToInclusive<$i> {
146                fn rand(&self, rng: &mut Xorshift) -> $i {
147                    let len = (self.end.abs_diff($i::MIN)).wrapping_add(1);
148                    let x = rng.random::<$u, _>(..);
149                    $i::MIN.wrapping_add_unsigned(if len != 0 { x % len } else { x })
150                }
151            }
152        )*
153    };
154}
155impl_random_spec_ranges!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
156
157macro_rules! impl_random_spec_tuple {
158    ($($T:ident)*, $($R:ident)*, $($v:ident)*) => {
159        impl<$($T),*, $($R),*> RandomSpec<($($T,)*)> for ($($R,)*)
160        where
161            $($R: RandomSpec<$T>),*
162        {
163            fn rand(&self, rng: &mut Xorshift) -> ($($T,)*) {
164                let ($($v,)*) = self;
165                ($(($v).rand(rng),)*)
166            }
167        }
168    };
169}
170impl_random_spec_tuple!(A, RA, a);
171impl_random_spec_tuple!(A B, RA RB, a b);
172impl_random_spec_tuple!(A B C, RA RB RC, a b c);
173impl_random_spec_tuple!(A B C D, RA RB RC RD, a b c d);
174impl_random_spec_tuple!(A B C D E, RA RB RC RD RE, a b c d e);
175impl_random_spec_tuple!(A B C D E F, RA RB RC RD RE RF, a b c d e f);
176impl_random_spec_tuple!(A B C D E F G, RA RB RC RD RE RF RG, a b c d e f g);
177impl_random_spec_tuple!(A B C D E F G H, RA RB RC RD RE RF RG RH, a b c d e f g h);
178impl_random_spec_tuple!(A B C D E F G H I, RA RB RC RD RE RF RG RH RI, a b c d e f g h i);
179impl_random_spec_tuple!(A B C D E F G H I J, RA RB RC RD RE RF RG RH RI RJ, a b c d e f g h i j);
180
181macro_rules! impl_random_spec_primitive {
182    ($($t:ty)*) => {
183        $(impl RandomSpec<$t> for $t {
184            fn rand(&self, _rng: &mut Xorshift) -> $t {
185                *self
186            }
187        })*
188    };
189}
190impl_random_spec_primitive!(() u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize bool char);
191
192impl<T, R> RandomSpec<T> for &R
193where
194    R: RandomSpec<T>,
195{
196    fn rand(&self, rng: &mut Xorshift) -> T {
197        <R as RandomSpec<T>>::rand(self, rng)
198    }
199}
200impl<T, R> RandomSpec<T> for &mut R
201where
202    R: RandomSpec<T>,
203{
204    fn rand(&self, rng: &mut Xorshift) -> T {
205        <R as RandomSpec<T>>::rand(self, rng)
206    }
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
210/// Left-close Right-open No Empty Segment
211pub struct NotEmptySegment<T>(pub T);
212impl<T> RandomSpec<(usize, usize)> for NotEmptySegment<T>
213where
214    T: RandomSpec<usize>,
215{
216    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
217        let n = rng.random(&self.0) as u64;
218        let k = randint_uniform(rng, n);
219        let l = randint_uniform(rng, n - k) as usize;
220        (l, l + k as usize + 1)
221    }
222}
223
224#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
225pub struct RandRange<Q, T> {
226    data: Q,
227    _marker: PhantomData<fn() -> T>,
228}
229impl<Q, T> RandRange<Q, T> {
230    pub fn new(data: Q) -> Self {
231        Self {
232            data,
233            _marker: PhantomData,
234        }
235    }
236}
237impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
238where
239    Q: RandomSpec<T>,
240    T: Ord,
241{
242    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
243        let mut l = rng.random(&self.data);
244        let mut r = rng.random(&self.data);
245        if l > r {
246            swap(&mut l, &mut r);
247        }
248        (
249            match rng.rand(3) {
250                0 => Bound::Excluded(l),
251                1 => Bound::Included(l),
252                _ => Bound::Unbounded,
253            },
254            match rng.rand(3) {
255                0 => Bound::Excluded(r),
256                1 => Bound::Included(r),
257                _ => Bound::Unbounded,
258            },
259        )
260    }
More examples
Hide additional examples
crates/competitive/src/tree/generator.rs (line 8)
7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
69        let n = rng.random(&self.0);
70        let edges = rand_inner(n, rng);
71        UndirectedSparseGraph::from_edges(n, edges)
72    }
crates/competitive/src/algorithm/automata_learning.rs (line 301)
289pub fn random_sampling(
290    sigma: usize,
291    len_spec: impl RandomSpec<usize>,
292    seconds: f64,
293) -> impl Iterator<Item = Vec<usize>> {
294    assert_ne!(sigma, 0, "Sigma must be greater than 0");
295    let now = Instant::now();
296    let mut rng = Xorshift::new();
297    from_fn(move || {
298        if now.elapsed().as_secs_f64() > seconds {
299            None
300        } else {
301            let n = rng.random(&len_spec);
302            Some(rng.random_iter(0..sigma).take(n).collect())
303        }
304    })
305}
Source

pub fn random_iter<T, R>(&mut self, spec: R) -> RandIter<'_, T, R> ⓘ
where R: RandomSpec<T>,

Examples found in repository?
crates/competitive/src/tree/generator.rs (line 11)
7    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
8        let n = rng.random(&self.0);
9        let edges = from_prufer_sequence(
10            n,
11            &rng.random_iter(0..n)
12                .take(n.saturating_sub(2))
13                .collect::<Vec<usize>>(),
14        );
15        UndirectedSparseGraph::from_edges(n, edges)
16    }
17}
18
19pub struct PathTree<T>(pub T);
20
21impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for PathTree<T> {
22    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
23        let n = rng.random(&self.0);
24        let edges = (1..n).map(|u| (u - 1, u)).collect();
25        UndirectedSparseGraph::from_edges(n, edges)
26    }
27}
28
29pub struct StarTree<T>(pub T);
30
31impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for StarTree<T> {
32    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
33        let n = rng.random(&self.0);
34        let edges = (1..n).map(|u| (0, u)).collect();
35        UndirectedSparseGraph::from_edges(n, edges)
36    }
37}
38
39pub struct MixedTree<T>(pub T);
40
41impl<T: RandomSpec<usize>> RandomSpec<UndirectedSparseGraph> for MixedTree<T> {
42    fn rand(&self, rng: &mut Xorshift) -> UndirectedSparseGraph {
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
More examples
Hide additional examples
crates/competitive/src/algorithm/automata_learning.rs (line 302)
289pub fn random_sampling(
290    sigma: usize,
291    len_spec: impl RandomSpec<usize>,
292    seconds: f64,
293) -> impl Iterator<Item = Vec<usize>> {
294    assert_ne!(sigma, 0, "Sigma must be greater than 0");
295    let now = Instant::now();
296    let mut rng = Xorshift::new();
297    from_fn(move || {
298        if now.elapsed().as_secs_f64() > seconds {
299            None
300        } else {
301            let n = rng.random(&len_spec);
302            Some(rng.random_iter(0..sigma).take(n).collect())
303        }
304    })
305}
Source§

impl Xorshift

Source

pub fn new_with_seed(seed: u64) -> Self

Examples found in repository?
crates/competitive/src/tools/xorshift.rs (line 18)
17    pub fn new() -> Self {
18        Xorshift::new_with_seed(RandomState::new().build_hasher().finish())
19    }
20
21    pub fn rand64(&mut self) -> u64 {
22        self.y ^= self.y << 5;
23        self.y ^= self.y >> 17;
24        self.y ^= self.y << 11;
25        self.y
26    }
27
28    pub fn rand(&mut self, k: u64) -> u64 {
29        self.rand64() % k
30    }
31
32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }
44
45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }
48
49    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
50        let mut n = slice.len();
51        while n > 1 {
52            let i = self.rand(n as _) as usize;
53            n -= 1;
54            slice.swap(i, n);
55        }
56    }
57}
58
59impl Default for Xorshift {
60    fn default() -> Self {
61        Xorshift::new_with_seed(0x2b99_2ddf_a232_49d6)
62    }
More examples
Hide additional examples
crates/competitive/src/tree/tree_hash.rs (line 47)
44    pub fn with_seed(seed: u64) -> Self {
45        Self {
46            rv: Vec::new(),
47            rng: Xorshift::new_with_seed(seed),
48        }
49    }
crates/competitive/src/heuristic/simurated_annealing.rs (line 30)
19    fn default() -> Self {
20        let now = std::time::Instant::now();
21        let log_table = (0..Self::LOG_TABLE_SIZE)
22            .map(|i| ((i * 2 + 1) as f64 / (Self::LOG_TABLE_SIZE * 2) as f64).ln())
23            .collect();
24        Self {
25            iter_count: 0,
26            now,
27            time: 0.,
28            temperture: 3e3,
29            log_table,
30            rand: Xorshift::new_with_seed(Self::SEED),
31            is_maximize: true,
32            start_temp: 3e3,
33            end_temp: 1e-8,
34            time_limit: 1.99,
35            update_interval: 0xff,
36        }
37    }
Source

pub fn new() -> Self

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 14)
13    fn init(len: usize) {
14        let mut rng = Xorshift::new();
15        Self::init_with_rng(len, &mut rng);
16    }
More examples
Hide additional examples
crates/competitive/src/tree/tree_hash.rs (line 41)
38    pub fn new() -> Self {
39        Self {
40            rv: Vec::new(),
41            rng: Xorshift::new(),
42        }
43    }
crates/competitive/src/data_structure/submask_range_query.rs (line 18)
17    pub fn new(bit_width: u32) -> Self {
18        let mut rng = Xorshift::new();
19        let mut mask = [0; 3];
20        let mut rem: Vec<_> = (0..bit_width).map(|w| w % 3).collect();
21        rng.shuffle(&mut rem);
22        for (k, r) in rem.into_iter().enumerate() {
23            mask[r as usize] |= 1 << k;
24        }
25        Self { bit_width, mask }
26    }
crates/competitive/src/algorithm/automata_learning.rs (line 296)
289pub fn random_sampling(
290    sigma: usize,
291    len_spec: impl RandomSpec<usize>,
292    seconds: f64,
293) -> impl Iterator<Item = Vec<usize>> {
294    assert_ne!(sigma, 0, "Sigma must be greater than 0");
295    let now = Instant::now();
296    let mut rng = Xorshift::new();
297    from_fn(move || {
298        if now.elapsed().as_secs_f64() > seconds {
299            None
300        } else {
301            let n = rng.random(&len_spec);
302            Some(rng.random_iter(0..sigma).take(n).collect())
303        }
304    })
305}
crates/competitive/src/math/mint_matrix.rs (line 23)
19    fn determinant_linear(mut self, other: Self) -> Option<Vec<MInt<M>>>
20    where
21        M: MIntConvert<usize> + MIntConvert<u64>,
22    {
23        let mut rng = Xorshift::new();
24        let a = MInt::from(rng.rand64());
25        let n = self.data.len();
26        for i in 0..n {
27            for j in 0..n {
28                self[i][j] += other[i][j] * a;
29            }
30        }
31        let mut f = other.determinant_linear_non_singular(self)?;
32        f.reverse();
33        Some(taylor_shift::<M>(f, -a))
34    }
crates/competitive/src/math/black_box_matrix.rs (line 222)
216    fn minimal_polynomial(&self) -> Vec<MInt<M>>
217    where
218        M: MIntConvert<u64>,
219    {
220        assert_eq!(self.shape().0, self.shape().1);
221        let n = self.shape().0;
222        let mut rng = Xorshift::new();
223        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
224        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
225        let a: Vec<MInt<M>> = (0..2 * n)
226            .scan(b, |b, _| {
227                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
228                *b = self.apply(b);
229                Some(a)
230            })
231            .collect();
232        let mut p = berlekamp_massey(&a);
233        p.reverse();
234        p
235    }
236
237    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
238    where
239        M: MIntConvert<usize> + MIntConvert<u64>,
240        C: ConvolveSteps<T = Vec<MInt<M>>>,
241    {
242        assert_eq!(self.shape().0, self.shape().1);
243        assert_eq!(self.shape().1, b.len());
244        let n = self.shape().0;
245        let p = self.minimal_polynomial();
246        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
247        let mut res = vec![MInt::zero(); n];
248        for f in f {
249            for j in 0..n {
250                res[j] += f * b[j];
251            }
252            b = self.apply(&b);
253        }
254        res
255    }
256
257    fn black_box_determinant(&self) -> MInt<M>
258    where
259        M: MIntConvert<u64>,
260    {
261        assert_eq!(self.shape().0, self.shape().1);
262        let n = self.shape().0;
263        let mut rng = Xorshift::new();
264        let d: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
265        let det_d = d.iter().fold(MInt::one(), |s, x| s * x);
266        let ad = BlackBoxMatrixImpl::<AddMulOperation<MInt<M>>, _>::new(
267            self.shape(),
268            |v: &[MInt<M>]| {
269                let mut w = self.apply(v);
270                for (w, d) in w.iter_mut().zip(&d) {
271                    *w *= d;
272                }
273                w
274            },
275        );
276        let p = ad.minimal_polynomial();
277        let det_ad = if n % 2 == 0 { p[0] } else { -p[0] };
278        det_ad / det_d
279    }
Additional examples can be found in:
Source

pub fn rand64(&mut self) -> u64

Examples found in repository?
crates/competitive/src/tools/xorshift.rs (line 29)
28    pub fn rand(&mut self, k: u64) -> u64 {
29        self.rand64() % k
30    }
31
32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }
More examples
Hide additional examples
crates/competitive/src/tools/random_generator.rs (line 70)
69    fn rand(&self, rng: &mut Xorshift) -> u128 {
70        ((rng.rand64() as u128) << 64) | rng.rand64() as u128
71    }
72}
73impl RandomSpec<i128> for RangeFull {
74    fn rand(&self, rng: &mut Xorshift) -> i128 {
75        rng.random::<u128, _>(..) as i128
76    }
77}
78
79macro_rules! impl_random_spec_ranges {
80    ($($u:ident $i:ident)*) => {
81        $(
82            impl RandomSpec<$u> for Range<$u> {
83                fn rand(&self, rng: &mut Xorshift) -> $u {
84                    assert!(self.start < self.end);
85                    let len = self.end - self.start;
86                    (self.start + rng.random::<$u, _>(..) % len)
87                }
88            }
89            impl RandomSpec<$i> for Range<$i> {
90                fn rand(&self, rng: &mut Xorshift) -> $i {
91                    assert!(self.start < self.end);
92                    let len = self.end.abs_diff(self.start);
93                    self.start.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
94                }
95            }
96            impl RandomSpec<$u> for RangeFrom<$u> {
97                fn rand(&self, rng: &mut Xorshift) -> $u {
98                    let len = ($u::MAX - self.start).wrapping_add(1);
99                    let x = rng.random::<$u, _>(..);
100                    self.start + if len != 0 { x % len } else { x }
101                }
102            }
103            impl RandomSpec<$i> for RangeFrom<$i> {
104                fn rand(&self, rng: &mut Xorshift) -> $i {
105                    let len = ($i::MAX.abs_diff(self.start)).wrapping_add(1);
106                    let x = rng.random::<$u, _>(..);
107                    self.start.wrapping_add_unsigned(if len != 0 { x % len } else { x })
108                }
109            }
110            impl RandomSpec<$u> for RangeInclusive<$u> {
111                fn rand(&self, rng: &mut Xorshift) -> $u {
112                    assert!(self.start() <= self.end());
113                    let len = (self.end() - self.start()).wrapping_add(1);
114                    let x = rng.random::<$u, _>(..);
115                    self.start() + if len != 0 { x % len } else { x }
116                }
117            }
118            impl RandomSpec<$i> for RangeInclusive<$i> {
119                fn rand(&self, rng: &mut Xorshift) -> $i {
120                    assert!(self.start() <= self.end());
121                    let len = (self.end().abs_diff(*self.start())).wrapping_add(1);
122                    let x = rng.random::<$u, _>(..);
123                    self.start().wrapping_add_unsigned(if len != 0 { x % len } else { x })
124                }
125            }
126            impl RandomSpec<$u> for RangeTo<$u> {
127                fn rand(&self, rng: &mut Xorshift) -> $u {
128                    let len = self.end;
129                    rng.random::<$u, _>(..) % len
130                }
131            }
132            impl RandomSpec<$i> for RangeTo<$i> {
133                fn rand(&self, rng: &mut Xorshift) -> $i {
134                    let len = self.end.abs_diff($i::MIN);
135                    $i::MIN.wrapping_add_unsigned(rng.random::<$u, _>(..) % len)
136                }
137            }
138            impl RandomSpec<$u> for RangeToInclusive<$u> {
139                fn rand(&self, rng: &mut Xorshift) -> $u {
140                    let len = (self.end).wrapping_add(1);
141                    let x = rng.random::<$u, _>(..);
142                    if len != 0 { x % len } else { x }
143                }
144            }
145            impl RandomSpec<$i> for RangeToInclusive<$i> {
146                fn rand(&self, rng: &mut Xorshift) -> $i {
147                    let len = (self.end.abs_diff($i::MIN)).wrapping_add(1);
148                    let x = rng.random::<$u, _>(..);
149                    $i::MIN.wrapping_add_unsigned(if len != 0 { x % len } else { x })
150                }
151            }
152        )*
153    };
154}
155impl_random_spec_ranges!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
156
157macro_rules! impl_random_spec_tuple {
158    ($($T:ident)*, $($R:ident)*, $($v:ident)*) => {
159        impl<$($T),*, $($R),*> RandomSpec<($($T,)*)> for ($($R,)*)
160        where
161            $($R: RandomSpec<$T>),*
162        {
163            fn rand(&self, rng: &mut Xorshift) -> ($($T,)*) {
164                let ($($v,)*) = self;
165                ($(($v).rand(rng),)*)
166            }
167        }
168    };
169}
170impl_random_spec_tuple!(A, RA, a);
171impl_random_spec_tuple!(A B, RA RB, a b);
172impl_random_spec_tuple!(A B C, RA RB RC, a b c);
173impl_random_spec_tuple!(A B C D, RA RB RC RD, a b c d);
174impl_random_spec_tuple!(A B C D E, RA RB RC RD RE, a b c d e);
175impl_random_spec_tuple!(A B C D E F, RA RB RC RD RE RF, a b c d e f);
176impl_random_spec_tuple!(A B C D E F G, RA RB RC RD RE RF RG, a b c d e f g);
177impl_random_spec_tuple!(A B C D E F G H, RA RB RC RD RE RF RG RH, a b c d e f g h);
178impl_random_spec_tuple!(A B C D E F G H I, RA RB RC RD RE RF RG RH RI, a b c d e f g h i);
179impl_random_spec_tuple!(A B C D E F G H I J, RA RB RC RD RE RF RG RH RI RJ, a b c d e f g h i j);
180
181macro_rules! impl_random_spec_primitive {
182    ($($t:ty)*) => {
183        $(impl RandomSpec<$t> for $t {
184            fn rand(&self, _rng: &mut Xorshift) -> $t {
185                *self
186            }
187        })*
188    };
189}
190impl_random_spec_primitive!(() u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize bool char);
191
192impl<T, R> RandomSpec<T> for &R
193where
194    R: RandomSpec<T>,
195{
196    fn rand(&self, rng: &mut Xorshift) -> T {
197        <R as RandomSpec<T>>::rand(self, rng)
198    }
199}
200impl<T, R> RandomSpec<T> for &mut R
201where
202    R: RandomSpec<T>,
203{
204    fn rand(&self, rng: &mut Xorshift) -> T {
205        <R as RandomSpec<T>>::rand(self, rng)
206    }
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
210/// Left-close Right-open No Empty Segment
211pub struct NotEmptySegment<T>(pub T);
212impl<T> RandomSpec<(usize, usize)> for NotEmptySegment<T>
213where
214    T: RandomSpec<usize>,
215{
216    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
217        let n = rng.random(&self.0) as u64;
218        let k = randint_uniform(rng, n);
219        let l = randint_uniform(rng, n - k) as usize;
220        (l, l + k as usize + 1)
221    }
222}
223
224#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
225pub struct RandRange<Q, T> {
226    data: Q,
227    _marker: PhantomData<fn() -> T>,
228}
229impl<Q, T> RandRange<Q, T> {
230    pub fn new(data: Q) -> Self {
231        Self {
232            data,
233            _marker: PhantomData,
234        }
235    }
236}
237impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
238where
239    Q: RandomSpec<T>,
240    T: Ord,
241{
242    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
243        let mut l = rng.random(&self.data);
244        let mut r = rng.random(&self.data);
245        if l > r {
246            swap(&mut l, &mut r);
247        }
248        (
249            match rng.rand(3) {
250                0 => Bound::Excluded(l),
251                1 => Bound::Included(l),
252                _ => Bound::Unbounded,
253            },
254            match rng.rand(3) {
255                0 => Bound::Excluded(r),
256                1 => Bound::Included(r),
257                _ => Bound::Unbounded,
258            },
259        )
260    }
261}
262
263#[inline]
264fn randint_uniform(rng: &mut Xorshift, k: u64) -> u64 {
265    let mut v = rng.rand64();
266    if k > 0 {
267        v %= k;
268    }
269    v
270}
crates/competitive/src/tree/tree_hash.rs (line 64)
61    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
62        let mut s = 1u64;
63        if self.rv.len() <= d {
64            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
65        }
66        for a in g.adjacencies(u) {
67            if a.to != p {
68                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
69            }
70        }
71        s += self.rv[d];
72        if s >= Self::MOD {
73            s -= Self::MOD;
74        }
75        s
76    }
crates/competitive/src/math/mint_matrix.rs (line 24)
19    fn determinant_linear(mut self, other: Self) -> Option<Vec<MInt<M>>>
20    where
21        M: MIntConvert<usize> + MIntConvert<u64>,
22    {
23        let mut rng = Xorshift::new();
24        let a = MInt::from(rng.rand64());
25        let n = self.data.len();
26        for i in 0..n {
27            for j in 0..n {
28                self[i][j] += other[i][j] * a;
29            }
30        }
31        let mut f = other.determinant_linear_non_singular(self)?;
32        f.reverse();
33        Some(taylor_shift::<M>(f, -a))
34    }
crates/competitive/src/math/black_box_matrix.rs (line 223)
216    fn minimal_polynomial(&self) -> Vec<MInt<M>>
217    where
218        M: MIntConvert<u64>,
219    {
220        assert_eq!(self.shape().0, self.shape().1);
221        let n = self.shape().0;
222        let mut rng = Xorshift::new();
223        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
224        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
225        let a: Vec<MInt<M>> = (0..2 * n)
226            .scan(b, |b, _| {
227                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
228                *b = self.apply(b);
229                Some(a)
230            })
231            .collect();
232        let mut p = berlekamp_massey(&a);
233        p.reverse();
234        p
235    }
236
237    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
238    where
239        M: MIntConvert<usize> + MIntConvert<u64>,
240        C: ConvolveSteps<T = Vec<MInt<M>>>,
241    {
242        assert_eq!(self.shape().0, self.shape().1);
243        assert_eq!(self.shape().1, b.len());
244        let n = self.shape().0;
245        let p = self.minimal_polynomial();
246        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
247        let mut res = vec![MInt::zero(); n];
248        for f in f {
249            for j in 0..n {
250                res[j] += f * b[j];
251            }
252            b = self.apply(&b);
253        }
254        res
255    }
256
257    fn black_box_determinant(&self) -> MInt<M>
258    where
259        M: MIntConvert<u64>,
260    {
261        assert_eq!(self.shape().0, self.shape().1);
262        let n = self.shape().0;
263        let mut rng = Xorshift::new();
264        let d: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
265        let det_d = d.iter().fold(MInt::one(), |s, x| s * x);
266        let ad = BlackBoxMatrixImpl::<AddMulOperation<MInt<M>>, _>::new(
267            self.shape(),
268            |v: &[MInt<M>]| {
269                let mut w = self.apply(v);
270                for (w, d) in w.iter_mut().zip(&d) {
271                    *w *= d;
272                }
273                w
274            },
275        );
276        let p = ad.minimal_polynomial();
277        let det_ad = if n % 2 == 0 { p[0] } else { -p[0] };
278        det_ad / det_d
279    }
Source

pub fn rand(&mut self, k: u64) -> u64

Examples found in repository?
crates/competitive/src/tools/xorshift.rs (line 33)
32    pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64> {
33        repeat_with(|| self.rand(k)).take(n).collect()
34    }
35
36    pub fn randf(&mut self) -> f64 {
37        const UPPER_MASK: u64 = 0x3FF0_0000_0000_0000;
38        const LOWER_MASK: u64 = 0x000F_FFFF_FFFF_FFFF;
39        let x = self.rand64();
40        let tmp = UPPER_MASK | (x & LOWER_MASK);
41        let result: f64 = f64::from_bits(tmp);
42        f64::from_bits(f64::to_bits(result - 1.0) ^ (x >> 63))
43    }
44
45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }
48
49    pub fn shuffle<T>(&mut self, slice: &mut [T]) {
50        let mut n = slice.len();
51        while n > 1 {
52            let i = self.rand(n as _) as usize;
53            n -= 1;
54            slice.swap(i, n);
55        }
56    }
More examples
Hide additional examples
crates/competitive/src/heuristic/simurated_annealing.rs (line 77)
69    pub fn is_accepted(&mut self, current_score: f64, next_score: f64) -> bool {
70        let diff = if self.is_maximize {
71            next_score - current_score
72        } else {
73            current_score - next_score
74        };
75        diff >= 0.
76            || diff
77                > self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64) as usize]
78                    * self.temperture
79    }
crates/competitive/src/tools/random_generator.rs (line 249)
242    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
243        let mut l = rng.random(&self.data);
244        let mut r = rng.random(&self.data);
245        if l > r {
246            swap(&mut l, &mut r);
247        }
248        (
249            match rng.rand(3) {
250                0 => Bound::Excluded(l),
251                1 => Bound::Included(l),
252                _ => Bound::Unbounded,
253            },
254            match rng.rand(3) {
255                0 => Bound::Excluded(r),
256                1 => Bound::Included(r),
257                _ => Bound::Unbounded,
258            },
259        )
260    }
crates/competitive/src/tree/generator.rs (line 48)
43        fn rand_inner(n: usize, rng: &mut Xorshift) -> Vec<(usize, usize)> {
44            let mut edges = Vec::with_capacity(n.saturating_sub(1));
45            if n >= 2 {
46                let k = rng.random(1..n);
47                for n in [k, n - k].iter().cloned() {
48                    let ty = rng.rand(6);
49                    edges.extend(match ty {
50                        0 => from_prufer_sequence(
51                            n,
52                            &rng.random_iter(0..n)
53                                .take(n.saturating_sub(2))
54                                .collect::<Vec<usize>>(),
55                        ),
56                        1 => (1..n).map(|u| (u - 1, u)).collect(),
57                        2 => (1..n).map(|u| (0, u)).collect(),
58                        _ => rand_inner(n, rng),
59                    });
60                }
61                for (u, v) in edges[k - 1..].iter_mut() {
62                    *u += k;
63                    *v += k;
64                }
65                edges.push((rng.random(0..k), rng.random(k..n)));
66            }
67            edges
68        }
crates/competitive/src/math/discrete_logarithm.rs (line 202)
182fn index_calculus_for_primitive_root(
183    p: u64,
184    ord: u64,
185    br_primes: &[BarrettReduction<u64>],
186    prec: &QdrtPowPrec,
187) -> Vec<u64> {
188    let br_ord = BarrettReduction::<u128>::new(ord as u128);
189    let mul = |x: u64, y: u64| br_ord.rem(x as u128 * y as u128) as u64;
190    let sub = |x: u64, y: u64| if x < y { x + ord - y } else { x - y };
191
192    let pc = br_primes.len();
193    let mut mat: Vec<Vec<u64>> = vec![];
194    let mut rows: Vec<Vec<u64>> = vec![];
195
196    let mut rng = Xorshift::default();
197    let br = BarrettReduction::<u128>::new(p as u128);
198
199    for i in 0..pc {
200        for ri in 0usize.. {
201            let mut row = vec![0u64; pc + 1];
202            let mut kk = rng.rand(ord - 1) + 1;
203            let mut gkk = prec.pow(kk, &br);
204            let mut k = kk;
205            let mut gk = gkk;
206            while ri >= rows.len() {
207                row[pc] = k;
208                if factorize_smooth(gk, &mut row, br_primes) {
209                    rows.push(row);
210                    break;
211                }
212                if k + kk < ord {
213                    k += kk;
214                    gk = br.rem(gk as u128 * gkk as u128) as u64;
215                } else {
216                    kk = rng.rand(ord - 1) + 1;
217                    gkk = prec.pow(kk, &br);
218                    k = kk;
219                    gk = gkk;
220                }
221            }
222            let row = &mut rows[ri];
223            for j in 0..i {
224                if row[j] != 0 {
225                    let b = mul(modinv(mat[j][j], ord), row[j]);
226                    for (r, a) in row[j..].iter_mut().zip(&mat[j][j..]) {
227                        *r = sub(*r, mul(*a, b));
228                    }
229                }
230                assert_eq!(row[j], 0);
231            }
232            if gcd(row[i], ord) == 1 {
233                let last = rows.len() - 1;
234                rows.swap(ri, last);
235                mat.push(rows.pop().unwrap());
236                break;
237            }
238        }
239    }
240    for i in (0..pc).rev() {
241        for j in i + 1..pc {
242            mat[i][pc] = sub(mat[i][pc], mul(mat[i][j], mat[j][pc]));
243        }
244        mat[i][pc] = mul(mat[i][pc], modinv(mat[i][i], ord));
245    }
246    (0..pc).map(|i| mat[i][pc]).collect()
247}
248
249#[derive(Debug)]
250struct IndexCalculusWithPrimitiveRoot {
251    p: u64,
252    ord: u64,
253    prec: QdrtPowPrec,
254    coeff: Vec<u64>,
255}
256
257impl IndexCalculusWithPrimitiveRoot {
258    fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self {
259        let ord = p - 1;
260        let g = primitive_root(p);
261        let br = BarrettReduction::<u128>::new(p as u128);
262        let prec = QdrtPowPrec::new(g, ord, &br);
263        let coeff = index_calculus_for_primitive_root(p, ord, br_primes, &prec);
264        Self {
265            p,
266            ord,
267            prec,
268            coeff,
269        }
270    }
271    fn index_calculus(&self, a: u64, br_primes: &[BarrettReduction<u64>]) -> Option<u64> {
272        let p = self.p;
273        let ord = self.ord;
274        let br = BarrettReduction::<u128>::new(p as u128);
275        let a = br.rem(a as _) as u64;
276        if a == 1 {
277            return Some(0);
278        }
279        if p == 2 {
280            return None;
281        }
282
283        let mut rng = Xorshift::new();
284        let mut row = vec![0u64; br_primes.len()];
285        let mut kk = rng.rand(ord - 1) + 1;
286        let mut gkk = self.prec.pow(kk, &br);
287        let mut k = kk;
288        let mut gk = br.rem(gkk as u128 * a as u128) as u64;
289        loop {
290            if factorize_smooth(gk, &mut row, br_primes) {
291                let mut res = ord - k;
292                for (&c, &r) in self.coeff.iter().zip(&row) {
293                    for _ in 0..r {
294                        res += c;
295                        if res >= ord {
296                            res -= ord;
297                        }
298                    }
299                }
300                return Some(res);
301            }
302            if k + kk < ord {
303                k += kk;
304                gk = br.rem(gk as u128 * gkk as u128) as u64;
305            } else {
306                kk = rng.rand(ord - 1) + 1;
307                gkk = self.prec.pow(kk, &br);
308                k = kk;
309                gk = br.rem(gkk as u128 * a as u128) as u64;
310            }
311        }
312    }
Source

pub fn rands(&mut self, k: u64, n: usize) -> Vec<u64>

Source

pub fn randf(&mut self) -> f64

Examples found in repository?
crates/competitive/src/tools/xorshift.rs (line 46)
45    pub fn gen_bool(&mut self, p: f64) -> bool {
46        self.randf() < p
47    }
Source

pub fn gen_bool(&mut self, p: f64) -> bool

Source

pub fn shuffle<T>(&mut self, slice: &mut [T])

Examples found in repository?
crates/competitive/src/data_structure/submask_range_query.rs (line 21)
17    pub fn new(bit_width: u32) -> Self {
18        let mut rng = Xorshift::new();
19        let mut mask = [0; 3];
20        let mut rem: Vec<_> = (0..bit_width).map(|w| w % 3).collect();
21        rng.shuffle(&mut rem);
22        for (k, r) in rem.into_iter().enumerate() {
23            mask[r as usize] |= 1 << k;
24        }
25        Self { bit_width, mask }
26    }

Trait Implementations§

Source§

impl Clone for Xorshift

Source§

fn clone(&self) -> Xorshift

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for Xorshift

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Default for Xorshift

Source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.