Struct Xorshift

Source

pub struct Xorshift {
    y: u64,
}

Fields§

§y: u64

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)]
225/// Left-close Right-open Segment
226pub struct WithEmptySegment<T>(pub T);
227impl<T> RandomSpec<(usize, usize)> for WithEmptySegment<T>
228where
229    T: RandomSpec<usize>,
230{
231    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
232        let n = rng.random(&self.0) as u64;
233        let k = randint_uniform(rng, n + 1);
234        let l = randint_uniform(rng, n - k + 1) as usize;
235        (l, l + k as usize)
236    }
237}
238
239#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
240pub struct RandRange<Q, T> {
241    data: Q,
242    _marker: PhantomData<fn() -> T>,
243}
244impl<Q, T> RandRange<Q, T> {
245    pub fn new(data: Q) -> Self {
246        Self {
247            data,
248            _marker: PhantomData,
249        }
250    }
251}
252impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
253where
254    Q: RandomSpec<T>,
255    T: Ord,
256{
257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }

More examples

Hide additional examples

crates/competitive/src/num/mint/mod.rs (line 34)

33        fn rand(&self, rng: &mut Xorshift) -> MInt<M> {
34            MInt::<M>::new_unchecked(rng.random(..M::get_mod()))
35        }

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 289)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

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 290)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

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/simulated_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/treap.rs (line 257)

253    fn default() -> Self {
254        Self {
255            root: None,
256            node_id_manager: Default::default(),
257            rng: Xorshift::new(),
258            allocator: ManuallyDrop::new(A::default()),
259            _marker: PhantomData,
260        }
261    }

crates/competitive/src/algorithm/automata_learning.rs (line 284)

277pub fn random_sampling(
278    sigma: usize,
279    len_spec: impl RandomSpec<usize>,
280    seconds: f64,
281) -> impl Iterator<Item = Vec<usize>> {
282    assert_ne!(sigma, 0, "Sigma must be greater than 0");
283    let now = Instant::now();
284    let mut rng = Xorshift::new();
285    from_fn(move || {
286        if now.elapsed().as_secs_f64() > seconds {
287            None
288        } else {
289            let n = rng.random(&len_spec);
290            Some(rng.random_iter(0..sigma).take(n).collect())
291        }
292    })
293}

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 220)

214    fn minimal_polynomial(&self) -> Vec<MInt<M>>
215    where
216        M: MIntConvert<u64>,
217    {
218        assert_eq!(self.shape().0, self.shape().1);
219        let n = self.shape().0;
220        let mut rng = Xorshift::new();
221        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
222        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
223        let a: Vec<MInt<M>> = (0..2 * n)
224            .scan(b, |b, _| {
225                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
226                *b = self.apply(b);
227                Some(a)
228            })
229            .collect();
230        let mut p = berlekamp_massey(&a);
231        p.reverse();
232        p
233    }
234
235    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
236    where
237        M: MIntConvert<usize> + MIntConvert<isize> + MIntConvert<u64>,
238        C: ConvolveSteps<T = Vec<MInt<M>>>,
239    {
240        assert_eq!(self.shape().0, self.shape().1);
241        assert_eq!(self.shape().1, b.len());
242        let n = self.shape().0;
243        let p = self.minimal_polynomial();
244        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
245        let mut res = vec![MInt::zero(); n];
246        for f in f {
247            for j in 0..n {
248                res[j] += f * b[j];
249            }
250            b = self.apply(&b);
251        }
252        res
253    }
254
255    fn black_box_determinant(&self) -> MInt<M>
256    where
257        M: MIntConvert<u64>,
258    {
259        assert_eq!(self.shape().0, self.shape().1);
260        let n = self.shape().0;
261        let mut rng = Xorshift::new();
262        let d: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
263        let det_d = d.iter().fold(MInt::one(), |s, x| s * x);
264        let ad = BlackBoxMatrixImpl::<AddMulOperation<MInt<M>>, _>::new(
265            self.shape(),
266            |v: &[MInt<M>]| {
267                let mut w = self.apply(v);
268                for (w, d) in w.iter_mut().zip(&d) {
269                    *w *= d;
270                }
271                w
272            },
273        );
274        let p = ad.minimal_polynomial();
275        let det_ad = if n % 2 == 0 { p[0] } else { -p[0] };
276        det_ad / det_d
277    }

