1 // Copyright 2018 Developers of the Rand project. 2 // Copyright 2013-2017 The Rust Project Developers. 3 // 4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or 5 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license 6 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your 7 // option. This file may not be copied, modified, or distributed 8 // except according to those terms. 9 10 //! Generating random samples from probability distributions 11 //! 12 //! This module is the home of the [`Distribution`] trait and several of its 13 //! implementations. It is the workhorse behind some of the convenient 14 //! functionality of the [`Rng`] trait, e.g. [`Rng::gen`], [`Rng::gen_range`] and 15 //! of course [`Rng::sample`]. 16 //! 17 //! Abstractly, a [probability distribution] describes the probability of 18 //! occurance of each value in its sample space. 19 //! 20 //! More concretely, an implementation of `Distribution<T>` for type `X` is an 21 //! algorithm for choosing values from the sample space (a subset of `T`) 22 //! according to the distribution `X` represents, using an external source of 23 //! randomness (an RNG supplied to the `sample` function). 24 //! 25 //! A type `X` may implement `Distribution<T>` for multiple types `T`. 26 //! Any type implementing [`Distribution`] is stateless (i.e. immutable), 27 //! but it may have internal parameters set at construction time (for example, 28 //! [`Uniform`] allows specification of its sample space as a range within `T`). 29 //! 30 //! 31 //! # The `Standard` distribution 32 //! 33 //! The [`Standard`] distribution is important to mention. This is the 34 //! distribution used by [`Rng::gen`] and represents the "default" way to 35 //! produce a random value for many different types, including most primitive 36 //! types, tuples, arrays, and a few derived types. See the documentation of 37 //! [`Standard`] for more details. 38 //! 39 //! Implementing `Distribution<T>` for [`Standard`] for user types `T` makes it 40 //! possible to generate type `T` with [`Rng::gen`], and by extension also 41 //! with the [`random`] function. 42 //! 43 //! ## Random characters 44 //! 45 //! [`Alphanumeric`] is a simple distribution to sample random letters and 46 //! numbers of the `char` type; in contrast [`Standard`] may sample any valid 47 //! `char`. 48 //! 49 //! 50 //! # Uniform numeric ranges 51 //! 52 //! The [`Uniform`] distribution is more flexible than [`Standard`], but also 53 //! more specialised: it supports fewer target types, but allows the sample 54 //! space to be specified as an arbitrary range within its target type `T`. 55 //! Both [`Standard`] and [`Uniform`] are in some sense uniform distributions. 56 //! 57 //! Values may be sampled from this distribution using [`Rng::gen_range`] or 58 //! by creating a distribution object with [`Uniform::new`], 59 //! [`Uniform::new_inclusive`] or `From<Range>`. When the range limits are not 60 //! known at compile time it is typically faster to reuse an existing 61 //! distribution object than to call [`Rng::gen_range`]. 62 //! 63 //! User types `T` may also implement `Distribution<T>` for [`Uniform`], 64 //! although this is less straightforward than for [`Standard`] (see the 65 //! documentation in the [`uniform`] module. Doing so enables generation of 66 //! values of type `T` with [`Rng::gen_range`]. 67 //! 68 //! ## Open and half-open ranges 69 //! 70 //! There are surprisingly many ways to uniformly generate random floats. A 71 //! range between 0 and 1 is standard, but the exact bounds (open vs closed) 72 //! and accuracy differ. In addition to the [`Standard`] distribution Rand offers 73 //! [`Open01`] and [`OpenClosed01`]. See "Floating point implementation" section of 74 //! [`Standard`] documentation for more details. 75 //! 76 //! # Non-uniform sampling 77 //! 78 //! Sampling a simple true/false outcome with a given probability has a name: 79 //! the [`Bernoulli`] distribution (this is used by [`Rng::gen_bool`]). 80 //! 81 //! For weighted sampling from a sequence of discrete values, use the 82 //! [`weighted`] module. 83 //! 84 //! This crate no longer includes other non-uniform distributions; instead 85 //! it is recommended that you use either [`rand_distr`] or [`statrs`]. 86 //! 87 //! 88 //! [probability distribution]: https://en.wikipedia.org/wiki/Probability_distribution 89 //! [`rand_distr`]: https://crates.io/crates/rand_distr 90 //! [`statrs`]: https://crates.io/crates/statrs 91 92 //! [`random`]: crate::random 93 //! [`rand_distr`]: https://crates.io/crates/rand_distr 94 //! [`statrs`]: https://crates.io/crates/statrs 95 96 use crate::Rng; 97 use core::iter; 98 99 pub use self::bernoulli::{Bernoulli, BernoulliError}; 100 pub use self::float::{Open01, OpenClosed01}; 101 pub use self::other::Alphanumeric; 102 #[doc(inline)] pub use self::uniform::Uniform; 103 #[cfg(feature = "alloc")] 104 pub use self::weighted::{WeightedError, WeightedIndex}; 105 106 // The following are all deprecated after being moved to rand_distr 107 #[allow(deprecated)] 108 #[cfg(feature = "std")] 109 pub use self::binomial::Binomial; 110 #[allow(deprecated)] 111 #[cfg(feature = "std")] 112 pub use self::cauchy::Cauchy; 113 #[allow(deprecated)] 114 #[cfg(feature = "std")] 115 pub use self::dirichlet::Dirichlet; 116 #[allow(deprecated)] 117 #[cfg(feature = "std")] 118 pub use self::exponential::{Exp, Exp1}; 119 #[allow(deprecated)] 120 #[cfg(feature = "std")] 121 pub use self::gamma::{Beta, ChiSquared, FisherF, Gamma, StudentT}; 122 #[allow(deprecated)] 123 #[cfg(feature = "std")] 124 pub use self::normal::{LogNormal, Normal, StandardNormal}; 125 #[allow(deprecated)] 126 #[cfg(feature = "std")] 127 pub use self::pareto::Pareto; 128 #[allow(deprecated)] 129 #[cfg(feature = "std")] 130 pub use self::poisson::Poisson; 131 #[allow(deprecated)] 132 #[cfg(feature = "std")] 133 pub use self::triangular::Triangular; 134 #[allow(deprecated)] 135 #[cfg(feature = "std")] 136 pub use self::unit_circle::UnitCircle; 137 #[allow(deprecated)] 138 #[cfg(feature = "std")] 139 pub use self::unit_sphere::UnitSphereSurface; 140 #[allow(deprecated)] 141 #[cfg(feature = "std")] 142 pub use self::weibull::Weibull; 143 144 mod bernoulli; 145 #[cfg(feature = "std")] mod binomial; 146 #[cfg(feature = "std")] mod cauchy; 147 #[cfg(feature = "std")] mod dirichlet; 148 #[cfg(feature = "std")] mod exponential; 149 #[cfg(feature = "std")] mod gamma; 150 #[cfg(feature = "std")] mod normal; 151 #[cfg(feature = "std")] mod pareto; 152 #[cfg(feature = "std")] mod poisson; 153 #[cfg(feature = "std")] mod triangular; 154 pub mod uniform; 155 #[cfg(feature = "std")] mod unit_circle; 156 #[cfg(feature = "std")] mod unit_sphere; 157 #[cfg(feature = "std")] mod weibull; 158 #[cfg(feature = "alloc")] pub mod weighted; 159 160 mod float; 161 #[doc(hidden)] 162 pub mod hidden_export { 163 pub use super::float::IntoFloat; // used by rand_distr 164 } 165 mod integer; 166 mod other; 167 mod utils; 168 #[cfg(feature = "std")] mod ziggurat_tables; 169 170 /// Types (distributions) that can be used to create a random instance of `T`. 171 /// 172 /// It is possible to sample from a distribution through both the 173 /// `Distribution` and [`Rng`] traits, via `distr.sample(&mut rng)` and 174 /// `rng.sample(distr)`. They also both offer the [`sample_iter`] method, which 175 /// produces an iterator that samples from the distribution. 176 /// 177 /// All implementations are expected to be immutable; this has the significant 178 /// advantage of not needing to consider thread safety, and for most 179 /// distributions efficient state-less sampling algorithms are available. 180 /// 181 /// Implementations are typically expected to be portable with reproducible 182 /// results when used with a PRNG with fixed seed; see the 183 /// [portability chapter](https://rust-random.github.io/book/portability.html) 184 /// of The Rust Rand Book. In some cases this does not apply, e.g. the `usize` 185 /// type requires different sampling on 32-bit and 64-bit machines. 186 /// 187 /// [`sample_iter`]: Distribution::method.sample_iter 188 pub trait Distribution<T> { 189 /// Generate a random value of `T`, using `rng` as the source of randomness. sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T190 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T; 191 192 /// Create an iterator that generates random values of `T`, using `rng` as 193 /// the source of randomness. 194 /// 195 /// Note that this function takes `self` by value. This works since 196 /// `Distribution<T>` is impl'd for `&D` where `D: Distribution<T>`, 197 /// however borrowing is not automatic hence `distr.sample_iter(...)` may 198 /// need to be replaced with `(&distr).sample_iter(...)` to borrow or 199 /// `(&*distr).sample_iter(...)` to reborrow an existing reference. 200 /// 201 /// # Example 202 /// 203 /// ``` 204 /// use rand::thread_rng; 205 /// use rand::distributions::{Distribution, Alphanumeric, Uniform, Standard}; 206 /// 207 /// let rng = thread_rng(); 208 /// 209 /// // Vec of 16 x f32: 210 /// let v: Vec<f32> = Standard.sample_iter(rng).take(16).collect(); 211 /// 212 /// // String: 213 /// let s: String = Alphanumeric.sample_iter(rng).take(7).collect(); 214 /// 215 /// // Dice-rolling: 216 /// let die_range = Uniform::new_inclusive(1, 6); 217 /// let mut roll_die = die_range.sample_iter(rng); 218 /// while roll_die.next().unwrap() != 6 { 219 /// println!("Not a 6; rolling again!"); 220 /// } 221 /// ``` sample_iter<R>(self, rng: R) -> DistIter<Self, R, T> where R: Rng, Self: Sized,222 fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T> 223 where 224 R: Rng, 225 Self: Sized, 226 { 227 DistIter { 228 distr: self, 229 rng, 230 phantom: ::core::marker::PhantomData, 231 } 232 } 233 } 234 235 impl<'a, T, D: Distribution<T>> Distribution<T> for &'a D { sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T236 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T { 237 (*self).sample(rng) 238 } 239 } 240 241 242 /// An iterator that generates random values of `T` with distribution `D`, 243 /// using `R` as the source of randomness. 244 /// 245 /// This `struct` is created by the [`sample_iter`] method on [`Distribution`]. 246 /// See its documentation for more. 247 /// 248 /// [`sample_iter`]: Distribution::sample_iter 249 #[derive(Debug)] 250 pub struct DistIter<D, R, T> { 251 distr: D, 252 rng: R, 253 phantom: ::core::marker::PhantomData<T>, 254 } 255 256 impl<D, R, T> Iterator for DistIter<D, R, T> 257 where 258 D: Distribution<T>, 259 R: Rng, 260 { 261 type Item = T; 262 263 #[inline(always)] next(&mut self) -> Option<T>264 fn next(&mut self) -> Option<T> { 265 // Here, self.rng may be a reference, but we must take &mut anyway. 266 // Even if sample could take an R: Rng by value, we would need to do this 267 // since Rng is not copyable and we cannot enforce that this is "reborrowable". 268 Some(self.distr.sample(&mut self.rng)) 269 } 270 size_hint(&self) -> (usize, Option<usize>)271 fn size_hint(&self) -> (usize, Option<usize>) { 272 (usize::max_value(), None) 273 } 274 } 275 276 impl<D, R, T> iter::FusedIterator for DistIter<D, R, T> 277 where 278 D: Distribution<T>, 279 R: Rng, 280 { 281 } 282 283 #[cfg(features = "nightly")] 284 impl<D, R, T> iter::TrustedLen for DistIter<D, R, T> 285 where 286 D: Distribution<T>, 287 R: Rng, 288 { 289 } 290 291 292 /// A generic random value distribution, implemented for many primitive types. 293 /// Usually generates values with a numerically uniform distribution, and with a 294 /// range appropriate to the type. 295 /// 296 /// ## Provided implementations 297 /// 298 /// Assuming the provided `Rng` is well-behaved, these implementations 299 /// generate values with the following ranges and distributions: 300 /// 301 /// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed 302 /// over all values of the type. 303 /// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all 304 /// code points in the range `0...0x10_FFFF`, except for the range 305 /// `0xD800...0xDFFF` (the surrogate code points). This includes 306 /// unassigned/reserved code points. 307 /// * `bool`: Generates `false` or `true`, each with probability 0.5. 308 /// * Floating point types (`f32` and `f64`): Uniformly distributed in the 309 /// half-open range `[0, 1)`. See notes below. 310 /// * Wrapping integers (`Wrapping<T>`), besides the type identical to their 311 /// normal integer variants. 312 /// 313 /// The `Standard` distribution also supports generation of the following 314 /// compound types where all component types are supported: 315 /// 316 /// * Tuples (up to 12 elements): each element is generated sequentially. 317 /// * Arrays (up to 32 elements): each element is generated sequentially; 318 /// see also [`Rng::fill`] which supports arbitrary array length for integer 319 /// types and tends to be faster for `u32` and smaller types. 320 /// * `Option<T>` first generates a `bool`, and if true generates and returns 321 /// `Some(value)` where `value: T`, otherwise returning `None`. 322 /// 323 /// ## Custom implementations 324 /// 325 /// The [`Standard`] distribution may be implemented for user types as follows: 326 /// 327 /// ``` 328 /// # #![allow(dead_code)] 329 /// use rand::Rng; 330 /// use rand::distributions::{Distribution, Standard}; 331 /// 332 /// struct MyF32 { 333 /// x: f32, 334 /// } 335 /// 336 /// impl Distribution<MyF32> for Standard { 337 /// fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> MyF32 { 338 /// MyF32 { x: rng.gen() } 339 /// } 340 /// } 341 /// ``` 342 /// 343 /// ## Example usage 344 /// ``` 345 /// use rand::prelude::*; 346 /// use rand::distributions::Standard; 347 /// 348 /// let val: f32 = StdRng::from_entropy().sample(Standard); 349 /// println!("f32 from [0, 1): {}", val); 350 /// ``` 351 /// 352 /// # Floating point implementation 353 /// The floating point implementations for `Standard` generate a random value in 354 /// the half-open interval `[0, 1)`, i.e. including 0 but not 1. 355 /// 356 /// All values that can be generated are of the form `n * ε/2`. For `f32` 357 /// the 24 most significant random bits of a `u32` are used and for `f64` the 358 /// 53 most significant bits of a `u64` are used. The conversion uses the 359 /// multiplicative method: `(rng.gen::<$uty>() >> N) as $ty * (ε/2)`. 360 /// 361 /// See also: [`Open01`] which samples from `(0, 1)`, [`OpenClosed01`] which 362 /// samples from `(0, 1]` and `Rng::gen_range(0, 1)` which also samples from 363 /// `[0, 1)`. Note that `Open01` and `gen_range` (which uses [`Uniform`]) use 364 /// transmute-based methods which yield 1 bit less precision but may perform 365 /// faster on some architectures (on modern Intel CPUs all methods have 366 /// approximately equal performance). 367 /// 368 /// [`Uniform`]: uniform::Uniform 369 #[derive(Clone, Copy, Debug)] 370 pub struct Standard; 371 372 373 #[cfg(all(test, feature = "std"))] 374 mod tests { 375 use super::{Distribution, Uniform}; 376 use crate::Rng; 377 378 #[test] test_distributions_iter()379 fn test_distributions_iter() { 380 use crate::distributions::Open01; 381 let mut rng = crate::test::rng(210); 382 let distr = Open01; 383 let results: Vec<f32> = distr.sample_iter(&mut rng).take(100).collect(); 384 println!("{:?}", results); 385 } 386 387 #[test] test_make_an_iter()388 fn test_make_an_iter() { 389 fn ten_dice_rolls_other_than_five<'a, R: Rng>( 390 rng: &'a mut R, 391 ) -> impl Iterator<Item = i32> + 'a { 392 Uniform::new_inclusive(1, 6) 393 .sample_iter(rng) 394 .filter(|x| *x != 5) 395 .take(10) 396 } 397 398 let mut rng = crate::test::rng(211); 399 let mut count = 0; 400 for val in ten_dice_rolls_other_than_five(&mut rng) { 401 assert!(val >= 1 && val <= 6 && val != 5); 402 count += 1; 403 } 404 assert_eq!(count, 10); 405 } 406 } 407