malachite_base/bools/
random.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::Parity;
10use crate::num::random::geometric::SimpleRational;
11use crate::num::random::{
12    RandomUnsignedsLessThan, VariableRangeGenerator, random_unsigneds_less_than,
13};
14use crate::random::Seed;
15use rand::Rng;
16use rand_chacha::ChaCha20Rng;
17
18/// Uniformly generates random [`bool`]s.
19///
20/// This `struct` is created by [`random_bools`]; see its documentation for more.
21#[derive(Clone, Debug)]
22pub struct RandomBools {
23    rng: ChaCha20Rng,
24    x: u32,
25    bits_left: u8,
26}
27
28impl Iterator for RandomBools {
29    type Item = bool;
30
31    #[inline]
32    fn next(&mut self) -> Option<bool> {
33        if self.bits_left == 0 {
34            self.x = self.rng.random();
35            self.bits_left = 31;
36        } else {
37            self.x >>= 1;
38            self.bits_left -= 1;
39        }
40        Some(self.x.odd())
41    }
42}
43
44/// Uniformly generates random [`bool`]s.
45///
46/// $P(\text{false}) = P(\text{true}) = \frac{1}{2}$.
47///
48/// The output length is infinite.
49///
50/// # Worst-case complexity per iteration
51/// Constant time and additional memory.
52///
53/// # Examples
54/// ```
55/// use malachite_base::bools::random::random_bools;
56/// use malachite_base::iterators::prefix_to_string;
57/// use malachite_base::random::EXAMPLE_SEED;
58///
59/// assert_eq!(
60///     prefix_to_string(random_bools(EXAMPLE_SEED), 10),
61///     "[true, false, false, false, true, true, true, false, true, true, ...]"
62/// )
63/// ```
64///
65/// # Notes
66/// The resulting iterator uses every random bit generated by the PRNG, unlike some implementations
67/// which only use one bit out of 32 or 64.
68#[inline]
69pub fn random_bools(seed: Seed) -> RandomBools {
70    RandomBools {
71        rng: seed.get_rng(),
72        x: 0,
73        bits_left: 0,
74    }
75}
76
77/// Generates random [`bool`]s, with a fixed probability of generating `true`.
78///
79/// This `struct` is created by [`weighted_random_bools`]; see its documentation for more.
80#[derive(Clone, Debug)]
81pub struct WeightedRandomBools {
82    numerator: u64,
83    xs: RandomUnsignedsLessThan<u64>,
84}
85
86impl Iterator for WeightedRandomBools {
87    type Item = bool;
88
89    #[inline]
90    fn next(&mut self) -> Option<bool> {
91        Some(self.xs.next().unwrap() < self.numerator)
92    }
93}
94
95/// Generates random [`bool`]s, with a fixed probability of generating `true`.
96///
97/// Let $n_p$ be `p_numerator`, $d_p$ be `p_denominator`, and let $p=n_p/d_p$. Then
98///
99/// $P(\text{true}) = p$,
100///
101/// $P(\text{false}) = 1-p$.
102///
103/// The output length is infinite.
104///
105/// # Panics
106/// Panics if `p_denominator` is 0 or `p_numerator > p_denominator`.
107///
108/// # Expected complexity per iteration
109/// $T(n) = O(n)$
110///
111/// $M(n) = O(1)$
112///
113/// where $T$ is time, $M$ is additional memory, and $n$ is `p_denominator.significant_bits()`.
114///
115/// # Examples
116/// ```
117/// use malachite_base::bools::random::weighted_random_bools;
118/// use malachite_base::iterators::prefix_to_string;
119/// use malachite_base::random::EXAMPLE_SEED;
120///
121/// assert_eq!(
122///     prefix_to_string(weighted_random_bools(EXAMPLE_SEED, 3, 4), 10),
123///     "[true, true, false, true, false, false, true, false, true, true, ...]"
124/// )
125/// ```
126pub fn weighted_random_bools(
127    seed: Seed,
128    p_numerator: u64,
129    p_denominator: u64,
130) -> WeightedRandomBools {
131    assert!(p_numerator <= p_denominator);
132    let p = SimpleRational::new(p_numerator, p_denominator);
133    WeightedRandomBools {
134        numerator: p.n,
135        xs: random_unsigneds_less_than(seed, p.d),
136    }
137}
138
139/// Generates a random [`bool`] with a particular probability of being `true`.
140///
141/// Let $n_p$ be `p_numerator`, $d_p$ be `p_denominator`, and let $p=n_p/d_p$. Then
142///
143/// $P(\text{true}) = p$,
144///
145/// $P(\text{false}) = 1-p$.
146///
147/// # Panics
148/// Panics if `p_denominator` is 0 or `p_numerator > p_denominator`.
149///
150/// # Expected complexity
151/// $T(n) = O(n)$
152///
153/// $M(n) = O(1)$
154///
155/// where $T$ is time, $M$ is additional memory, and $n$ is `p_denominator.significant_bits()`.
156///
157/// # Examples
158/// ```
159/// use malachite_base::bools::random::get_weighted_random_bool;
160/// use malachite_base::num::random::VariableRangeGenerator;
161/// use malachite_base::random::EXAMPLE_SEED;
162///
163/// assert_eq!(
164///     get_weighted_random_bool(&mut VariableRangeGenerator::new(EXAMPLE_SEED), 1, 10),
165///     false
166/// );
167/// ```
168pub fn get_weighted_random_bool(
169    range_generator: &mut VariableRangeGenerator,
170    p_numerator: u64,
171    p_denominator: u64,
172) -> bool {
173    assert_ne!(p_denominator, 0);
174    assert!(p_numerator <= p_denominator);
175    if p_numerator == 0 {
176        return false;
177    } else if p_numerator == p_denominator {
178        return true;
179    }
180    let p = SimpleRational::new(p_numerator, p_denominator);
181    range_generator.next_less_than(p.d) < p.n
182}
malachite_base/bools/random.rs

malachite_base/bools/
random.rs