Additional examples can be found in:

crates/competitive/src/math/discrete_logarithm.rs

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)]
225/// Left-close Right-open Segment
226pub struct WithEmptySegment<T>(pub T);
227impl<T> RandomSpec<(usize, usize)> for WithEmptySegment<T>
228where
229    T: RandomSpec<usize>,
230{
231    fn rand(&self, rng: &mut Xorshift) -> (usize, usize) {
232        let n = rng.random(&self.0) as u64;
233        let k = randint_uniform(rng, n + 1);
234        let l = randint_uniform(rng, n - k + 1) as usize;
235        (l, l + k as usize)
236    }
237}
238
239#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
240pub struct RandRange<Q, T> {
241    data: Q,
242    _marker: PhantomData<fn() -> T>,
243}
244impl<Q, T> RandRange<Q, T> {
245    pub fn new(data: Q) -> Self {
246        Self {
247            data,
248            _marker: PhantomData,
249        }
250    }
251}
252impl<Q, T> RandomSpec<(Bound<T>, Bound<T>)> for RandRange<Q, T>
253where
254    Q: RandomSpec<T>,
255    T: Ord,
256{
257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }
276}
277
278#[inline]
279fn randint_uniform(rng: &mut Xorshift, k: u64) -> u64 {
280    let mut v = rng.rand64();
281    if k > 0 {
282        v %= k;
283    }
284    v
285}

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/data_structure/treap.rs (line 374)

371    pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
372        let (left, right) = TreapSpec::split(self.root.take(), SeekByKey::new(&key), false);
373        let data = TreapData {
374            priority: self.rng.rand64(),
375            key: MonoidActElement::from_key(key),
376            value: LazyMapElement::from_key(value),
377        };
378        let node = BstRoot::from_data(data, self.allocator.deref_mut());
379        let node_id = self.node_id_manager.register(&node);
380        self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
381        node_id
382    }

crates/competitive/src/math/black_box_matrix.rs (line 221)

214    fn minimal_polynomial(&self) -> Vec<MInt<M>>
215    where
216        M: MIntConvert<u64>,
217    {
218        assert_eq!(self.shape().0, self.shape().1);
219        let n = self.shape().0;
220        let mut rng = Xorshift::new();
221        let b: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
222        let u: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
223        let a: Vec<MInt<M>> = (0..2 * n)
224            .scan(b, |b, _| {
225                let a = b.iter().zip(&u).fold(MInt::zero(), |s, (x, y)| s + x * y);
226                *b = self.apply(b);
227                Some(a)
228            })
229            .collect();
230        let mut p = berlekamp_massey(&a);
231        p.reverse();
232        p
233    }
234
235    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
236    where
237        M: MIntConvert<usize> + MIntConvert<isize> + MIntConvert<u64>,
238        C: ConvolveSteps<T = Vec<MInt<M>>>,
239    {
240        assert_eq!(self.shape().0, self.shape().1);
241        assert_eq!(self.shape().1, b.len());
242        let n = self.shape().0;
243        let p = self.minimal_polynomial();
244        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
245        let mut res = vec![MInt::zero(); n];
246        for f in f {
247            for j in 0..n {
248                res[j] += f * b[j];
249            }
250            b = self.apply(&b);
251        }
252        res
253    }
254
255    fn black_box_determinant(&self) -> MInt<M>
256    where
257        M: MIntConvert<u64>,
258    {
259        assert_eq!(self.shape().0, self.shape().1);
260        let n = self.shape().0;
261        let mut rng = Xorshift::new();
262        let d: Vec<MInt<M>> = (0..n).map(|_| MInt::from(rng.rand64())).collect();
263        let det_d = d.iter().fold(MInt::one(), |s, x| s * x);
264        let ad = BlackBoxMatrixImpl::<AddMulOperation<MInt<M>>, _>::new(
265            self.shape(),
266            |v: &[MInt<M>]| {
267                let mut w = self.apply(v);
268                for (w, d) in w.iter_mut().zip(&d) {
269                    *w *= d;
270                }
271                w
272            },
273        );
274        let p = ad.minimal_polynomial();
275        let det_ad = if n % 2 == 0 { p[0] } else { -p[0] };
276        det_ad / det_d
277    }

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/simulated_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    }
80    pub fn accepted_score(&mut self, current_score: f64) -> f64 {
81        let bound =
82            self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64) as usize] * self.temperture;
83        if self.is_maximize {
84            current_score + bound
85        } else {
86            current_score - bound
87        }
88    }

crates/competitive/src/tools/random_generator.rs (line 264)

257    fn rand(&self, rng: &mut Xorshift) -> (Bound<T>, Bound<T>) {
258        let mut l = rng.random(&self.data);
259        let mut r = rng.random(&self.data);
260        if l > r {
261            swap(&mut l, &mut r);
262        }
263        (
264            match rng.rand(3) {
265                0 => Bound::Excluded(l),
266                1 => Bound::Included(l),
267                _ => Bound::Unbounded,
268            },
269            match rng.rand(3) {
270                0 => Bound::Excluded(r),
271                1 => Bound::Included(r),
272                _ => Bound::Unbounded,
273            },
274        )
275    }
276}
277
278#[inline]
279fn randint_uniform(rng: &mut Xorshift, k: u64) -> u64 {
280    let mut v = rng.rand64();
281    if k > 0 {
282        v %= k;
283    }
284    v
285}
286
287pub struct WeightedSampler {
288    n: usize,
289    prob: Vec<f64>,
290    alias: Vec<usize>,
291}
292
293impl WeightedSampler {
294    pub fn new(weights: impl IntoIterator<Item = f64>) -> Self {
295        let mut weights: Vec<_> = weights.into_iter().collect();
296        let n = weights.len();
297        assert!(n > 0, "weights must be non-empty");
298        let mut prob = vec![0.0; n];
299        let mut alias = vec![0; n];
300        let mut small = vec![];
301        let mut large = vec![];
302        let sum: f64 = weights.iter().sum();
303        assert!(sum > 0.0, "sum of weights must be positive");
304        for (i, weight) in weights.iter_mut().enumerate() {
305            assert!(*weight >= 0.0, "weights must be non-negative");
306            *weight *= n as f64 / sum;
307            if *weight < 1.0 {
308                small.push(i);
309            } else {
310                large.push(i);
311            }
312        }
313        loop {
314            match (small.pop(), large.pop()) {
315                (Some(l), Some(g)) => {
316                    prob[l] = weights[l];
317                    alias[l] = g;
318                    weights[g] -= 1.0 - weights[l];
319                    if weights[g] < 1.0 {
320                        small.push(g);
321                    } else {
322                        large.push(g);
323                    }
324                }
325                (Some(g), None) | (None, Some(g)) => {
326                    prob[g] = 1.0;
327                    alias[g] = g;
328                }
329                (None, None) => break,
330            }
331        }
332        Self { n, prob, alias }
333    }
334}
335
336impl RandomSpec<usize> for WeightedSampler {
337    fn rand(&self, rng: &mut Xorshift) -> usize {
338        let i = rng.rand(self.n as u64) as usize;
339        if rng.randf() < self.prob[i] {
340            i
341        } else {
342            self.alias[i]
343        }
344    }

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    }

More examples

Hide additional examples

crates/competitive/src/tools/random_generator.rs (line 339)

337    fn rand(&self, rng: &mut Xorshift) -> usize {
338        let i = rng.rand(self.n as u64) as usize;
339        if rng.randf() < self.prob[i] {
340            i
341        } else {
342            self.alias[i]
343        }
344    }

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::default();
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    }