diff options
Diffstat (limited to 'vendor/rand-0.7.3/src/distributions')
22 files changed, 6402 insertions, 0 deletions
diff --git a/vendor/rand-0.7.3/src/distributions/bernoulli.rs b/vendor/rand-0.7.3/src/distributions/bernoulli.rs new file mode 100644 index 000000000..a1fa86e14 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/bernoulli.rs @@ -0,0 +1,199 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Bernoulli distribution. + +use crate::distributions::Distribution; +use crate::Rng; +use core::{fmt, u64}; + +/// The Bernoulli distribution. +/// +/// This is a special case of the Binomial distribution where `n = 1`. +/// +/// # Example +/// +/// ```rust +/// use rand::distributions::{Bernoulli, Distribution}; +/// +/// let d = Bernoulli::new(0.3).unwrap(); +/// let v = d.sample(&mut rand::thread_rng()); +/// println!("{} is from a Bernoulli distribution", v); +/// ``` +/// +/// # Precision +/// +/// This `Bernoulli` distribution uses 64 bits from the RNG (a `u64`), +/// so only probabilities that are multiples of 2<sup>-64</sup> can be +/// represented. +#[derive(Clone, Copy, Debug)] +pub struct Bernoulli { + /// Probability of success, relative to the maximal integer. + p_int: u64, +} + +// To sample from the Bernoulli distribution we use a method that compares a +// random `u64` value `v < (p * 2^64)`. +// +// If `p == 1.0`, the integer `v` to compare against can not represented as a +// `u64`. We manually set it to `u64::MAX` instead (2^64 - 1 instead of 2^64). +// Note that value of `p < 1.0` can never result in `u64::MAX`, because an +// `f64` only has 53 bits of precision, and the next largest value of `p` will +// result in `2^64 - 2048`. +// +// Also there is a 100% theoretical concern: if someone consistenly wants to +// generate `true` using the Bernoulli distribution (i.e. by using a probability +// of `1.0`), just using `u64::MAX` is not enough. On average it would return +// false once every 2^64 iterations. Some people apparently care about this +// case. +// +// That is why we special-case `u64::MAX` to always return `true`, without using +// the RNG, and pay the performance price for all uses that *are* reasonable. +// Luckily, if `new()` and `sample` are close, the compiler can optimize out the +// extra check. +const ALWAYS_TRUE: u64 = u64::MAX; + +// This is just `2.0.powi(64)`, but written this way because it is not available +// in `no_std` mode. +const SCALE: f64 = 2.0 * (1u64 << 63) as f64; + +/// Error type returned from `Bernoulli::new`. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub enum BernoulliError { + /// `p < 0` or `p > 1`. + InvalidProbability, +} + +impl fmt::Display for BernoulliError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str(match self { + BernoulliError::InvalidProbability => "p is outside [0, 1] in Bernoulli distribution", + }) + } +} + +#[cfg(feature = "std")] +impl ::std::error::Error for BernoulliError {} + +impl Bernoulli { + /// Construct a new `Bernoulli` with the given probability of success `p`. + /// + /// # Precision + /// + /// For `p = 1.0`, the resulting distribution will always generate true. + /// For `p = 0.0`, the resulting distribution will always generate false. + /// + /// This method is accurate for any input `p` in the range `[0, 1]` which is + /// a multiple of 2<sup>-64</sup>. (Note that not all multiples of + /// 2<sup>-64</sup> in `[0, 1]` can be represented as a `f64`.) + #[inline] + pub fn new(p: f64) -> Result<Bernoulli, BernoulliError> { + if !(p >= 0.0 && p < 1.0) { + if p == 1.0 { + return Ok(Bernoulli { p_int: ALWAYS_TRUE }); + } + return Err(BernoulliError::InvalidProbability); + } + Ok(Bernoulli { + p_int: (p * SCALE) as u64, + }) + } + + /// Construct a new `Bernoulli` with the probability of success of + /// `numerator`-in-`denominator`. I.e. `new_ratio(2, 3)` will return + /// a `Bernoulli` with a 2-in-3 chance, or about 67%, of returning `true`. + /// + /// return `true`. If `numerator == 0` it will always return `false`. + /// For `numerator > denominator` and `denominator == 0`, this returns an + /// error. Otherwise, for `numerator == denominator`, samples are always + /// true; for `numerator == 0` samples are always false. + #[inline] + pub fn from_ratio(numerator: u32, denominator: u32) -> Result<Bernoulli, BernoulliError> { + if numerator > denominator || denominator == 0 { + return Err(BernoulliError::InvalidProbability); + } + if numerator == denominator { + return Ok(Bernoulli { p_int: ALWAYS_TRUE }); + } + let p_int = ((f64::from(numerator) / f64::from(denominator)) * SCALE) as u64; + Ok(Bernoulli { p_int }) + } +} + +impl Distribution<bool> for Bernoulli { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool { + // Make sure to always return true for p = 1.0. + if self.p_int == ALWAYS_TRUE { + return true; + } + let v: u64 = rng.gen(); + v < self.p_int + } +} + +#[cfg(test)] +mod test { + use super::Bernoulli; + use crate::distributions::Distribution; + use crate::Rng; + + #[test] + fn test_trivial() { + let mut r = crate::test::rng(1); + let always_false = Bernoulli::new(0.0).unwrap(); + let always_true = Bernoulli::new(1.0).unwrap(); + for _ in 0..5 { + assert_eq!(r.sample::<bool, _>(&always_false), false); + assert_eq!(r.sample::<bool, _>(&always_true), true); + assert_eq!(Distribution::<bool>::sample(&always_false, &mut r), false); + assert_eq!(Distribution::<bool>::sample(&always_true, &mut r), true); + } + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_average() { + const P: f64 = 0.3; + const NUM: u32 = 3; + const DENOM: u32 = 10; + let d1 = Bernoulli::new(P).unwrap(); + let d2 = Bernoulli::from_ratio(NUM, DENOM).unwrap(); + const N: u32 = 100_000; + + let mut sum1: u32 = 0; + let mut sum2: u32 = 0; + let mut rng = crate::test::rng(2); + for _ in 0..N { + if d1.sample(&mut rng) { + sum1 += 1; + } + if d2.sample(&mut rng) { + sum2 += 1; + } + } + let avg1 = (sum1 as f64) / (N as f64); + assert!((avg1 - P).abs() < 5e-3); + + let avg2 = (sum2 as f64) / (N as f64); + assert!((avg2 - (NUM as f64) / (DENOM as f64)).abs() < 5e-3); + } + + #[test] + fn value_stability() { + let mut rng = crate::test::rng(3); + let distr = Bernoulli::new(0.4532).unwrap(); + let mut buf = [false; 10]; + for x in &mut buf { + *x = rng.sample(&distr); + } + assert_eq!(buf, [ + true, false, false, true, false, false, true, true, true, true + ]); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/binomial.rs b/vendor/rand-0.7.3/src/distributions/binomial.rs new file mode 100644 index 000000000..c096e4a86 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/binomial.rs @@ -0,0 +1,321 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2016-2017 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The binomial distribution. +#![allow(deprecated)] +#![allow(clippy::all)] + +use crate::distributions::{Distribution, Uniform}; +use crate::Rng; + +/// The binomial distribution `Binomial(n, p)`. +/// +/// This distribution has density function: +/// `f(k) = n!/(k! (n-k)!) p^k (1-p)^(n-k)` for `k >= 0`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Binomial { + /// Number of trials. + n: u64, + /// Probability of success. + p: f64, +} + +impl Binomial { + /// Construct a new `Binomial` with the given shape parameters `n` (number + /// of trials) and `p` (probability of success). + /// + /// Panics if `p < 0` or `p > 1`. + pub fn new(n: u64, p: f64) -> Binomial { + assert!(p >= 0.0, "Binomial::new called with p < 0"); + assert!(p <= 1.0, "Binomial::new called with p > 1"); + Binomial { n, p } + } +} + +/// Convert a `f64` to an `i64`, panicing on overflow. +// In the future (Rust 1.34), this might be replaced with `TryFrom`. +fn f64_to_i64(x: f64) -> i64 { + assert!(x < (::std::i64::MAX as f64)); + x as i64 +} + +impl Distribution<u64> for Binomial { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u64 { + // Handle these values directly. + if self.p == 0.0 { + return 0; + } else if self.p == 1.0 { + return self.n; + } + + // The binomial distribution is symmetrical with respect to p -> 1-p, + // k -> n-k switch p so that it is less than 0.5 - this allows for lower + // expected values we will just invert the result at the end + let p = if self.p <= 0.5 { self.p } else { 1.0 - self.p }; + + let result; + let q = 1. - p; + + // For small n * min(p, 1 - p), the BINV algorithm based on the inverse + // transformation of the binomial distribution is efficient. Otherwise, + // the BTPE algorithm is used. + // + // Voratas Kachitvichyanukul and Bruce W. Schmeiser. 1988. Binomial + // random variate generation. Commun. ACM 31, 2 (February 1988), + // 216-222. http://dx.doi.org/10.1145/42372.42381 + + // Threshold for prefering the BINV algorithm. The paper suggests 10, + // Ranlib uses 30, and GSL uses 14. + const BINV_THRESHOLD: f64 = 10.; + + if (self.n as f64) * p < BINV_THRESHOLD && self.n <= (::std::i32::MAX as u64) { + // Use the BINV algorithm. + let s = p / q; + let a = ((self.n + 1) as f64) * s; + let mut r = q.powi(self.n as i32); + let mut u: f64 = rng.gen(); + let mut x = 0; + while u > r as f64 { + u -= r; + x += 1; + r *= a / (x as f64) - s; + } + result = x; + } else { + // Use the BTPE algorithm. + + // Threshold for using the squeeze algorithm. This can be freely + // chosen based on performance. Ranlib and GSL use 20. + const SQUEEZE_THRESHOLD: i64 = 20; + + // Step 0: Calculate constants as functions of `n` and `p`. + let n = self.n as f64; + let np = n * p; + let npq = np * q; + let f_m = np + p; + let m = f64_to_i64(f_m); + // radius of triangle region, since height=1 also area of region + let p1 = (2.195 * npq.sqrt() - 4.6 * q).floor() + 0.5; + // tip of triangle + let x_m = (m as f64) + 0.5; + // left edge of triangle + let x_l = x_m - p1; + // right edge of triangle + let x_r = x_m + p1; + let c = 0.134 + 20.5 / (15.3 + (m as f64)); + // p1 + area of parallelogram region + let p2 = p1 * (1. + 2. * c); + + fn lambda(a: f64) -> f64 { + a * (1. + 0.5 * a) + } + + let lambda_l = lambda((f_m - x_l) / (f_m - x_l * p)); + let lambda_r = lambda((x_r - f_m) / (x_r * q)); + // p1 + area of left tail + let p3 = p2 + c / lambda_l; + // p1 + area of right tail + let p4 = p3 + c / lambda_r; + + // return value + let mut y: i64; + + let gen_u = Uniform::new(0., p4); + let gen_v = Uniform::new(0., 1.); + + loop { + // Step 1: Generate `u` for selecting the region. If region 1 is + // selected, generate a triangularly distributed variate. + let u = gen_u.sample(rng); + let mut v = gen_v.sample(rng); + if !(u > p1) { + y = f64_to_i64(x_m - p1 * v + u); + break; + } + + if !(u > p2) { + // Step 2: Region 2, parallelograms. Check if region 2 is + // used. If so, generate `y`. + let x = x_l + (u - p1) / c; + v = v * c + 1.0 - (x - x_m).abs() / p1; + if v > 1. { + continue; + } else { + y = f64_to_i64(x); + } + } else if !(u > p3) { + // Step 3: Region 3, left exponential tail. + y = f64_to_i64(x_l + v.ln() / lambda_l); + if y < 0 { + continue; + } else { + v *= (u - p2) * lambda_l; + } + } else { + // Step 4: Region 4, right exponential tail. + y = f64_to_i64(x_r - v.ln() / lambda_r); + if y > 0 && (y as u64) > self.n { + continue; + } else { + v *= (u - p3) * lambda_r; + } + } + + // Step 5: Acceptance/rejection comparison. + + // Step 5.0: Test for appropriate method of evaluating f(y). + let k = (y - m).abs(); + if !(k > SQUEEZE_THRESHOLD && (k as f64) < 0.5 * npq - 1.) { + // Step 5.1: Evaluate f(y) via the recursive relationship. Start the + // search from the mode. + let s = p / q; + let a = s * (n + 1.); + let mut f = 1.0; + if m < y { + let mut i = m; + loop { + i += 1; + f *= a / (i as f64) - s; + if i == y { + break; + } + } + } else if m > y { + let mut i = y; + loop { + i += 1; + f /= a / (i as f64) - s; + if i == m { + break; + } + } + } + if v > f { + continue; + } else { + break; + } + } + + // Step 5.2: Squeezing. Check the value of ln(v) againts upper and + // lower bound of ln(f(y)). + let k = k as f64; + let rho = (k / npq) * ((k * (k / 3. + 0.625) + 1. / 6.) / npq + 0.5); + let t = -0.5 * k * k / npq; + let alpha = v.ln(); + if alpha < t - rho { + break; + } + if alpha > t + rho { + continue; + } + + // Step 5.3: Final acceptance/rejection test. + let x1 = (y + 1) as f64; + let f1 = (m + 1) as f64; + let z = (f64_to_i64(n) + 1 - m) as f64; + let w = (f64_to_i64(n) - y + 1) as f64; + + fn stirling(a: f64) -> f64 { + let a2 = a * a; + (13860. - (462. - (132. - (99. - 140. / a2) / a2) / a2) / a2) / a / 166320. + } + + if alpha + > x_m * (f1 / x1).ln() + + (n - (m as f64) + 0.5) * (z / w).ln() + + ((y - m) as f64) * (w * p / (x1 * q)).ln() + // We use the signs from the GSL implementation, which are + // different than the ones in the reference. According to + // the GSL authors, the new signs were verified to be + // correct by one of the original designers of the + // algorithm. + + stirling(f1) + + stirling(z) + - stirling(x1) + - stirling(w) + { + continue; + } + + break; + } + assert!(y >= 0); + result = y as u64; + } + + // Invert the result for p < 0.5. + if p != self.p { + self.n - result + } else { + result + } + } +} + +#[cfg(test)] +mod test { + use super::Binomial; + use crate::distributions::Distribution; + use crate::Rng; + + fn test_binomial_mean_and_variance<R: Rng>(n: u64, p: f64, rng: &mut R) { + let binomial = Binomial::new(n, p); + + let expected_mean = n as f64 * p; + let expected_variance = n as f64 * p * (1.0 - p); + + let mut results = [0.0; 1000]; + for i in results.iter_mut() { + *i = binomial.sample(rng) as f64; + } + + let mean = results.iter().sum::<f64>() / results.len() as f64; + assert!( + (mean as f64 - expected_mean).abs() < expected_mean / 50.0, + "mean: {}, expected_mean: {}", + mean, + expected_mean + ); + + let variance = + results.iter().map(|x| (x - mean) * (x - mean)).sum::<f64>() / results.len() as f64; + assert!( + (variance - expected_variance).abs() < expected_variance / 10.0, + "variance: {}, expected_variance: {}", + variance, + expected_variance + ); + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_binomial() { + let mut rng = crate::test::rng(351); + test_binomial_mean_and_variance(150, 0.1, &mut rng); + test_binomial_mean_and_variance(70, 0.6, &mut rng); + test_binomial_mean_and_variance(40, 0.5, &mut rng); + test_binomial_mean_and_variance(20, 0.7, &mut rng); + test_binomial_mean_and_variance(20, 0.5, &mut rng); + } + + #[test] + fn test_binomial_end_points() { + let mut rng = crate::test::rng(352); + assert_eq!(rng.sample(Binomial::new(20, 0.0)), 0); + assert_eq!(rng.sample(Binomial::new(20, 1.0)), 20); + } + + #[test] + #[should_panic] + fn test_binomial_invalid_lambda_neg() { + Binomial::new(20, -10.0); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/cauchy.rs b/vendor/rand-0.7.3/src/distributions/cauchy.rs new file mode 100644 index 000000000..dc54c98a3 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/cauchy.rs @@ -0,0 +1,99 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2016-2017 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Cauchy distribution. +#![allow(deprecated)] +#![allow(clippy::all)] + +use crate::distributions::Distribution; +use crate::Rng; +use std::f64::consts::PI; + +/// The Cauchy distribution `Cauchy(median, scale)`. +/// +/// This distribution has a density function: +/// `f(x) = 1 / (pi * scale * (1 + ((x - median) / scale)^2))` +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Cauchy { + median: f64, + scale: f64, +} + +impl Cauchy { + /// Construct a new `Cauchy` with the given shape parameters + /// `median` the peak location and `scale` the scale factor. + /// Panics if `scale <= 0`. + pub fn new(median: f64, scale: f64) -> Cauchy { + assert!(scale > 0.0, "Cauchy::new called with scale factor <= 0"); + Cauchy { median, scale } + } +} + +impl Distribution<f64> for Cauchy { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + // sample from [0, 1) + let x = rng.gen::<f64>(); + // get standard cauchy random number + // note that π/2 is not exactly representable, even if x=0.5 the result is finite + let comp_dev = (PI * x).tan(); + // shift and scale according to parameters + let result = self.median + self.scale * comp_dev; + result + } +} + +#[cfg(test)] +mod test { + use super::Cauchy; + use crate::distributions::Distribution; + + fn median(mut numbers: &mut [f64]) -> f64 { + sort(&mut numbers); + let mid = numbers.len() / 2; + numbers[mid] + } + + fn sort(numbers: &mut [f64]) { + numbers.sort_by(|a, b| a.partial_cmp(b).unwrap()); + } + + #[test] + fn test_cauchy_averages() { + // NOTE: given that the variance and mean are undefined, + // this test does not have any rigorous statistical meaning. + let cauchy = Cauchy::new(10.0, 5.0); + let mut rng = crate::test::rng(123); + let mut numbers: [f64; 1000] = [0.0; 1000]; + let mut sum = 0.0; + for i in 0..1000 { + numbers[i] = cauchy.sample(&mut rng); + sum += numbers[i]; + } + let median = median(&mut numbers); + println!("Cauchy median: {}", median); + assert!((median - 10.0).abs() < 0.4); // not 100% certain, but probable enough + let mean = sum / 1000.0; + println!("Cauchy mean: {}", mean); + // for a Cauchy distribution the mean should not converge + assert!((mean - 10.0).abs() > 0.4); // not 100% certain, but probable enough + } + + #[test] + #[should_panic] + fn test_cauchy_invalid_scale_zero() { + Cauchy::new(0.0, 0.0); + } + + #[test] + #[should_panic] + fn test_cauchy_invalid_scale_neg() { + Cauchy::new(0.0, -10.0); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/dirichlet.rs b/vendor/rand-0.7.3/src/distributions/dirichlet.rs new file mode 100644 index 000000000..a75678a85 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/dirichlet.rs @@ -0,0 +1,126 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The dirichlet distribution. +#![allow(deprecated)] +#![allow(clippy::all)] + +use crate::distributions::gamma::Gamma; +use crate::distributions::Distribution; +use crate::Rng; + +/// The dirichelet distribution `Dirichlet(alpha)`. +/// +/// The Dirichlet distribution is a family of continuous multivariate +/// probability distributions parameterized by a vector alpha of positive reals. +/// It is a multivariate generalization of the beta distribution. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Debug)] +pub struct Dirichlet { + /// Concentration parameters (alpha) + alpha: Vec<f64>, +} + +impl Dirichlet { + /// Construct a new `Dirichlet` with the given alpha parameter `alpha`. + /// + /// # Panics + /// - if `alpha.len() < 2` + #[inline] + pub fn new<V: Into<Vec<f64>>>(alpha: V) -> Dirichlet { + let a = alpha.into(); + assert!(a.len() > 1); + for i in 0..a.len() { + assert!(a[i] > 0.0); + } + + Dirichlet { alpha: a } + } + + /// Construct a new `Dirichlet` with the given shape parameter `alpha` and `size`. + /// + /// # Panics + /// - if `alpha <= 0.0` + /// - if `size < 2` + #[inline] + pub fn new_with_param(alpha: f64, size: usize) -> Dirichlet { + assert!(alpha > 0.0); + assert!(size > 1); + Dirichlet { + alpha: vec![alpha; size], + } + } +} + +impl Distribution<Vec<f64>> for Dirichlet { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Vec<f64> { + let n = self.alpha.len(); + let mut samples = vec![0.0f64; n]; + let mut sum = 0.0f64; + + for i in 0..n { + let g = Gamma::new(self.alpha[i], 1.0); + samples[i] = g.sample(rng); + sum += samples[i]; + } + let invacc = 1.0 / sum; + for i in 0..n { + samples[i] *= invacc; + } + samples + } +} + +#[cfg(test)] +mod test { + use super::Dirichlet; + use crate::distributions::Distribution; + + #[test] + fn test_dirichlet() { + let d = Dirichlet::new(vec![1.0, 2.0, 3.0]); + let mut rng = crate::test::rng(221); + let samples = d.sample(&mut rng); + let _: Vec<f64> = samples + .into_iter() + .map(|x| { + assert!(x > 0.0); + x + }) + .collect(); + } + + #[test] + fn test_dirichlet_with_param() { + let alpha = 0.5f64; + let size = 2; + let d = Dirichlet::new_with_param(alpha, size); + let mut rng = crate::test::rng(221); + let samples = d.sample(&mut rng); + let _: Vec<f64> = samples + .into_iter() + .map(|x| { + assert!(x > 0.0); + x + }) + .collect(); + } + + #[test] + #[should_panic] + fn test_dirichlet_invalid_length() { + Dirichlet::new_with_param(0.5f64, 1); + } + + #[test] + #[should_panic] + fn test_dirichlet_invalid_alpha() { + Dirichlet::new_with_param(0.0f64, 2); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/exponential.rs b/vendor/rand-0.7.3/src/distributions/exponential.rs new file mode 100644 index 000000000..5fdf7aa74 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/exponential.rs @@ -0,0 +1,114 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The exponential distribution. +#![allow(deprecated)] + +use crate::distributions::utils::ziggurat; +use crate::distributions::{ziggurat_tables, Distribution}; +use crate::Rng; + +/// Samples floating-point numbers according to the exponential distribution, +/// with rate parameter `λ = 1`. This is equivalent to `Exp::new(1.0)` or +/// sampling with `-rng.gen::<f64>().ln()`, but faster. +/// +/// See `Exp` for the general exponential distribution. +/// +/// Implemented via the ZIGNOR variant[^1] of the Ziggurat method. The exact +/// description in the paper was adjusted to use tables for the exponential +/// distribution rather than normal. +/// +/// [^1]: Jurgen A. Doornik (2005). [*An Improved Ziggurat Method to +/// Generate Normal Random Samples*]( +/// https://www.doornik.com/research/ziggurat.pdf). +/// Nuffield College, Oxford +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Exp1; + +// This could be done via `-rng.gen::<f64>().ln()` but that is slower. +impl Distribution<f64> for Exp1 { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + #[inline] + fn pdf(x: f64) -> f64 { + (-x).exp() + } + #[inline] + fn zero_case<R: Rng + ?Sized>(rng: &mut R, _u: f64) -> f64 { + ziggurat_tables::ZIG_EXP_R - rng.gen::<f64>().ln() + } + + ziggurat( + rng, + false, + &ziggurat_tables::ZIG_EXP_X, + &ziggurat_tables::ZIG_EXP_F, + pdf, + zero_case, + ) + } +} + +/// The exponential distribution `Exp(lambda)`. +/// +/// This distribution has density function: `f(x) = lambda * exp(-lambda * x)` +/// for `x > 0`. +/// +/// Note that [`Exp1`](crate::distributions::Exp1) is an optimised implementation for `lambda = 1`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Exp { + /// `lambda` stored as `1/lambda`, since this is what we scale by. + lambda_inverse: f64, +} + +impl Exp { + /// Construct a new `Exp` with the given shape parameter + /// `lambda`. Panics if `lambda <= 0`. + #[inline] + pub fn new(lambda: f64) -> Exp { + assert!(lambda > 0.0, "Exp::new called with `lambda` <= 0"); + Exp { + lambda_inverse: 1.0 / lambda, + } + } +} + +impl Distribution<f64> for Exp { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let n: f64 = rng.sample(Exp1); + n * self.lambda_inverse + } +} + +#[cfg(test)] +mod test { + use super::Exp; + use crate::distributions::Distribution; + + #[test] + fn test_exp() { + let exp = Exp::new(10.0); + let mut rng = crate::test::rng(221); + for _ in 0..1000 { + assert!(exp.sample(&mut rng) >= 0.0); + } + } + #[test] + #[should_panic] + fn test_exp_invalid_lambda_zero() { + Exp::new(0.0); + } + #[test] + #[should_panic] + fn test_exp_invalid_lambda_neg() { + Exp::new(-10.0); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/float.rs b/vendor/rand-0.7.3/src/distributions/float.rs new file mode 100644 index 000000000..0a45f3977 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/float.rs @@ -0,0 +1,307 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Basic floating-point number distributions + +use crate::distributions::utils::FloatSIMDUtils; +use crate::distributions::{Distribution, Standard}; +use crate::Rng; +use core::mem; +#[cfg(feature = "simd_support")] use packed_simd::*; + +/// A distribution to sample floating point numbers uniformly in the half-open +/// interval `(0, 1]`, i.e. including 1 but not 0. +/// +/// All values that can be generated are of the form `n * ε/2`. For `f32` +/// the 24 most significant random bits of a `u32` are used and for `f64` the +/// 53 most significant bits of a `u64` are used. The conversion uses the +/// multiplicative method. +/// +/// See also: [`Standard`] which samples from `[0, 1)`, [`Open01`] +/// which samples from `(0, 1)` and [`Uniform`] which samples from arbitrary +/// ranges. +/// +/// # Example +/// ``` +/// use rand::{thread_rng, Rng}; +/// use rand::distributions::OpenClosed01; +/// +/// let val: f32 = thread_rng().sample(OpenClosed01); +/// println!("f32 from (0, 1): {}", val); +/// ``` +/// +/// [`Standard`]: crate::distributions::Standard +/// [`Open01`]: crate::distributions::Open01 +/// [`Uniform`]: crate::distributions::uniform::Uniform +#[derive(Clone, Copy, Debug)] +pub struct OpenClosed01; + +/// A distribution to sample floating point numbers uniformly in the open +/// interval `(0, 1)`, i.e. not including either endpoint. +/// +/// All values that can be generated are of the form `n * ε + ε/2`. For `f32` +/// the 23 most significant random bits of an `u32` are used, for `f64` 52 from +/// an `u64`. The conversion uses a transmute-based method. +/// +/// See also: [`Standard`] which samples from `[0, 1)`, [`OpenClosed01`] +/// which samples from `(0, 1]` and [`Uniform`] which samples from arbitrary +/// ranges. +/// +/// # Example +/// ``` +/// use rand::{thread_rng, Rng}; +/// use rand::distributions::Open01; +/// +/// let val: f32 = thread_rng().sample(Open01); +/// println!("f32 from (0, 1): {}", val); +/// ``` +/// +/// [`Standard`]: crate::distributions::Standard +/// [`OpenClosed01`]: crate::distributions::OpenClosed01 +/// [`Uniform`]: crate::distributions::uniform::Uniform +#[derive(Clone, Copy, Debug)] +pub struct Open01; + + +// This trait is needed by both this lib and rand_distr hence is a hidden export +#[doc(hidden)] +pub trait IntoFloat { + type F; + + /// Helper method to combine the fraction and a contant exponent into a + /// float. + /// + /// Only the least significant bits of `self` may be set, 23 for `f32` and + /// 52 for `f64`. + /// The resulting value will fall in a range that depends on the exponent. + /// As an example the range with exponent 0 will be + /// [2<sup>0</sup>..2<sup>1</sup>), which is [1..2). + fn into_float_with_exponent(self, exponent: i32) -> Self::F; +} + +macro_rules! float_impls { + ($ty:ident, $uty:ident, $f_scalar:ident, $u_scalar:ty, + $fraction_bits:expr, $exponent_bias:expr) => { + impl IntoFloat for $uty { + type F = $ty; + #[inline(always)] + fn into_float_with_exponent(self, exponent: i32) -> $ty { + // The exponent is encoded using an offset-binary representation + let exponent_bits: $u_scalar = + (($exponent_bias + exponent) as $u_scalar) << $fraction_bits; + $ty::from_bits(self | exponent_bits) + } + } + + impl Distribution<$ty> for Standard { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + // Multiply-based method; 24/53 random bits; [0, 1) interval. + // We use the most significant bits because for simple RNGs + // those are usually more random. + let float_size = mem::size_of::<$f_scalar>() as u32 * 8; + let precision = $fraction_bits + 1; + let scale = 1.0 / ((1 as $u_scalar << precision) as $f_scalar); + + let value: $uty = rng.gen(); + let value = value >> (float_size - precision); + scale * $ty::cast_from_int(value) + } + } + + impl Distribution<$ty> for OpenClosed01 { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + // Multiply-based method; 24/53 random bits; (0, 1] interval. + // We use the most significant bits because for simple RNGs + // those are usually more random. + let float_size = mem::size_of::<$f_scalar>() as u32 * 8; + let precision = $fraction_bits + 1; + let scale = 1.0 / ((1 as $u_scalar << precision) as $f_scalar); + + let value: $uty = rng.gen(); + let value = value >> (float_size - precision); + // Add 1 to shift up; will not overflow because of right-shift: + scale * $ty::cast_from_int(value + 1) + } + } + + impl Distribution<$ty> for Open01 { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + // Transmute-based method; 23/52 random bits; (0, 1) interval. + // We use the most significant bits because for simple RNGs + // those are usually more random. + use core::$f_scalar::EPSILON; + let float_size = mem::size_of::<$f_scalar>() as u32 * 8; + + let value: $uty = rng.gen(); + let fraction = value >> (float_size - $fraction_bits); + fraction.into_float_with_exponent(0) - (1.0 - EPSILON / 2.0) + } + } + } +} + +float_impls! { f32, u32, f32, u32, 23, 127 } +float_impls! { f64, u64, f64, u64, 52, 1023 } + +#[cfg(feature = "simd_support")] +float_impls! { f32x2, u32x2, f32, u32, 23, 127 } +#[cfg(feature = "simd_support")] +float_impls! { f32x4, u32x4, f32, u32, 23, 127 } +#[cfg(feature = "simd_support")] +float_impls! { f32x8, u32x8, f32, u32, 23, 127 } +#[cfg(feature = "simd_support")] +float_impls! { f32x16, u32x16, f32, u32, 23, 127 } + +#[cfg(feature = "simd_support")] +float_impls! { f64x2, u64x2, f64, u64, 52, 1023 } +#[cfg(feature = "simd_support")] +float_impls! { f64x4, u64x4, f64, u64, 52, 1023 } +#[cfg(feature = "simd_support")] +float_impls! { f64x8, u64x8, f64, u64, 52, 1023 } + + +#[cfg(test)] +mod tests { + use super::*; + use crate::rngs::mock::StepRng; + + const EPSILON32: f32 = ::core::f32::EPSILON; + const EPSILON64: f64 = ::core::f64::EPSILON; + + macro_rules! test_f32 { + ($fnn:ident, $ty:ident, $ZERO:expr, $EPSILON:expr) => { + #[test] + fn $fnn() { + // Standard + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.gen::<$ty>(), $ZERO); + let mut one = StepRng::new(1 << 8 | 1 << (8 + 32), 0); + assert_eq!(one.gen::<$ty>(), $EPSILON / 2.0); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.gen::<$ty>(), 1.0 - $EPSILON / 2.0); + + // OpenClosed01 + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.sample::<$ty, _>(OpenClosed01), 0.0 + $EPSILON / 2.0); + let mut one = StepRng::new(1 << 8 | 1 << (8 + 32), 0); + assert_eq!(one.sample::<$ty, _>(OpenClosed01), $EPSILON); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.sample::<$ty, _>(OpenClosed01), $ZERO + 1.0); + + // Open01 + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.sample::<$ty, _>(Open01), 0.0 + $EPSILON / 2.0); + let mut one = StepRng::new(1 << 9 | 1 << (9 + 32), 0); + assert_eq!(one.sample::<$ty, _>(Open01), $EPSILON / 2.0 * 3.0); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.sample::<$ty, _>(Open01), 1.0 - $EPSILON / 2.0); + } + }; + } + test_f32! { f32_edge_cases, f32, 0.0, EPSILON32 } + #[cfg(feature = "simd_support")] + test_f32! { f32x2_edge_cases, f32x2, f32x2::splat(0.0), f32x2::splat(EPSILON32) } + #[cfg(feature = "simd_support")] + test_f32! { f32x4_edge_cases, f32x4, f32x4::splat(0.0), f32x4::splat(EPSILON32) } + #[cfg(feature = "simd_support")] + test_f32! { f32x8_edge_cases, f32x8, f32x8::splat(0.0), f32x8::splat(EPSILON32) } + #[cfg(feature = "simd_support")] + test_f32! { f32x16_edge_cases, f32x16, f32x16::splat(0.0), f32x16::splat(EPSILON32) } + + macro_rules! test_f64 { + ($fnn:ident, $ty:ident, $ZERO:expr, $EPSILON:expr) => { + #[test] + fn $fnn() { + // Standard + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.gen::<$ty>(), $ZERO); + let mut one = StepRng::new(1 << 11, 0); + assert_eq!(one.gen::<$ty>(), $EPSILON / 2.0); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.gen::<$ty>(), 1.0 - $EPSILON / 2.0); + + // OpenClosed01 + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.sample::<$ty, _>(OpenClosed01), 0.0 + $EPSILON / 2.0); + let mut one = StepRng::new(1 << 11, 0); + assert_eq!(one.sample::<$ty, _>(OpenClosed01), $EPSILON); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.sample::<$ty, _>(OpenClosed01), $ZERO + 1.0); + + // Open01 + let mut zeros = StepRng::new(0, 0); + assert_eq!(zeros.sample::<$ty, _>(Open01), 0.0 + $EPSILON / 2.0); + let mut one = StepRng::new(1 << 12, 0); + assert_eq!(one.sample::<$ty, _>(Open01), $EPSILON / 2.0 * 3.0); + let mut max = StepRng::new(!0, 0); + assert_eq!(max.sample::<$ty, _>(Open01), 1.0 - $EPSILON / 2.0); + } + }; + } + test_f64! { f64_edge_cases, f64, 0.0, EPSILON64 } + #[cfg(feature = "simd_support")] + test_f64! { f64x2_edge_cases, f64x2, f64x2::splat(0.0), f64x2::splat(EPSILON64) } + #[cfg(feature = "simd_support")] + test_f64! { f64x4_edge_cases, f64x4, f64x4::splat(0.0), f64x4::splat(EPSILON64) } + #[cfg(feature = "simd_support")] + test_f64! { f64x8_edge_cases, f64x8, f64x8::splat(0.0), f64x8::splat(EPSILON64) } + + #[test] + fn value_stability() { + fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>( + distr: &D, zero: T, expected: &[T], + ) { + let mut rng = crate::test::rng(0x6f44f5646c2a7334); + let mut buf = [zero; 3]; + for x in &mut buf { + *x = rng.sample(&distr); + } + assert_eq!(&buf, expected); + } + + test_samples(&Standard, 0f32, &[0.0035963655, 0.7346052, 0.09778172]); + test_samples(&Standard, 0f64, &[ + 0.7346051961657583, + 0.20298547462974248, + 0.8166436635290655, + ]); + + test_samples(&OpenClosed01, 0f32, &[0.003596425, 0.73460525, 0.09778178]); + test_samples(&OpenClosed01, 0f64, &[ + 0.7346051961657584, + 0.2029854746297426, + 0.8166436635290656, + ]); + + test_samples(&Open01, 0f32, &[0.0035963655, 0.73460525, 0.09778172]); + test_samples(&Open01, 0f64, &[ + 0.7346051961657584, + 0.20298547462974248, + 0.8166436635290656, + ]); + + #[cfg(feature = "simd_support")] + { + // We only test a sub-set of types here. Values are identical to + // non-SIMD types; we assume this pattern continues across all + // SIMD types. + + test_samples(&Standard, f32x2::new(0.0, 0.0), &[ + f32x2::new(0.0035963655, 0.7346052), + f32x2::new(0.09778172, 0.20298547), + f32x2::new(0.34296435, 0.81664366), + ]); + + test_samples(&Standard, f64x2::new(0.0, 0.0), &[ + f64x2::new(0.7346051961657583, 0.20298547462974248), + f64x2::new(0.8166436635290655, 0.7423708925400552), + f64x2::new(0.16387782224016323, 0.9087068770169618), + ]); + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/gamma.rs b/vendor/rand-0.7.3/src/distributions/gamma.rs new file mode 100644 index 000000000..f19738dbe --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/gamma.rs @@ -0,0 +1,373 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Gamma and derived distributions. +#![allow(deprecated)] + +use self::ChiSquaredRepr::*; +use self::GammaRepr::*; + +use crate::distributions::normal::StandardNormal; +use crate::distributions::{Distribution, Exp, Open01}; +use crate::Rng; + +/// The Gamma distribution `Gamma(shape, scale)` distribution. +/// +/// The density function of this distribution is +/// +/// ```text +/// f(x) = x^(k - 1) * exp(-x / θ) / (Γ(k) * θ^k) +/// ``` +/// +/// where `Γ` is the Gamma function, `k` is the shape and `θ` is the +/// scale and both `k` and `θ` are strictly positive. +/// +/// The algorithm used is that described by Marsaglia & Tsang 2000[^1], +/// falling back to directly sampling from an Exponential for `shape +/// == 1`, and using the boosting technique described in that paper for +/// `shape < 1`. +/// +/// [^1]: George Marsaglia and Wai Wan Tsang. 2000. "A Simple Method for +/// Generating Gamma Variables" *ACM Trans. Math. Softw.* 26, 3 +/// (September 2000), 363-372. +/// DOI:[10.1145/358407.358414](https://doi.acm.org/10.1145/358407.358414) +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Gamma { + repr: GammaRepr, +} + +#[derive(Clone, Copy, Debug)] +enum GammaRepr { + Large(GammaLargeShape), + One(Exp), + Small(GammaSmallShape), +} + +// These two helpers could be made public, but saving the +// match-on-Gamma-enum branch from using them directly (e.g. if one +// knows that the shape is always > 1) doesn't appear to be much +// faster. + +/// Gamma distribution where the shape parameter is less than 1. +/// +/// Note, samples from this require a compulsory floating-point `pow` +/// call, which makes it significantly slower than sampling from a +/// gamma distribution where the shape parameter is greater than or +/// equal to 1. +/// +/// See `Gamma` for sampling from a Gamma distribution with general +/// shape parameters. +#[derive(Clone, Copy, Debug)] +struct GammaSmallShape { + inv_shape: f64, + large_shape: GammaLargeShape, +} + +/// Gamma distribution where the shape parameter is larger than 1. +/// +/// See `Gamma` for sampling from a Gamma distribution with general +/// shape parameters. +#[derive(Clone, Copy, Debug)] +struct GammaLargeShape { + scale: f64, + c: f64, + d: f64, +} + +impl Gamma { + /// Construct an object representing the `Gamma(shape, scale)` + /// distribution. + /// + /// Panics if `shape <= 0` or `scale <= 0`. + #[inline] + pub fn new(shape: f64, scale: f64) -> Gamma { + assert!(shape > 0.0, "Gamma::new called with shape <= 0"); + assert!(scale > 0.0, "Gamma::new called with scale <= 0"); + + let repr = if shape == 1.0 { + One(Exp::new(1.0 / scale)) + } else if shape < 1.0 { + Small(GammaSmallShape::new_raw(shape, scale)) + } else { + Large(GammaLargeShape::new_raw(shape, scale)) + }; + Gamma { repr } + } +} + +impl GammaSmallShape { + fn new_raw(shape: f64, scale: f64) -> GammaSmallShape { + GammaSmallShape { + inv_shape: 1. / shape, + large_shape: GammaLargeShape::new_raw(shape + 1.0, scale), + } + } +} + +impl GammaLargeShape { + fn new_raw(shape: f64, scale: f64) -> GammaLargeShape { + let d = shape - 1. / 3.; + GammaLargeShape { + scale, + c: 1. / (9. * d).sqrt(), + d, + } + } +} + +impl Distribution<f64> for Gamma { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + match self.repr { + Small(ref g) => g.sample(rng), + One(ref g) => g.sample(rng), + Large(ref g) => g.sample(rng), + } + } +} +impl Distribution<f64> for GammaSmallShape { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let u: f64 = rng.sample(Open01); + + self.large_shape.sample(rng) * u.powf(self.inv_shape) + } +} +impl Distribution<f64> for GammaLargeShape { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + loop { + let x = rng.sample(StandardNormal); + let v_cbrt = 1.0 + self.c * x; + if v_cbrt <= 0.0 { + // a^3 <= 0 iff a <= 0 + continue; + } + + let v = v_cbrt * v_cbrt * v_cbrt; + let u: f64 = rng.sample(Open01); + + let x_sqr = x * x; + if u < 1.0 - 0.0331 * x_sqr * x_sqr + || u.ln() < 0.5 * x_sqr + self.d * (1.0 - v + v.ln()) + { + return self.d * v * self.scale; + } + } + } +} + +/// The chi-squared distribution `χ²(k)`, where `k` is the degrees of +/// freedom. +/// +/// For `k > 0` integral, this distribution is the sum of the squares +/// of `k` independent standard normal random variables. For other +/// `k`, this uses the equivalent characterisation +/// `χ²(k) = Gamma(k/2, 2)`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct ChiSquared { + repr: ChiSquaredRepr, +} + +#[derive(Clone, Copy, Debug)] +enum ChiSquaredRepr { + // k == 1, Gamma(alpha, ..) is particularly slow for alpha < 1, + // e.g. when alpha = 1/2 as it would be for this case, so special- + // casing and using the definition of N(0,1)^2 is faster. + DoFExactlyOne, + DoFAnythingElse(Gamma), +} + +impl ChiSquared { + /// Create a new chi-squared distribution with degrees-of-freedom + /// `k`. Panics if `k < 0`. + pub fn new(k: f64) -> ChiSquared { + let repr = if k == 1.0 { + DoFExactlyOne + } else { + assert!(k > 0.0, "ChiSquared::new called with `k` < 0"); + DoFAnythingElse(Gamma::new(0.5 * k, 2.0)) + }; + ChiSquared { repr } + } +} +impl Distribution<f64> for ChiSquared { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + match self.repr { + DoFExactlyOne => { + // k == 1 => N(0,1)^2 + let norm = rng.sample(StandardNormal); + norm * norm + } + DoFAnythingElse(ref g) => g.sample(rng), + } + } +} + +/// The Fisher F distribution `F(m, n)`. +/// +/// This distribution is equivalent to the ratio of two normalised +/// chi-squared distributions, that is, `F(m,n) = (χ²(m)/m) / +/// (χ²(n)/n)`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct FisherF { + numer: ChiSquared, + denom: ChiSquared, + // denom_dof / numer_dof so that this can just be a straight + // multiplication, rather than a division. + dof_ratio: f64, +} + +impl FisherF { + /// Create a new `FisherF` distribution, with the given + /// parameter. Panics if either `m` or `n` are not positive. + pub fn new(m: f64, n: f64) -> FisherF { + assert!(m > 0.0, "FisherF::new called with `m < 0`"); + assert!(n > 0.0, "FisherF::new called with `n < 0`"); + + FisherF { + numer: ChiSquared::new(m), + denom: ChiSquared::new(n), + dof_ratio: n / m, + } + } +} +impl Distribution<f64> for FisherF { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + self.numer.sample(rng) / self.denom.sample(rng) * self.dof_ratio + } +} + +/// The Student t distribution, `t(nu)`, where `nu` is the degrees of +/// freedom. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct StudentT { + chi: ChiSquared, + dof: f64, +} + +impl StudentT { + /// Create a new Student t distribution with `n` degrees of + /// freedom. Panics if `n <= 0`. + pub fn new(n: f64) -> StudentT { + assert!(n > 0.0, "StudentT::new called with `n <= 0`"); + StudentT { + chi: ChiSquared::new(n), + dof: n, + } + } +} +impl Distribution<f64> for StudentT { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let norm = rng.sample(StandardNormal); + norm * (self.dof / self.chi.sample(rng)).sqrt() + } +} + +/// The Beta distribution with shape parameters `alpha` and `beta`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Beta { + gamma_a: Gamma, + gamma_b: Gamma, +} + +impl Beta { + /// Construct an object representing the `Beta(alpha, beta)` + /// distribution. + /// + /// Panics if `shape <= 0` or `scale <= 0`. + pub fn new(alpha: f64, beta: f64) -> Beta { + assert!((alpha > 0.) & (beta > 0.)); + Beta { + gamma_a: Gamma::new(alpha, 1.), + gamma_b: Gamma::new(beta, 1.), + } + } +} + +impl Distribution<f64> for Beta { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let x = self.gamma_a.sample(rng); + let y = self.gamma_b.sample(rng); + x / (x + y) + } +} + +#[cfg(test)] +mod test { + use super::{Beta, ChiSquared, FisherF, StudentT}; + use crate::distributions::Distribution; + + const N: u32 = 100; + + #[test] + fn test_chi_squared_one() { + let chi = ChiSquared::new(1.0); + let mut rng = crate::test::rng(201); + for _ in 0..N { + chi.sample(&mut rng); + } + } + #[test] + fn test_chi_squared_small() { + let chi = ChiSquared::new(0.5); + let mut rng = crate::test::rng(202); + for _ in 0..N { + chi.sample(&mut rng); + } + } + #[test] + fn test_chi_squared_large() { + let chi = ChiSquared::new(30.0); + let mut rng = crate::test::rng(203); + for _ in 0..N { + chi.sample(&mut rng); + } + } + #[test] + #[should_panic] + fn test_chi_squared_invalid_dof() { + ChiSquared::new(-1.0); + } + + #[test] + fn test_f() { + let f = FisherF::new(2.0, 32.0); + let mut rng = crate::test::rng(204); + for _ in 0..N { + f.sample(&mut rng); + } + } + + #[test] + fn test_t() { + let t = StudentT::new(11.0); + let mut rng = crate::test::rng(205); + for _ in 0..N { + t.sample(&mut rng); + } + } + + #[test] + fn test_beta() { + let beta = Beta::new(1.0, 2.0); + let mut rng = crate::test::rng(201); + for _ in 0..N { + beta.sample(&mut rng); + } + } + + #[test] + #[should_panic] + fn test_beta_invalid_dof() { + Beta::new(0., 0.); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/integer.rs b/vendor/rand-0.7.3/src/distributions/integer.rs new file mode 100644 index 000000000..f2db1f1c6 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/integer.rs @@ -0,0 +1,279 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The implementations of the `Standard` distribution for integer types. + +use crate::distributions::{Distribution, Standard}; +use crate::Rng; +#[cfg(all(target_arch = "x86", feature = "nightly"))] use core::arch::x86::*; +#[cfg(all(target_arch = "x86_64", feature = "nightly"))] +use core::arch::x86_64::*; +#[cfg(not(target_os = "emscripten"))] use core::num::NonZeroU128; +use core::num::{NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8, NonZeroUsize}; +#[cfg(feature = "simd_support")] use packed_simd::*; + +impl Distribution<u8> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u8 { + rng.next_u32() as u8 + } +} + +impl Distribution<u16> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u16 { + rng.next_u32() as u16 + } +} + +impl Distribution<u32> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u32 { + rng.next_u32() + } +} + +impl Distribution<u64> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u64 { + rng.next_u64() + } +} + +#[cfg(not(target_os = "emscripten"))] +impl Distribution<u128> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u128 { + // Use LE; we explicitly generate one value before the next. + let x = u128::from(rng.next_u64()); + let y = u128::from(rng.next_u64()); + (y << 64) | x + } +} + +impl Distribution<usize> for Standard { + #[inline] + #[cfg(any(target_pointer_width = "32", target_pointer_width = "16"))] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize { + rng.next_u32() as usize + } + + #[inline] + #[cfg(target_pointer_width = "64")] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize { + rng.next_u64() as usize + } +} + +macro_rules! impl_int_from_uint { + ($ty:ty, $uty:ty) => { + impl Distribution<$ty> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + rng.gen::<$uty>() as $ty + } + } + }; +} + +impl_int_from_uint! { i8, u8 } +impl_int_from_uint! { i16, u16 } +impl_int_from_uint! { i32, u32 } +impl_int_from_uint! { i64, u64 } +#[cfg(not(target_os = "emscripten"))] +impl_int_from_uint! { i128, u128 } +impl_int_from_uint! { isize, usize } + +macro_rules! impl_nzint { + ($ty:ty, $new:path) => { + impl Distribution<$ty> for Standard { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + loop { + if let Some(nz) = $new(rng.gen()) { + break nz; + } + } + } + } + }; +} + +impl_nzint!(NonZeroU8, NonZeroU8::new); +impl_nzint!(NonZeroU16, NonZeroU16::new); +impl_nzint!(NonZeroU32, NonZeroU32::new); +impl_nzint!(NonZeroU64, NonZeroU64::new); +#[cfg(not(target_os = "emscripten"))] +impl_nzint!(NonZeroU128, NonZeroU128::new); +impl_nzint!(NonZeroUsize, NonZeroUsize::new); + +#[cfg(feature = "simd_support")] +macro_rules! simd_impl { + ($(($intrinsic:ident, $vec:ty),)+) => {$( + impl Distribution<$intrinsic> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $intrinsic { + $intrinsic::from_bits(rng.gen::<$vec>()) + } + } + )+}; + + ($bits:expr,) => {}; + ($bits:expr, $ty:ty, $($ty_more:ty,)*) => { + simd_impl!($bits, $($ty_more,)*); + + impl Distribution<$ty> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $ty { + let mut vec: $ty = Default::default(); + unsafe { + let ptr = &mut vec; + let b_ptr = &mut *(ptr as *mut $ty as *mut [u8; $bits/8]); + rng.fill_bytes(b_ptr); + } + vec.to_le() + } + } + }; +} + +#[cfg(feature = "simd_support")] +simd_impl!(16, u8x2, i8x2,); +#[cfg(feature = "simd_support")] +simd_impl!(32, u8x4, i8x4, u16x2, i16x2,); +#[cfg(feature = "simd_support")] +simd_impl!(64, u8x8, i8x8, u16x4, i16x4, u32x2, i32x2,); +#[cfg(feature = "simd_support")] +simd_impl!(128, u8x16, i8x16, u16x8, i16x8, u32x4, i32x4, u64x2, i64x2,); +#[cfg(feature = "simd_support")] +simd_impl!(256, u8x32, i8x32, u16x16, i16x16, u32x8, i32x8, u64x4, i64x4,); +#[cfg(feature = "simd_support")] +simd_impl!(512, u8x64, i8x64, u16x32, i16x32, u32x16, i32x16, u64x8, i64x8,); +#[cfg(all( + feature = "simd_support", + feature = "nightly", + any(target_arch = "x86", target_arch = "x86_64") +))] +simd_impl!((__m64, u8x8), (__m128i, u8x16), (__m256i, u8x32),); + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_integers() { + let mut rng = crate::test::rng(806); + + rng.sample::<isize, _>(Standard); + rng.sample::<i8, _>(Standard); + rng.sample::<i16, _>(Standard); + rng.sample::<i32, _>(Standard); + rng.sample::<i64, _>(Standard); + #[cfg(not(target_os = "emscripten"))] + rng.sample::<i128, _>(Standard); + + rng.sample::<usize, _>(Standard); + rng.sample::<u8, _>(Standard); + rng.sample::<u16, _>(Standard); + rng.sample::<u32, _>(Standard); + rng.sample::<u64, _>(Standard); + #[cfg(not(target_os = "emscripten"))] + rng.sample::<u128, _>(Standard); + } + + #[test] + fn value_stability() { + fn test_samples<T: Copy + core::fmt::Debug + PartialEq>(zero: T, expected: &[T]) + where Standard: Distribution<T> { + let mut rng = crate::test::rng(807); + let mut buf = [zero; 3]; + for x in &mut buf { + *x = rng.sample(Standard); + } + assert_eq!(&buf, expected); + } + + test_samples(0u8, &[9, 247, 111]); + test_samples(0u16, &[32265, 42999, 38255]); + test_samples(0u32, &[2220326409, 2575017975, 2018088303]); + test_samples(0u64, &[ + 11059617991457472009, + 16096616328739788143, + 1487364411147516184, + ]); + test_samples(0u128, &[ + 296930161868957086625409848350820761097, + 145644820879247630242265036535529306392, + 111087889832015897993126088499035356354, + ]); + #[cfg(any(target_pointer_width = "32", target_pointer_width = "16"))] + test_samples(0usize, &[2220326409, 2575017975, 2018088303]); + #[cfg(target_pointer_width = "64")] + test_samples(0usize, &[ + 11059617991457472009, + 16096616328739788143, + 1487364411147516184, + ]); + + test_samples(0i8, &[9, -9, 111]); + // Skip further i* types: they are simple reinterpretation of u* samples + + #[cfg(feature = "simd_support")] + { + // We only test a sub-set of types here and make assumptions about the rest. + + test_samples(u8x2::default(), &[ + u8x2::new(9, 126), + u8x2::new(247, 167), + u8x2::new(111, 149), + ]); + test_samples(u8x4::default(), &[ + u8x4::new(9, 126, 87, 132), + u8x4::new(247, 167, 123, 153), + u8x4::new(111, 149, 73, 120), + ]); + test_samples(u8x8::default(), &[ + u8x8::new(9, 126, 87, 132, 247, 167, 123, 153), + u8x8::new(111, 149, 73, 120, 68, 171, 98, 223), + u8x8::new(24, 121, 1, 50, 13, 46, 164, 20), + ]); + + test_samples(i64x8::default(), &[ + i64x8::new( + -7387126082252079607, + -2350127744969763473, + 1487364411147516184, + 7895421560427121838, + 602190064936008898, + 6022086574635100741, + -5080089175222015595, + -4066367846667249123, + ), + i64x8::new( + 9180885022207963908, + 3095981199532211089, + 6586075293021332726, + 419343203796414657, + 3186951873057035255, + 5287129228749947252, + 444726432079249540, + -1587028029513790706, + ), + i64x8::new( + 6075236523189346388, + 1351763722368165432, + -6192309979959753740, + -7697775502176768592, + -4482022114172078123, + 7522501477800909500, + -1837258847956201231, + -586926753024886735, + ), + ]); + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/mod.rs b/vendor/rand-0.7.3/src/distributions/mod.rs new file mode 100644 index 000000000..4e1b1a6e3 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/mod.rs @@ -0,0 +1,406 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013-2017 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Generating random samples from probability distributions +//! +//! This module is the home of the [`Distribution`] trait and several of its +//! implementations. It is the workhorse behind some of the convenient +//! functionality of the [`Rng`] trait, e.g. [`Rng::gen`], [`Rng::gen_range`] and +//! of course [`Rng::sample`]. +//! +//! Abstractly, a [probability distribution] describes the probability of +//! occurance of each value in its sample space. +//! +//! More concretely, an implementation of `Distribution<T>` for type `X` is an +//! algorithm for choosing values from the sample space (a subset of `T`) +//! according to the distribution `X` represents, using an external source of +//! randomness (an RNG supplied to the `sample` function). +//! +//! A type `X` may implement `Distribution<T>` for multiple types `T`. +//! Any type implementing [`Distribution`] is stateless (i.e. immutable), +//! but it may have internal parameters set at construction time (for example, +//! [`Uniform`] allows specification of its sample space as a range within `T`). +//! +//! +//! # The `Standard` distribution +//! +//! The [`Standard`] distribution is important to mention. This is the +//! distribution used by [`Rng::gen`] and represents the "default" way to +//! produce a random value for many different types, including most primitive +//! types, tuples, arrays, and a few derived types. See the documentation of +//! [`Standard`] for more details. +//! +//! Implementing `Distribution<T>` for [`Standard`] for user types `T` makes it +//! possible to generate type `T` with [`Rng::gen`], and by extension also +//! with the [`random`] function. +//! +//! ## Random characters +//! +//! [`Alphanumeric`] is a simple distribution to sample random letters and +//! numbers of the `char` type; in contrast [`Standard`] may sample any valid +//! `char`. +//! +//! +//! # Uniform numeric ranges +//! +//! The [`Uniform`] distribution is more flexible than [`Standard`], but also +//! more specialised: it supports fewer target types, but allows the sample +//! space to be specified as an arbitrary range within its target type `T`. +//! Both [`Standard`] and [`Uniform`] are in some sense uniform distributions. +//! +//! Values may be sampled from this distribution using [`Rng::gen_range`] or +//! by creating a distribution object with [`Uniform::new`], +//! [`Uniform::new_inclusive`] or `From<Range>`. When the range limits are not +//! known at compile time it is typically faster to reuse an existing +//! distribution object than to call [`Rng::gen_range`]. +//! +//! User types `T` may also implement `Distribution<T>` for [`Uniform`], +//! although this is less straightforward than for [`Standard`] (see the +//! documentation in the [`uniform`] module. Doing so enables generation of +//! values of type `T` with [`Rng::gen_range`]. +//! +//! ## Open and half-open ranges +//! +//! There are surprisingly many ways to uniformly generate random floats. A +//! range between 0 and 1 is standard, but the exact bounds (open vs closed) +//! and accuracy differ. In addition to the [`Standard`] distribution Rand offers +//! [`Open01`] and [`OpenClosed01`]. See "Floating point implementation" section of +//! [`Standard`] documentation for more details. +//! +//! # Non-uniform sampling +//! +//! Sampling a simple true/false outcome with a given probability has a name: +//! the [`Bernoulli`] distribution (this is used by [`Rng::gen_bool`]). +//! +//! For weighted sampling from a sequence of discrete values, use the +//! [`weighted`] module. +//! +//! This crate no longer includes other non-uniform distributions; instead +//! it is recommended that you use either [`rand_distr`] or [`statrs`]. +//! +//! +//! [probability distribution]: https://en.wikipedia.org/wiki/Probability_distribution +//! [`rand_distr`]: https://crates.io/crates/rand_distr +//! [`statrs`]: https://crates.io/crates/statrs + +//! [`random`]: crate::random +//! [`rand_distr`]: https://crates.io/crates/rand_distr +//! [`statrs`]: https://crates.io/crates/statrs + +use crate::Rng; +use core::iter; + +pub use self::bernoulli::{Bernoulli, BernoulliError}; +pub use self::float::{Open01, OpenClosed01}; +pub use self::other::Alphanumeric; +#[doc(inline)] pub use self::uniform::Uniform; +#[cfg(feature = "alloc")] +pub use self::weighted::{WeightedError, WeightedIndex}; + +// The following are all deprecated after being moved to rand_distr +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::binomial::Binomial; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::cauchy::Cauchy; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::dirichlet::Dirichlet; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::exponential::{Exp, Exp1}; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::gamma::{Beta, ChiSquared, FisherF, Gamma, StudentT}; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::normal::{LogNormal, Normal, StandardNormal}; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::pareto::Pareto; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::poisson::Poisson; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::triangular::Triangular; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::unit_circle::UnitCircle; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::unit_sphere::UnitSphereSurface; +#[allow(deprecated)] +#[cfg(feature = "std")] +pub use self::weibull::Weibull; + +mod bernoulli; +#[cfg(feature = "std")] mod binomial; +#[cfg(feature = "std")] mod cauchy; +#[cfg(feature = "std")] mod dirichlet; +#[cfg(feature = "std")] mod exponential; +#[cfg(feature = "std")] mod gamma; +#[cfg(feature = "std")] mod normal; +#[cfg(feature = "std")] mod pareto; +#[cfg(feature = "std")] mod poisson; +#[cfg(feature = "std")] mod triangular; +pub mod uniform; +#[cfg(feature = "std")] mod unit_circle; +#[cfg(feature = "std")] mod unit_sphere; +#[cfg(feature = "std")] mod weibull; +#[cfg(feature = "alloc")] pub mod weighted; + +mod float; +#[doc(hidden)] +pub mod hidden_export { + pub use super::float::IntoFloat; // used by rand_distr +} +mod integer; +mod other; +mod utils; +#[cfg(feature = "std")] mod ziggurat_tables; + +/// Types (distributions) that can be used to create a random instance of `T`. +/// +/// It is possible to sample from a distribution through both the +/// `Distribution` and [`Rng`] traits, via `distr.sample(&mut rng)` and +/// `rng.sample(distr)`. They also both offer the [`sample_iter`] method, which +/// produces an iterator that samples from the distribution. +/// +/// All implementations are expected to be immutable; this has the significant +/// advantage of not needing to consider thread safety, and for most +/// distributions efficient state-less sampling algorithms are available. +/// +/// Implementations are typically expected to be portable with reproducible +/// results when used with a PRNG with fixed seed; see the +/// [portability chapter](https://rust-random.github.io/book/portability.html) +/// of The Rust Rand Book. In some cases this does not apply, e.g. the `usize` +/// type requires different sampling on 32-bit and 64-bit machines. +/// +/// [`sample_iter`]: Distribution::method.sample_iter +pub trait Distribution<T> { + /// Generate a random value of `T`, using `rng` as the source of randomness. + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T; + + /// Create an iterator that generates random values of `T`, using `rng` as + /// the source of randomness. + /// + /// Note that this function takes `self` by value. This works since + /// `Distribution<T>` is impl'd for `&D` where `D: Distribution<T>`, + /// however borrowing is not automatic hence `distr.sample_iter(...)` may + /// need to be replaced with `(&distr).sample_iter(...)` to borrow or + /// `(&*distr).sample_iter(...)` to reborrow an existing reference. + /// + /// # Example + /// + /// ``` + /// use rand::thread_rng; + /// use rand::distributions::{Distribution, Alphanumeric, Uniform, Standard}; + /// + /// let rng = thread_rng(); + /// + /// // Vec of 16 x f32: + /// let v: Vec<f32> = Standard.sample_iter(rng).take(16).collect(); + /// + /// // String: + /// let s: String = Alphanumeric.sample_iter(rng).take(7).collect(); + /// + /// // Dice-rolling: + /// let die_range = Uniform::new_inclusive(1, 6); + /// let mut roll_die = die_range.sample_iter(rng); + /// while roll_die.next().unwrap() != 6 { + /// println!("Not a 6; rolling again!"); + /// } + /// ``` + fn sample_iter<R>(self, rng: R) -> DistIter<Self, R, T> + where + R: Rng, + Self: Sized, + { + DistIter { + distr: self, + rng, + phantom: ::core::marker::PhantomData, + } + } +} + +impl<'a, T, D: Distribution<T>> Distribution<T> for &'a D { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> T { + (*self).sample(rng) + } +} + + +/// An iterator that generates random values of `T` with distribution `D`, +/// using `R` as the source of randomness. +/// +/// This `struct` is created by the [`sample_iter`] method on [`Distribution`]. +/// See its documentation for more. +/// +/// [`sample_iter`]: Distribution::sample_iter +#[derive(Debug)] +pub struct DistIter<D, R, T> { + distr: D, + rng: R, + phantom: ::core::marker::PhantomData<T>, +} + +impl<D, R, T> Iterator for DistIter<D, R, T> +where + D: Distribution<T>, + R: Rng, +{ + type Item = T; + + #[inline(always)] + fn next(&mut self) -> Option<T> { + // Here, self.rng may be a reference, but we must take &mut anyway. + // Even if sample could take an R: Rng by value, we would need to do this + // since Rng is not copyable and we cannot enforce that this is "reborrowable". + Some(self.distr.sample(&mut self.rng)) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + (usize::max_value(), None) + } +} + +impl<D, R, T> iter::FusedIterator for DistIter<D, R, T> +where + D: Distribution<T>, + R: Rng, +{ +} + +#[cfg(features = "nightly")] +impl<D, R, T> iter::TrustedLen for DistIter<D, R, T> +where + D: Distribution<T>, + R: Rng, +{ +} + + +/// A generic random value distribution, implemented for many primitive types. +/// Usually generates values with a numerically uniform distribution, and with a +/// range appropriate to the type. +/// +/// ## Provided implementations +/// +/// Assuming the provided `Rng` is well-behaved, these implementations +/// generate values with the following ranges and distributions: +/// +/// * Integers (`i32`, `u32`, `isize`, `usize`, etc.): Uniformly distributed +/// over all values of the type. +/// * `char`: Uniformly distributed over all Unicode scalar values, i.e. all +/// code points in the range `0...0x10_FFFF`, except for the range +/// `0xD800...0xDFFF` (the surrogate code points). This includes +/// unassigned/reserved code points. +/// * `bool`: Generates `false` or `true`, each with probability 0.5. +/// * Floating point types (`f32` and `f64`): Uniformly distributed in the +/// half-open range `[0, 1)`. See notes below. +/// * Wrapping integers (`Wrapping<T>`), besides the type identical to their +/// normal integer variants. +/// +/// The `Standard` distribution also supports generation of the following +/// compound types where all component types are supported: +/// +/// * Tuples (up to 12 elements): each element is generated sequentially. +/// * Arrays (up to 32 elements): each element is generated sequentially; +/// see also [`Rng::fill`] which supports arbitrary array length for integer +/// types and tends to be faster for `u32` and smaller types. +/// * `Option<T>` first generates a `bool`, and if true generates and returns +/// `Some(value)` where `value: T`, otherwise returning `None`. +/// +/// ## Custom implementations +/// +/// The [`Standard`] distribution may be implemented for user types as follows: +/// +/// ``` +/// # #![allow(dead_code)] +/// use rand::Rng; +/// use rand::distributions::{Distribution, Standard}; +/// +/// struct MyF32 { +/// x: f32, +/// } +/// +/// impl Distribution<MyF32> for Standard { +/// fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> MyF32 { +/// MyF32 { x: rng.gen() } +/// } +/// } +/// ``` +/// +/// ## Example usage +/// ``` +/// use rand::prelude::*; +/// use rand::distributions::Standard; +/// +/// let val: f32 = StdRng::from_entropy().sample(Standard); +/// println!("f32 from [0, 1): {}", val); +/// ``` +/// +/// # Floating point implementation +/// The floating point implementations for `Standard` generate a random value in +/// the half-open interval `[0, 1)`, i.e. including 0 but not 1. +/// +/// All values that can be generated are of the form `n * ε/2`. For `f32` +/// the 24 most significant random bits of a `u32` are used and for `f64` the +/// 53 most significant bits of a `u64` are used. The conversion uses the +/// multiplicative method: `(rng.gen::<$uty>() >> N) as $ty * (ε/2)`. +/// +/// See also: [`Open01`] which samples from `(0, 1)`, [`OpenClosed01`] which +/// samples from `(0, 1]` and `Rng::gen_range(0, 1)` which also samples from +/// `[0, 1)`. Note that `Open01` and `gen_range` (which uses [`Uniform`]) use +/// transmute-based methods which yield 1 bit less precision but may perform +/// faster on some architectures (on modern Intel CPUs all methods have +/// approximately equal performance). +/// +/// [`Uniform`]: uniform::Uniform +#[derive(Clone, Copy, Debug)] +pub struct Standard; + + +#[cfg(all(test, feature = "std"))] +mod tests { + use super::{Distribution, Uniform}; + use crate::Rng; + + #[test] + fn test_distributions_iter() { + use crate::distributions::Open01; + let mut rng = crate::test::rng(210); + let distr = Open01; + let results: Vec<f32> = distr.sample_iter(&mut rng).take(100).collect(); + println!("{:?}", results); + } + + #[test] + fn test_make_an_iter() { + fn ten_dice_rolls_other_than_five<'a, R: Rng>( + rng: &'a mut R, + ) -> impl Iterator<Item = i32> + 'a { + Uniform::new_inclusive(1, 6) + .sample_iter(rng) + .filter(|x| *x != 5) + .take(10) + } + + let mut rng = crate::test::rng(211); + let mut count = 0; + for val in ten_dice_rolls_other_than_five(&mut rng) { + assert!(val >= 1 && val <= 6 && val != 5); + count += 1; + } + assert_eq!(count, 10); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/normal.rs b/vendor/rand-0.7.3/src/distributions/normal.rs new file mode 100644 index 000000000..ec62fa9ab --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/normal.rs @@ -0,0 +1,177 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The normal and derived distributions. +#![allow(deprecated)] + +use crate::distributions::utils::ziggurat; +use crate::distributions::{ziggurat_tables, Distribution, Open01}; +use crate::Rng; + +/// Samples floating-point numbers according to the normal distribution +/// `N(0, 1)` (a.k.a. a standard normal, or Gaussian). This is equivalent to +/// `Normal::new(0.0, 1.0)` but faster. +/// +/// See `Normal` for the general normal distribution. +/// +/// Implemented via the ZIGNOR variant[^1] of the Ziggurat method. +/// +/// [^1]: Jurgen A. Doornik (2005). [*An Improved Ziggurat Method to +/// Generate Normal Random Samples*]( +/// https://www.doornik.com/research/ziggurat.pdf). +/// Nuffield College, Oxford +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct StandardNormal; + +impl Distribution<f64> for StandardNormal { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + #[inline] + fn pdf(x: f64) -> f64 { + (-x * x / 2.0).exp() + } + #[inline] + fn zero_case<R: Rng + ?Sized>(rng: &mut R, u: f64) -> f64 { + // compute a random number in the tail by hand + + // strange initial conditions, because the loop is not + // do-while, so the condition should be true on the first + // run, they get overwritten anyway (0 < 1, so these are + // good). + let mut x = 1.0f64; + let mut y = 0.0f64; + + while -2.0 * y < x * x { + let x_: f64 = rng.sample(Open01); + let y_: f64 = rng.sample(Open01); + + x = x_.ln() / ziggurat_tables::ZIG_NORM_R; + y = y_.ln(); + } + + if u < 0.0 { + x - ziggurat_tables::ZIG_NORM_R + } else { + ziggurat_tables::ZIG_NORM_R - x + } + } + + ziggurat( + rng, + true, // this is symmetric + &ziggurat_tables::ZIG_NORM_X, + &ziggurat_tables::ZIG_NORM_F, + pdf, + zero_case, + ) + } +} + +/// The normal distribution `N(mean, std_dev**2)`. +/// +/// This uses the ZIGNOR variant of the Ziggurat method, see [`StandardNormal`] +/// for more details. +/// +/// Note that [`StandardNormal`] is an optimised implementation for mean 0, and +/// standard deviation 1. +/// +/// [`StandardNormal`]: crate::distributions::StandardNormal +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Normal { + mean: f64, + std_dev: f64, +} + +impl Normal { + /// Construct a new `Normal` distribution with the given mean and + /// standard deviation. + /// + /// # Panics + /// + /// Panics if `std_dev < 0`. + #[inline] + pub fn new(mean: f64, std_dev: f64) -> Normal { + assert!(std_dev >= 0.0, "Normal::new called with `std_dev` < 0"); + Normal { mean, std_dev } + } +} +impl Distribution<f64> for Normal { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let n = rng.sample(StandardNormal); + self.mean + self.std_dev * n + } +} + + +/// The log-normal distribution `ln N(mean, std_dev**2)`. +/// +/// If `X` is log-normal distributed, then `ln(X)` is `N(mean, std_dev**2)` +/// distributed. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct LogNormal { + norm: Normal, +} + +impl LogNormal { + /// Construct a new `LogNormal` distribution with the given mean + /// and standard deviation. + /// + /// # Panics + /// + /// Panics if `std_dev < 0`. + #[inline] + pub fn new(mean: f64, std_dev: f64) -> LogNormal { + assert!(std_dev >= 0.0, "LogNormal::new called with `std_dev` < 0"); + LogNormal { + norm: Normal::new(mean, std_dev), + } + } +} +impl Distribution<f64> for LogNormal { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + self.norm.sample(rng).exp() + } +} + +#[cfg(test)] +mod tests { + use super::{LogNormal, Normal}; + use crate::distributions::Distribution; + + #[test] + fn test_normal() { + let norm = Normal::new(10.0, 10.0); + let mut rng = crate::test::rng(210); + for _ in 0..1000 { + norm.sample(&mut rng); + } + } + #[test] + #[should_panic] + fn test_normal_invalid_sd() { + Normal::new(10.0, -1.0); + } + + + #[test] + fn test_log_normal() { + let lnorm = LogNormal::new(10.0, 10.0); + let mut rng = crate::test::rng(211); + for _ in 0..1000 { + lnorm.sample(&mut rng); + } + } + #[test] + #[should_panic] + fn test_log_normal_invalid_sd() { + LogNormal::new(10.0, -1.0); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/other.rs b/vendor/rand-0.7.3/src/distributions/other.rs new file mode 100644 index 000000000..c95060e51 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/other.rs @@ -0,0 +1,291 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The implementations of the `Standard` distribution for other built-in types. + +use core::char; +use core::num::Wrapping; + +use crate::distributions::{Distribution, Standard, Uniform}; +use crate::Rng; + +// ----- Sampling distributions ----- + +/// Sample a `char`, uniformly distributed over ASCII letters and numbers: +/// a-z, A-Z and 0-9. +/// +/// # Example +/// +/// ``` +/// use std::iter; +/// use rand::{Rng, thread_rng}; +/// use rand::distributions::Alphanumeric; +/// +/// let mut rng = thread_rng(); +/// let chars: String = iter::repeat(()) +/// .map(|()| rng.sample(Alphanumeric)) +/// .take(7) +/// .collect(); +/// println!("Random chars: {}", chars); +/// ``` +#[derive(Debug)] +pub struct Alphanumeric; + + +// ----- Implementations of distributions ----- + +impl Distribution<char> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char { + // A valid `char` is either in the interval `[0, 0xD800)` or + // `(0xDFFF, 0x11_0000)`. All `char`s must therefore be in + // `[0, 0x11_0000)` but not in the "gap" `[0xD800, 0xDFFF]` which is + // reserved for surrogates. This is the size of that gap. + const GAP_SIZE: u32 = 0xDFFF - 0xD800 + 1; + + // Uniform::new(0, 0x11_0000 - GAP_SIZE) can also be used but it + // seemed slower. + let range = Uniform::new(GAP_SIZE, 0x11_0000); + + let mut n = range.sample(rng); + if n <= 0xDFFF { + n -= GAP_SIZE; + } + unsafe { char::from_u32_unchecked(n) } + } +} + +impl Distribution<char> for Alphanumeric { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char { + const RANGE: u32 = 26 + 26 + 10; + const GEN_ASCII_STR_CHARSET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\ + abcdefghijklmnopqrstuvwxyz\ + 0123456789"; + // We can pick from 62 characters. This is so close to a power of 2, 64, + // that we can do better than `Uniform`. Use a simple bitshift and + // rejection sampling. We do not use a bitmask, because for small RNGs + // the most significant bits are usually of higher quality. + loop { + let var = rng.next_u32() >> (32 - 6); + if var < RANGE { + return GEN_ASCII_STR_CHARSET[var as usize] as char; + } + } + } +} + +impl Distribution<bool> for Standard { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool { + // We can compare against an arbitrary bit of an u32 to get a bool. + // Because the least significant bits of a lower quality RNG can have + // simple patterns, we compare against the most significant bit. This is + // easiest done using a sign test. + (rng.next_u32() as i32) < 0 + } +} + +macro_rules! tuple_impl { + // use variables to indicate the arity of the tuple + ($($tyvar:ident),* ) => { + // the trailing commas are for the 1 tuple + impl< $( $tyvar ),* > + Distribution<( $( $tyvar ),* , )> + for Standard + where $( Standard: Distribution<$tyvar> ),* + { + #[inline] + fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> ( $( $tyvar ),* , ) { + ( + // use the $tyvar's to get the appropriate number of + // repeats (they're not actually needed) + $( + _rng.gen::<$tyvar>() + ),* + , + ) + } + } + } +} + +impl Distribution<()> for Standard { + #[allow(clippy::unused_unit)] + #[inline] + fn sample<R: Rng + ?Sized>(&self, _: &mut R) -> () { + () + } +} +tuple_impl! {A} +tuple_impl! {A, B} +tuple_impl! {A, B, C} +tuple_impl! {A, B, C, D} +tuple_impl! {A, B, C, D, E} +tuple_impl! {A, B, C, D, E, F} +tuple_impl! {A, B, C, D, E, F, G} +tuple_impl! {A, B, C, D, E, F, G, H} +tuple_impl! {A, B, C, D, E, F, G, H, I} +tuple_impl! {A, B, C, D, E, F, G, H, I, J} +tuple_impl! {A, B, C, D, E, F, G, H, I, J, K} +tuple_impl! {A, B, C, D, E, F, G, H, I, J, K, L} + +macro_rules! array_impl { + // recursive, given at least one type parameter: + {$n:expr, $t:ident, $($ts:ident,)*} => { + array_impl!{($n - 1), $($ts,)*} + + impl<T> Distribution<[T; $n]> for Standard where Standard: Distribution<T> { + #[inline] + fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { + [_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*] + } + } + }; + // empty case: + {$n:expr,} => { + impl<T> Distribution<[T; $n]> for Standard { + fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { [] } + } + }; +} + +array_impl! {32, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T,} + +impl<T> Distribution<Option<T>> for Standard +where Standard: Distribution<T> +{ + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<T> { + // UFCS is needed here: https://github.com/rust-lang/rust/issues/24066 + if rng.gen::<bool>() { + Some(rng.gen()) + } else { + None + } + } +} + +impl<T> Distribution<Wrapping<T>> for Standard +where Standard: Distribution<T> +{ + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T> { + Wrapping(rng.gen()) + } +} + + +#[cfg(test)] +mod tests { + use super::*; + use crate::RngCore; + #[cfg(all(not(feature = "std"), feature = "alloc"))] use alloc::string::String; + + #[test] + fn test_misc() { + let rng: &mut dyn RngCore = &mut crate::test::rng(820); + + rng.sample::<char, _>(Standard); + rng.sample::<bool, _>(Standard); + } + + #[cfg(feature = "alloc")] + #[test] + fn test_chars() { + use core::iter; + let mut rng = crate::test::rng(805); + + // Test by generating a relatively large number of chars, so we also + // take the rejection sampling path. + let word: String = iter::repeat(()) + .map(|()| rng.gen::<char>()) + .take(1000) + .collect(); + assert!(word.len() != 0); + } + + #[test] + fn test_alphanumeric() { + let mut rng = crate::test::rng(806); + + // Test by generating a relatively large number of chars, so we also + // take the rejection sampling path. + let mut incorrect = false; + for _ in 0..100 { + let c = rng.sample(Alphanumeric); + incorrect |= !((c >= '0' && c <= '9') || + (c >= 'A' && c <= 'Z') || + (c >= 'a' && c <= 'z') ); + } + assert!(incorrect == false); + } + + #[test] + fn value_stability() { + fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>( + distr: &D, zero: T, expected: &[T], + ) { + let mut rng = crate::test::rng(807); + let mut buf = [zero; 5]; + for x in &mut buf { + *x = rng.sample(&distr); + } + assert_eq!(&buf, expected); + } + + test_samples(&Standard, 'a', &[ + '\u{8cdac}', + '\u{a346a}', + '\u{80120}', + '\u{ed692}', + '\u{35888}', + ]); + test_samples(&Alphanumeric, 'a', &['h', 'm', 'e', '3', 'M']); + test_samples(&Standard, false, &[true, true, false, true, false]); + test_samples(&Standard, None as Option<bool>, &[ + Some(true), + None, + Some(false), + None, + Some(false), + ]); + test_samples(&Standard, Wrapping(0i32), &[ + Wrapping(-2074640887), + Wrapping(-1719949321), + Wrapping(2018088303), + Wrapping(-547181756), + Wrapping(838957336), + ]); + + // We test only sub-sets of tuple and array impls + test_samples(&Standard, (), &[(), (), (), (), ()]); + test_samples(&Standard, (false,), &[ + (true,), + (true,), + (false,), + (true,), + (false,), + ]); + test_samples(&Standard, (false, false), &[ + (true, true), + (false, true), + (false, false), + (true, false), + (false, false), + ]); + + test_samples(&Standard, [0u8; 0], &[[], [], [], [], []]); + test_samples(&Standard, [0u8; 3], &[ + [9, 247, 111], + [68, 24, 13], + [174, 19, 194], + [172, 69, 213], + [149, 207, 29], + ]); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/pareto.rs b/vendor/rand-0.7.3/src/distributions/pareto.rs new file mode 100644 index 000000000..ac5473b8c --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/pareto.rs @@ -0,0 +1,70 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Pareto distribution. +#![allow(deprecated)] + +use crate::distributions::{Distribution, OpenClosed01}; +use crate::Rng; + +/// Samples floating-point numbers according to the Pareto distribution +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Pareto { + scale: f64, + inv_neg_shape: f64, +} + +impl Pareto { + /// Construct a new Pareto distribution with given `scale` and `shape`. + /// + /// In the literature, `scale` is commonly written as x<sub>m</sub> or k and + /// `shape` is often written as α. + /// + /// # Panics + /// + /// `scale` and `shape` have to be non-zero and positive. + pub fn new(scale: f64, shape: f64) -> Pareto { + assert!((scale > 0.) & (shape > 0.)); + Pareto { + scale, + inv_neg_shape: -1.0 / shape, + } + } +} + +impl Distribution<f64> for Pareto { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let u: f64 = rng.sample(OpenClosed01); + self.scale * u.powf(self.inv_neg_shape) + } +} + +#[cfg(test)] +mod tests { + use super::Pareto; + use crate::distributions::Distribution; + + #[test] + #[should_panic] + fn invalid() { + Pareto::new(0., 0.); + } + + #[test] + fn sample() { + let scale = 1.0; + let shape = 2.0; + let d = Pareto::new(scale, shape); + let mut rng = crate::test::rng(1); + for _ in 0..1000 { + let r = d.sample(&mut rng); + assert!(r >= scale); + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/poisson.rs b/vendor/rand-0.7.3/src/distributions/poisson.rs new file mode 100644 index 000000000..ce94d7542 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/poisson.rs @@ -0,0 +1,151 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2016-2017 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Poisson distribution. +#![allow(deprecated)] + +use crate::distributions::utils::log_gamma; +use crate::distributions::{Cauchy, Distribution}; +use crate::Rng; + +/// The Poisson distribution `Poisson(lambda)`. +/// +/// This distribution has a density function: +/// `f(k) = lambda^k * exp(-lambda) / k!` for `k >= 0`. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Poisson { + lambda: f64, + // precalculated values + exp_lambda: f64, + log_lambda: f64, + sqrt_2lambda: f64, + magic_val: f64, +} + +impl Poisson { + /// Construct a new `Poisson` with the given shape parameter + /// `lambda`. Panics if `lambda <= 0`. + pub fn new(lambda: f64) -> Poisson { + assert!(lambda > 0.0, "Poisson::new called with lambda <= 0"); + let log_lambda = lambda.ln(); + Poisson { + lambda, + exp_lambda: (-lambda).exp(), + log_lambda, + sqrt_2lambda: (2.0 * lambda).sqrt(), + magic_val: lambda * log_lambda - log_gamma(1.0 + lambda), + } + } +} + +impl Distribution<u64> for Poisson { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> u64 { + // using the algorithm from Numerical Recipes in C + + // for low expected values use the Knuth method + if self.lambda < 12.0 { + let mut result = 0; + let mut p = 1.0; + while p > self.exp_lambda { + p *= rng.gen::<f64>(); + result += 1; + } + result - 1 + } + // high expected values - rejection method + else { + let mut int_result: u64; + + // we use the Cauchy distribution as the comparison distribution + // f(x) ~ 1/(1+x^2) + let cauchy = Cauchy::new(0.0, 1.0); + + loop { + let mut result; + let mut comp_dev; + + loop { + // draw from the Cauchy distribution + comp_dev = rng.sample(cauchy); + // shift the peak of the comparison ditribution + result = self.sqrt_2lambda * comp_dev + self.lambda; + // repeat the drawing until we are in the range of possible values + if result >= 0.0 { + break; + } + } + // now the result is a random variable greater than 0 with Cauchy distribution + // the result should be an integer value + result = result.floor(); + int_result = result as u64; + + // this is the ratio of the Poisson distribution to the comparison distribution + // the magic value scales the distribution function to a range of approximately 0-1 + // since it is not exact, we multiply the ratio by 0.9 to avoid ratios greater than 1 + // this doesn't change the resulting distribution, only increases the rate of failed drawings + let check = 0.9 + * (1.0 + comp_dev * comp_dev) + * (result * self.log_lambda - log_gamma(1.0 + result) - self.magic_val).exp(); + + // check with uniform random value - if below the threshold, we are within the target distribution + if rng.gen::<f64>() <= check { + break; + } + } + int_result + } + } +} + +#[cfg(test)] +mod test { + use super::Poisson; + use crate::distributions::Distribution; + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_poisson_10() { + let poisson = Poisson::new(10.0); + let mut rng = crate::test::rng(123); + let mut sum = 0; + for _ in 0..1000 { + sum += poisson.sample(&mut rng); + } + let avg = (sum as f64) / 1000.0; + println!("Poisson average: {}", avg); + assert!((avg - 10.0).abs() < 0.5); // not 100% certain, but probable enough + } + + #[test] + fn test_poisson_15() { + // Take the 'high expected values' path + let poisson = Poisson::new(15.0); + let mut rng = crate::test::rng(123); + let mut sum = 0; + for _ in 0..1000 { + sum += poisson.sample(&mut rng); + } + let avg = (sum as f64) / 1000.0; + println!("Poisson average: {}", avg); + assert!((avg - 15.0).abs() < 0.5); // not 100% certain, but probable enough + } + + #[test] + #[should_panic] + fn test_poisson_invalid_lambda_zero() { + Poisson::new(0.0); + } + + #[test] + #[should_panic] + fn test_poisson_invalid_lambda_neg() { + Poisson::new(-10.0); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/triangular.rs b/vendor/rand-0.7.3/src/distributions/triangular.rs new file mode 100644 index 000000000..37be19867 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/triangular.rs @@ -0,0 +1,83 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The triangular distribution. +#![allow(deprecated)] + +use crate::distributions::{Distribution, Standard}; +use crate::Rng; + +/// The triangular distribution. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Triangular { + min: f64, + max: f64, + mode: f64, +} + +impl Triangular { + /// Construct a new `Triangular` with minimum `min`, maximum `max` and mode + /// `mode`. + /// + /// # Panics + /// + /// If `max < mode`, `mode < max` or `max == min`. + #[inline] + pub fn new(min: f64, max: f64, mode: f64) -> Triangular { + assert!(max >= mode); + assert!(mode >= min); + assert!(max != min); + Triangular { min, max, mode } + } +} + +impl Distribution<f64> for Triangular { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let f: f64 = rng.sample(Standard); + let diff_mode_min = self.mode - self.min; + let diff_max_min = self.max - self.min; + if f * diff_max_min < diff_mode_min { + self.min + (f * diff_max_min * diff_mode_min).sqrt() + } else { + self.max - ((1. - f) * diff_max_min * (self.max - self.mode)).sqrt() + } + } +} + +#[cfg(test)] +mod test { + use super::Triangular; + use crate::distributions::Distribution; + + #[test] + fn test_new() { + for &(min, max, mode) in &[ + (-1., 1., 0.), + (1., 2., 1.), + (5., 25., 25.), + (1e-5, 1e5, 1e-3), + (0., 1., 0.9), + (-4., -0.5, -2.), + (-13.039, 8.41, 1.17), + ] { + println!("{} {} {}", min, max, mode); + let _ = Triangular::new(min, max, mode); + } + } + + #[test] + fn test_sample() { + let norm = Triangular::new(0., 1., 0.5); + let mut rng = crate::test::rng(1); + for _ in 0..1000 { + norm.sample(&mut rng); + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/uniform.rs b/vendor/rand-0.7.3/src/distributions/uniform.rs new file mode 100644 index 000000000..8584152f0 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/uniform.rs @@ -0,0 +1,1380 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2017 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A distribution uniformly sampling numbers within a given range. +//! +//! [`Uniform`] is the standard distribution to sample uniformly from a range; +//! e.g. `Uniform::new_inclusive(1, 6)` can sample integers from 1 to 6, like a +//! standard die. [`Rng::gen_range`] supports any type supported by +//! [`Uniform`]. +//! +//! This distribution is provided with support for several primitive types +//! (all integer and floating-point types) as well as [`std::time::Duration`], +//! and supports extension to user-defined types via a type-specific *back-end* +//! implementation. +//! +//! The types [`UniformInt`], [`UniformFloat`] and [`UniformDuration`] are the +//! back-ends supporting sampling from primitive integer and floating-point +//! ranges as well as from [`std::time::Duration`]; these types do not normally +//! need to be used directly (unless implementing a derived back-end). +//! +//! # Example usage +//! +//! ``` +//! use rand::{Rng, thread_rng}; +//! use rand::distributions::Uniform; +//! +//! let mut rng = thread_rng(); +//! let side = Uniform::new(-10.0, 10.0); +//! +//! // sample between 1 and 10 points +//! for _ in 0..rng.gen_range(1, 11) { +//! // sample a point from the square with sides -10 - 10 in two dimensions +//! let (x, y) = (rng.sample(side), rng.sample(side)); +//! println!("Point: {}, {}", x, y); +//! } +//! ``` +//! +//! # Extending `Uniform` to support a custom type +//! +//! To extend [`Uniform`] to support your own types, write a back-end which +//! implements the [`UniformSampler`] trait, then implement the [`SampleUniform`] +//! helper trait to "register" your back-end. See the `MyF32` example below. +//! +//! At a minimum, the back-end needs to store any parameters needed for sampling +//! (e.g. the target range) and implement `new`, `new_inclusive` and `sample`. +//! Those methods should include an assert to check the range is valid (i.e. +//! `low < high`). The example below merely wraps another back-end. +//! +//! The `new`, `new_inclusive` and `sample_single` functions use arguments of +//! type SampleBorrow<X> in order to support passing in values by reference or +//! by value. In the implementation of these functions, you can choose to +//! simply use the reference returned by [`SampleBorrow::borrow`], or you can choose +//! to copy or clone the value, whatever is appropriate for your type. +//! +//! ``` +//! use rand::prelude::*; +//! use rand::distributions::uniform::{Uniform, SampleUniform, +//! UniformSampler, UniformFloat, SampleBorrow}; +//! +//! struct MyF32(f32); +//! +//! #[derive(Clone, Copy, Debug)] +//! struct UniformMyF32(UniformFloat<f32>); +//! +//! impl UniformSampler for UniformMyF32 { +//! type X = MyF32; +//! fn new<B1, B2>(low: B1, high: B2) -> Self +//! where B1: SampleBorrow<Self::X> + Sized, +//! B2: SampleBorrow<Self::X> + Sized +//! { +//! UniformMyF32(UniformFloat::<f32>::new(low.borrow().0, high.borrow().0)) +//! } +//! fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self +//! where B1: SampleBorrow<Self::X> + Sized, +//! B2: SampleBorrow<Self::X> + Sized +//! { +//! UniformSampler::new(low, high) +//! } +//! fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X { +//! MyF32(self.0.sample(rng)) +//! } +//! } +//! +//! impl SampleUniform for MyF32 { +//! type Sampler = UniformMyF32; +//! } +//! +//! let (low, high) = (MyF32(17.0f32), MyF32(22.0f32)); +//! let uniform = Uniform::new(low, high); +//! let x = uniform.sample(&mut thread_rng()); +//! ``` +//! +//! [`SampleUniform`]: crate::distributions::uniform::SampleUniform +//! [`UniformSampler`]: crate::distributions::uniform::UniformSampler +//! [`UniformInt`]: crate::distributions::uniform::UniformInt +//! [`UniformFloat`]: crate::distributions::uniform::UniformFloat +//! [`UniformDuration`]: crate::distributions::uniform::UniformDuration +//! [`SampleBorrow::borrow`]: crate::distributions::uniform::SampleBorrow::borrow + +#[cfg(not(feature = "std"))] use core::time::Duration; +#[cfg(feature = "std")] use std::time::Duration; + +use crate::distributions::float::IntoFloat; +use crate::distributions::utils::{BoolAsSIMD, FloatAsSIMD, FloatSIMDUtils, WideningMultiply}; +use crate::distributions::Distribution; +use crate::Rng; + +#[cfg(not(feature = "std"))] +#[allow(unused_imports)] // rustc doesn't detect that this is actually used +use crate::distributions::utils::Float; + + +#[cfg(feature = "simd_support")] use packed_simd::*; + +/// Sample values uniformly between two bounds. +/// +/// [`Uniform::new`] and [`Uniform::new_inclusive`] construct a uniform +/// distribution sampling from the given range; these functions may do extra +/// work up front to make sampling of multiple values faster. +/// +/// When sampling from a constant range, many calculations can happen at +/// compile-time and all methods should be fast; for floating-point ranges and +/// the full range of integer types this should have comparable performance to +/// the `Standard` distribution. +/// +/// Steps are taken to avoid bias which might be present in naive +/// implementations; for example `rng.gen::<u8>() % 170` samples from the range +/// `[0, 169]` but is twice as likely to select numbers less than 85 than other +/// values. Further, the implementations here give more weight to the high-bits +/// generated by the RNG than the low bits, since with some RNGs the low-bits +/// are of lower quality than the high bits. +/// +/// Implementations must sample in `[low, high)` range for +/// `Uniform::new(low, high)`, i.e., excluding `high`. In particular care must +/// be taken to ensure that rounding never results values `< low` or `>= high`. +/// +/// # Example +/// +/// ``` +/// use rand::distributions::{Distribution, Uniform}; +/// +/// fn main() { +/// let between = Uniform::from(10..10000); +/// let mut rng = rand::thread_rng(); +/// let mut sum = 0; +/// for _ in 0..1000 { +/// sum += between.sample(&mut rng); +/// } +/// println!("{}", sum); +/// } +/// ``` +/// +/// [`new`]: Uniform::new +/// [`new_inclusive`]: Uniform::new_inclusive +#[derive(Clone, Copy, Debug)] +pub struct Uniform<X: SampleUniform>(X::Sampler); + +impl<X: SampleUniform> Uniform<X> { + /// Create a new `Uniform` instance which samples uniformly from the half + /// open range `[low, high)` (excluding `high`). Panics if `low >= high`. + pub fn new<B1, B2>(low: B1, high: B2) -> Uniform<X> + where + B1: SampleBorrow<X> + Sized, + B2: SampleBorrow<X> + Sized, + { + Uniform(X::Sampler::new(low, high)) + } + + /// Create a new `Uniform` instance which samples uniformly from the closed + /// range `[low, high]` (inclusive). Panics if `low > high`. + pub fn new_inclusive<B1, B2>(low: B1, high: B2) -> Uniform<X> + where + B1: SampleBorrow<X> + Sized, + B2: SampleBorrow<X> + Sized, + { + Uniform(X::Sampler::new_inclusive(low, high)) + } +} + +impl<X: SampleUniform> Distribution<X> for Uniform<X> { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> X { + self.0.sample(rng) + } +} + +/// Helper trait for creating objects using the correct implementation of +/// [`UniformSampler`] for the sampling type. +/// +/// See the [module documentation] on how to implement [`Uniform`] range +/// sampling for a custom type. +/// +/// [module documentation]: crate::distributions::uniform +pub trait SampleUniform: Sized { + /// The `UniformSampler` implementation supporting type `X`. + type Sampler: UniformSampler<X = Self>; +} + +/// Helper trait handling actual uniform sampling. +/// +/// See the [module documentation] on how to implement [`Uniform`] range +/// sampling for a custom type. +/// +/// Implementation of [`sample_single`] is optional, and is only useful when +/// the implementation can be faster than `Self::new(low, high).sample(rng)`. +/// +/// [module documentation]: crate::distributions::uniform +/// [`sample_single`]: UniformSampler::sample_single +pub trait UniformSampler: Sized { + /// The type sampled by this implementation. + type X; + + /// Construct self, with inclusive lower bound and exclusive upper bound + /// `[low, high)`. + /// + /// Usually users should not call this directly but instead use + /// `Uniform::new`, which asserts that `low < high` before calling this. + fn new<B1, B2>(low: B1, high: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized; + + /// Construct self, with inclusive bounds `[low, high]`. + /// + /// Usually users should not call this directly but instead use + /// `Uniform::new_inclusive`, which asserts that `low <= high` before + /// calling this. + fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized; + + /// Sample a value. + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X; + + /// Sample a single value uniformly from a range with inclusive lower bound + /// and exclusive upper bound `[low, high)`. + /// + /// By default this is implemented using + /// `UniformSampler::new(low, high).sample(rng)`. However, for some types + /// more optimal implementations for single usage may be provided via this + /// method (which is the case for integers and floats). + /// Results may not be identical. + /// + /// Note that to use this method in a generic context, the type needs to be + /// retrieved via `SampleUniform::Sampler` as follows: + /// ``` + /// use rand::{thread_rng, distributions::uniform::{SampleUniform, UniformSampler}}; + /// # #[allow(unused)] + /// fn sample_from_range<T: SampleUniform>(lb: T, ub: T) -> T { + /// let mut rng = thread_rng(); + /// <T as SampleUniform>::Sampler::sample_single(lb, ub, &mut rng) + /// } + /// ``` + fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let uniform: Self = UniformSampler::new(low, high); + uniform.sample(rng) + } +} + +impl<X: SampleUniform> From<::core::ops::Range<X>> for Uniform<X> { + fn from(r: ::core::ops::Range<X>) -> Uniform<X> { + Uniform::new(r.start, r.end) + } +} + +impl<X: SampleUniform> From<::core::ops::RangeInclusive<X>> for Uniform<X> { + fn from(r: ::core::ops::RangeInclusive<X>) -> Uniform<X> { + Uniform::new_inclusive(r.start(), r.end()) + } +} + +/// Helper trait similar to [`Borrow`] but implemented +/// only for SampleUniform and references to SampleUniform in +/// order to resolve ambiguity issues. +/// +/// [`Borrow`]: std::borrow::Borrow +pub trait SampleBorrow<Borrowed> { + /// Immutably borrows from an owned value. See [`Borrow::borrow`] + /// + /// [`Borrow::borrow`]: std::borrow::Borrow::borrow + fn borrow(&self) -> &Borrowed; +} +impl<Borrowed> SampleBorrow<Borrowed> for Borrowed +where Borrowed: SampleUniform +{ + #[inline(always)] + fn borrow(&self) -> &Borrowed { + self + } +} +impl<'a, Borrowed> SampleBorrow<Borrowed> for &'a Borrowed +where Borrowed: SampleUniform +{ + #[inline(always)] + fn borrow(&self) -> &Borrowed { + *self + } +} + +//////////////////////////////////////////////////////////////////////////////// + +// What follows are all back-ends. + + +/// The back-end implementing [`UniformSampler`] for integer types. +/// +/// Unless you are implementing [`UniformSampler`] for your own type, this type +/// should not be used directly, use [`Uniform`] instead. +/// +/// # Implementation notes +/// +/// For simplicity, we use the same generic struct `UniformInt<X>` for all +/// integer types `X`. This gives us only one field type, `X`; to store unsigned +/// values of this size, we take use the fact that these conversions are no-ops. +/// +/// For a closed range, the number of possible numbers we should generate is +/// `range = (high - low + 1)`. To avoid bias, we must ensure that the size of +/// our sample space, `zone`, is a multiple of `range`; other values must be +/// rejected (by replacing with a new random sample). +/// +/// As a special case, we use `range = 0` to represent the full range of the +/// result type (i.e. for `new_inclusive($ty::MIN, $ty::MAX)`). +/// +/// The optimum `zone` is the largest product of `range` which fits in our +/// (unsigned) target type. We calculate this by calculating how many numbers we +/// must reject: `reject = (MAX + 1) % range = (MAX - range + 1) % range`. Any (large) +/// product of `range` will suffice, thus in `sample_single` we multiply by a +/// power of 2 via bit-shifting (faster but may cause more rejections). +/// +/// The smallest integer PRNGs generate is `u32`. For 8- and 16-bit outputs we +/// use `u32` for our `zone` and samples (because it's not slower and because +/// it reduces the chance of having to reject a sample). In this case we cannot +/// store `zone` in the target type since it is too large, however we know +/// `ints_to_reject < range <= $unsigned::MAX`. +/// +/// An alternative to using a modulus is widening multiply: After a widening +/// multiply by `range`, the result is in the high word. Then comparing the low +/// word against `zone` makes sure our distribution is uniform. +#[derive(Clone, Copy, Debug)] +pub struct UniformInt<X> { + low: X, + range: X, + z: X, // either ints_to_reject or zone depending on implementation +} + +macro_rules! uniform_int_impl { + ($ty:ty, $unsigned:ident, $u_large:ident) => { + impl SampleUniform for $ty { + type Sampler = UniformInt<$ty>; + } + + impl UniformSampler for UniformInt<$ty> { + // We play free and fast with unsigned vs signed here + // (when $ty is signed), but that's fine, since the + // contract of this macro is for $ty and $unsigned to be + // "bit-equal", so casting between them is a no-op. + + type X = $ty; + + #[inline] // if the range is constant, this helps LLVM to do the + // calculations at compile-time. + fn new<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low < high, "Uniform::new called with `low >= high`"); + UniformSampler::new_inclusive(low, high - 1) + } + + #[inline] // if the range is constant, this helps LLVM to do the + // calculations at compile-time. + fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!( + low <= high, + "Uniform::new_inclusive called with `low > high`" + ); + let unsigned_max = ::core::$u_large::MAX; + + let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned; + let ints_to_reject = if range > 0 { + let range = $u_large::from(range); + (unsigned_max - range + 1) % range + } else { + 0 + }; + + UniformInt { + low: low, + // These are really $unsigned values, but store as $ty: + range: range as $ty, + z: ints_to_reject as $unsigned as $ty, + } + } + + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X { + let range = self.range as $unsigned as $u_large; + if range > 0 { + let unsigned_max = ::core::$u_large::MAX; + let zone = unsigned_max - (self.z as $unsigned as $u_large); + loop { + let v: $u_large = rng.gen(); + let (hi, lo) = v.wmul(range); + if lo <= zone { + return self.low.wrapping_add(hi as $ty); + } + } + } else { + // Sample from the entire integer range. + rng.gen() + } + } + + fn sample_single<R: Rng + ?Sized, B1, B2>(low_b: B1, high_b: B2, rng: &mut R) -> Self::X + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low < high, "UniformSampler::sample_single: low >= high"); + let range = high.wrapping_sub(low) as $unsigned as $u_large; + let zone = if ::core::$unsigned::MAX <= ::core::u16::MAX as $unsigned { + // Using a modulus is faster than the approximation for + // i8 and i16. I suppose we trade the cost of one + // modulus for near-perfect branch prediction. + let unsigned_max: $u_large = ::core::$u_large::MAX; + let ints_to_reject = (unsigned_max - range + 1) % range; + unsigned_max - ints_to_reject + } else { + // conservative but fast approximation. `- 1` is necessary to allow the + // same comparison without bias. + (range << range.leading_zeros()).wrapping_sub(1) + }; + + loop { + let v: $u_large = rng.gen(); + let (hi, lo) = v.wmul(range); + if lo <= zone { + return low.wrapping_add(hi as $ty); + } + } + } + } + }; +} + +uniform_int_impl! { i8, u8, u32 } +uniform_int_impl! { i16, u16, u32 } +uniform_int_impl! { i32, u32, u32 } +uniform_int_impl! { i64, u64, u64 } +#[cfg(not(target_os = "emscripten"))] +uniform_int_impl! { i128, u128, u128 } +uniform_int_impl! { isize, usize, usize } +uniform_int_impl! { u8, u8, u32 } +uniform_int_impl! { u16, u16, u32 } +uniform_int_impl! { u32, u32, u32 } +uniform_int_impl! { u64, u64, u64 } +uniform_int_impl! { usize, usize, usize } +#[cfg(not(target_os = "emscripten"))] +uniform_int_impl! { u128, u128, u128 } + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +macro_rules! uniform_simd_int_impl { + ($ty:ident, $unsigned:ident, $u_scalar:ident) => { + // The "pick the largest zone that can fit in an `u32`" optimization + // is less useful here. Multiple lanes complicate things, we don't + // know the PRNG's minimal output size, and casting to a larger vector + // is generally a bad idea for SIMD performance. The user can still + // implement it manually. + + // TODO: look into `Uniform::<u32x4>::new(0u32, 100)` functionality + // perhaps `impl SampleUniform for $u_scalar`? + impl SampleUniform for $ty { + type Sampler = UniformInt<$ty>; + } + + impl UniformSampler for UniformInt<$ty> { + type X = $ty; + + #[inline] // if the range is constant, this helps LLVM to do the + // calculations at compile-time. + fn new<B1, B2>(low_b: B1, high_b: B2) -> Self + where B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low.lt(high).all(), "Uniform::new called with `low >= high`"); + UniformSampler::new_inclusive(low, high - 1) + } + + #[inline] // if the range is constant, this helps LLVM to do the + // calculations at compile-time. + fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self + where B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low.le(high).all(), + "Uniform::new_inclusive called with `low > high`"); + let unsigned_max = ::core::$u_scalar::MAX; + + // NOTE: these may need to be replaced with explicitly + // wrapping operations if `packed_simd` changes + let range: $unsigned = ((high - low) + 1).cast(); + // `% 0` will panic at runtime. + let not_full_range = range.gt($unsigned::splat(0)); + // replacing 0 with `unsigned_max` allows a faster `select` + // with bitwise OR + let modulo = not_full_range.select(range, $unsigned::splat(unsigned_max)); + // wrapping addition + let ints_to_reject = (unsigned_max - range + 1) % modulo; + // When `range` is 0, `lo` of `v.wmul(range)` will always be + // zero which means only one sample is needed. + let zone = unsigned_max - ints_to_reject; + + UniformInt { + low: low, + // These are really $unsigned values, but store as $ty: + range: range.cast(), + z: zone.cast(), + } + } + + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X { + let range: $unsigned = self.range.cast(); + let zone: $unsigned = self.z.cast(); + + // This might seem very slow, generating a whole new + // SIMD vector for every sample rejection. For most uses + // though, the chance of rejection is small and provides good + // general performance. With multiple lanes, that chance is + // multiplied. To mitigate this, we replace only the lanes of + // the vector which fail, iteratively reducing the chance of + // rejection. The replacement method does however add a little + // overhead. Benchmarking or calculating probabilities might + // reveal contexts where this replacement method is slower. + let mut v: $unsigned = rng.gen(); + loop { + let (hi, lo) = v.wmul(range); + let mask = lo.le(zone); + if mask.all() { + let hi: $ty = hi.cast(); + // wrapping addition + let result = self.low + hi; + // `select` here compiles to a blend operation + // When `range.eq(0).none()` the compare and blend + // operations are avoided. + let v: $ty = v.cast(); + return range.gt($unsigned::splat(0)).select(result, v); + } + // Replace only the failing lanes + v = mask.select(v, rng.gen()); + } + } + } + }; + + // bulk implementation + ($(($unsigned:ident, $signed:ident),)+ $u_scalar:ident) => { + $( + uniform_simd_int_impl!($unsigned, $unsigned, $u_scalar); + uniform_simd_int_impl!($signed, $unsigned, $u_scalar); + )+ + }; +} + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +uniform_simd_int_impl! { + (u64x2, i64x2), + (u64x4, i64x4), + (u64x8, i64x8), + u64 +} + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +uniform_simd_int_impl! { + (u32x2, i32x2), + (u32x4, i32x4), + (u32x8, i32x8), + (u32x16, i32x16), + u32 +} + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +uniform_simd_int_impl! { + (u16x2, i16x2), + (u16x4, i16x4), + (u16x8, i16x8), + (u16x16, i16x16), + (u16x32, i16x32), + u16 +} + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +uniform_simd_int_impl! { + (u8x2, i8x2), + (u8x4, i8x4), + (u8x8, i8x8), + (u8x16, i8x16), + (u8x32, i8x32), + (u8x64, i8x64), + u8 +} + + +/// The back-end implementing [`UniformSampler`] for floating-point types. +/// +/// Unless you are implementing [`UniformSampler`] for your own type, this type +/// should not be used directly, use [`Uniform`] instead. +/// +/// # Implementation notes +/// +/// Instead of generating a float in the `[0, 1)` range using [`Standard`], the +/// `UniformFloat` implementation converts the output of an PRNG itself. This +/// way one or two steps can be optimized out. +/// +/// The floats are first converted to a value in the `[1, 2)` interval using a +/// transmute-based method, and then mapped to the expected range with a +/// multiply and addition. Values produced this way have what equals 23 bits of +/// random digits for an `f32`, and 52 for an `f64`. +/// +/// [`new`]: UniformSampler::new +/// [`new_inclusive`]: UniformSampler::new_inclusive +/// [`Standard`]: crate::distributions::Standard +#[derive(Clone, Copy, Debug)] +pub struct UniformFloat<X> { + low: X, + scale: X, +} + +macro_rules! uniform_float_impl { + ($ty:ty, $uty:ident, $f_scalar:ident, $u_scalar:ident, $bits_to_discard:expr) => { + impl SampleUniform for $ty { + type Sampler = UniformFloat<$ty>; + } + + impl UniformSampler for UniformFloat<$ty> { + type X = $ty; + + fn new<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low.all_lt(high), "Uniform::new called with `low >= high`"); + assert!( + low.all_finite() && high.all_finite(), + "Uniform::new called with non-finite boundaries" + ); + let max_rand = <$ty>::splat( + (::core::$u_scalar::MAX >> $bits_to_discard).into_float_with_exponent(0) - 1.0, + ); + + let mut scale = high - low; + + loop { + let mask = (scale * max_rand + low).ge_mask(high); + if mask.none() { + break; + } + scale = scale.decrease_masked(mask); + } + + debug_assert!(<$ty>::splat(0.0).all_le(scale)); + + UniformFloat { low, scale } + } + + fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!( + low.all_le(high), + "Uniform::new_inclusive called with `low > high`" + ); + assert!( + low.all_finite() && high.all_finite(), + "Uniform::new_inclusive called with non-finite boundaries" + ); + let max_rand = <$ty>::splat( + (::core::$u_scalar::MAX >> $bits_to_discard).into_float_with_exponent(0) - 1.0, + ); + + let mut scale = (high - low) / max_rand; + + loop { + let mask = (scale * max_rand + low).gt_mask(high); + if mask.none() { + break; + } + scale = scale.decrease_masked(mask); + } + + debug_assert!(<$ty>::splat(0.0).all_le(scale)); + + UniformFloat { low, scale } + } + + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X { + // Generate a value in the range [1, 2) + let value1_2 = (rng.gen::<$uty>() >> $bits_to_discard).into_float_with_exponent(0); + + // Get a value in the range [0, 1) in order to avoid + // overflowing into infinity when multiplying with scale + let value0_1 = value1_2 - 1.0; + + // We don't use `f64::mul_add`, because it is not available with + // `no_std`. Furthermore, it is slower for some targets (but + // faster for others). However, the order of multiplication and + // addition is important, because on some platforms (e.g. ARM) + // it will be optimized to a single (non-FMA) instruction. + value0_1 * self.scale + self.low + } + + #[inline] + fn sample_single<R: Rng + ?Sized, B1, B2>(low_b: B1, high_b: B2, rng: &mut R) -> Self::X + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!( + low.all_lt(high), + "UniformSampler::sample_single: low >= high" + ); + let mut scale = high - low; + + loop { + // Generate a value in the range [1, 2) + let value1_2 = + (rng.gen::<$uty>() >> $bits_to_discard).into_float_with_exponent(0); + + // Get a value in the range [0, 1) in order to avoid + // overflowing into infinity when multiplying with scale + let value0_1 = value1_2 - 1.0; + + // Doing multiply before addition allows some architectures + // to use a single instruction. + let res = value0_1 * scale + low; + + debug_assert!(low.all_le(res) || !scale.all_finite()); + if res.all_lt(high) { + return res; + } + + // This handles a number of edge cases. + // * `low` or `high` is NaN. In this case `scale` and + // `res` are going to end up as NaN. + // * `low` is negative infinity and `high` is finite. + // `scale` is going to be infinite and `res` will be + // NaN. + // * `high` is positive infinity and `low` is finite. + // `scale` is going to be infinite and `res` will + // be infinite or NaN (if value0_1 is 0). + // * `low` is negative infinity and `high` is positive + // infinity. `scale` will be infinite and `res` will + // be NaN. + // * `low` and `high` are finite, but `high - low` + // overflows to infinite. `scale` will be infinite + // and `res` will be infinite or NaN (if value0_1 is 0). + // So if `high` or `low` are non-finite, we are guaranteed + // to fail the `res < high` check above and end up here. + // + // While we technically should check for non-finite `low` + // and `high` before entering the loop, by doing the checks + // here instead, we allow the common case to avoid these + // checks. But we are still guaranteed that if `low` or + // `high` are non-finite we'll end up here and can do the + // appropriate checks. + // + // Likewise `high - low` overflowing to infinity is also + // rare, so handle it here after the common case. + let mask = !scale.finite_mask(); + if mask.any() { + assert!( + low.all_finite() && high.all_finite(), + "Uniform::sample_single: low and high must be finite" + ); + scale = scale.decrease_masked(mask); + } + } + } + } + }; +} + +uniform_float_impl! { f32, u32, f32, u32, 32 - 23 } +uniform_float_impl! { f64, u64, f64, u64, 64 - 52 } + +#[cfg(feature = "simd_support")] +uniform_float_impl! { f32x2, u32x2, f32, u32, 32 - 23 } +#[cfg(feature = "simd_support")] +uniform_float_impl! { f32x4, u32x4, f32, u32, 32 - 23 } +#[cfg(feature = "simd_support")] +uniform_float_impl! { f32x8, u32x8, f32, u32, 32 - 23 } +#[cfg(feature = "simd_support")] +uniform_float_impl! { f32x16, u32x16, f32, u32, 32 - 23 } + +#[cfg(feature = "simd_support")] +uniform_float_impl! { f64x2, u64x2, f64, u64, 64 - 52 } +#[cfg(feature = "simd_support")] +uniform_float_impl! { f64x4, u64x4, f64, u64, 64 - 52 } +#[cfg(feature = "simd_support")] +uniform_float_impl! { f64x8, u64x8, f64, u64, 64 - 52 } + + +/// The back-end implementing [`UniformSampler`] for `Duration`. +/// +/// Unless you are implementing [`UniformSampler`] for your own types, this type +/// should not be used directly, use [`Uniform`] instead. +#[derive(Clone, Copy, Debug)] +pub struct UniformDuration { + mode: UniformDurationMode, + offset: u32, +} + +#[derive(Debug, Copy, Clone)] +enum UniformDurationMode { + Small { + secs: u64, + nanos: Uniform<u32>, + }, + Medium { + nanos: Uniform<u64>, + }, + Large { + max_secs: u64, + max_nanos: u32, + secs: Uniform<u64>, + }, +} + +impl SampleUniform for Duration { + type Sampler = UniformDuration; +} + +impl UniformSampler for UniformDuration { + type X = Duration; + + #[inline] + fn new<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!(low < high, "Uniform::new called with `low >= high`"); + UniformDuration::new_inclusive(low, high - Duration::new(0, 1)) + } + + #[inline] + fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + let low = *low_b.borrow(); + let high = *high_b.borrow(); + assert!( + low <= high, + "Uniform::new_inclusive called with `low > high`" + ); + + let low_s = low.as_secs(); + let low_n = low.subsec_nanos(); + let mut high_s = high.as_secs(); + let mut high_n = high.subsec_nanos(); + + if high_n < low_n { + high_s -= 1; + high_n += 1_000_000_000; + } + + let mode = if low_s == high_s { + UniformDurationMode::Small { + secs: low_s, + nanos: Uniform::new_inclusive(low_n, high_n), + } + } else { + let max = high_s + .checked_mul(1_000_000_000) + .and_then(|n| n.checked_add(u64::from(high_n))); + + if let Some(higher_bound) = max { + let lower_bound = low_s * 1_000_000_000 + u64::from(low_n); + UniformDurationMode::Medium { + nanos: Uniform::new_inclusive(lower_bound, higher_bound), + } + } else { + // An offset is applied to simplify generation of nanoseconds + let max_nanos = high_n - low_n; + UniformDurationMode::Large { + max_secs: high_s, + max_nanos, + secs: Uniform::new_inclusive(low_s, high_s), + } + } + }; + UniformDuration { + mode, + offset: low_n, + } + } + + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Duration { + match self.mode { + UniformDurationMode::Small { secs, nanos } => { + let n = nanos.sample(rng); + Duration::new(secs, n) + } + UniformDurationMode::Medium { nanos } => { + let nanos = nanos.sample(rng); + Duration::new(nanos / 1_000_000_000, (nanos % 1_000_000_000) as u32) + } + UniformDurationMode::Large { + max_secs, + max_nanos, + secs, + } => { + // constant folding means this is at least as fast as `gen_range` + let nano_range = Uniform::new(0, 1_000_000_000); + loop { + let s = secs.sample(rng); + let n = nano_range.sample(rng); + if !(s == max_secs && n > max_nanos) { + let sum = n + self.offset; + break Duration::new(s, sum); + } + } + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::rngs::mock::StepRng; + + #[should_panic] + #[test] + fn test_uniform_bad_limits_equal_int() { + Uniform::new(10, 10); + } + + #[test] + fn test_uniform_good_limits_equal_int() { + let mut rng = crate::test::rng(804); + let dist = Uniform::new_inclusive(10, 10); + for _ in 0..20 { + assert_eq!(rng.sample(dist), 10); + } + } + + #[should_panic] + #[test] + fn test_uniform_bad_limits_flipped_int() { + Uniform::new(10, 5); + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_integers() { + #[cfg(not(target_os = "emscripten"))] use core::{i128, u128}; + use core::{i16, i32, i64, i8, isize}; + use core::{u16, u32, u64, u8, usize}; + + let mut rng = crate::test::rng(251); + macro_rules! t { + ($ty:ident, $v:expr, $le:expr, $lt:expr) => {{ + for &(low, high) in $v.iter() { + let my_uniform = Uniform::new(low, high); + for _ in 0..1000 { + let v: $ty = rng.sample(my_uniform); + assert!($le(low, v) && $lt(v, high)); + } + + let my_uniform = Uniform::new_inclusive(low, high); + for _ in 0..1000 { + let v: $ty = rng.sample(my_uniform); + assert!($le(low, v) && $le(v, high)); + } + + let my_uniform = Uniform::new(&low, high); + for _ in 0..1000 { + let v: $ty = rng.sample(my_uniform); + assert!($le(low, v) && $lt(v, high)); + } + + let my_uniform = Uniform::new_inclusive(&low, &high); + for _ in 0..1000 { + let v: $ty = rng.sample(my_uniform); + assert!($le(low, v) && $le(v, high)); + } + + for _ in 0..1000 { + let v: $ty = rng.gen_range(low, high); + assert!($le(low, v) && $lt(v, high)); + } + } + }}; + + // scalar bulk + ($($ty:ident),*) => {{ + $(t!( + $ty, + [(0, 10), (10, 127), ($ty::MIN, $ty::MAX)], + |x, y| x <= y, + |x, y| x < y + );)* + }}; + + // simd bulk + ($($ty:ident),* => $scalar:ident) => {{ + $(t!( + $ty, + [ + ($ty::splat(0), $ty::splat(10)), + ($ty::splat(10), $ty::splat(127)), + ($ty::splat($scalar::MIN), $ty::splat($scalar::MAX)), + ], + |x: $ty, y| x.le(y).all(), + |x: $ty, y| x.lt(y).all() + );)* + }}; + } + t!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize); + #[cfg(not(target_os = "emscripten"))] + t!(i128, u128); + + #[cfg(all(feature = "simd_support", feature = "nightly"))] + { + t!(u8x2, u8x4, u8x8, u8x16, u8x32, u8x64 => u8); + t!(i8x2, i8x4, i8x8, i8x16, i8x32, i8x64 => i8); + t!(u16x2, u16x4, u16x8, u16x16, u16x32 => u16); + t!(i16x2, i16x4, i16x8, i16x16, i16x32 => i16); + t!(u32x2, u32x4, u32x8, u32x16 => u32); + t!(i32x2, i32x4, i32x8, i32x16 => i32); + t!(u64x2, u64x4, u64x8 => u64); + t!(i64x2, i64x4, i64x8 => i64); + } + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_floats() { + let mut rng = crate::test::rng(252); + let mut zero_rng = StepRng::new(0, 0); + let mut max_rng = StepRng::new(0xffff_ffff_ffff_ffff, 0); + macro_rules! t { + ($ty:ty, $f_scalar:ident, $bits_shifted:expr) => {{ + let v: &[($f_scalar, $f_scalar)] = &[ + (0.0, 100.0), + (-1e35, -1e25), + (1e-35, 1e-25), + (-1e35, 1e35), + (<$f_scalar>::from_bits(0), <$f_scalar>::from_bits(3)), + (-<$f_scalar>::from_bits(10), -<$f_scalar>::from_bits(1)), + (-<$f_scalar>::from_bits(5), 0.0), + (-<$f_scalar>::from_bits(7), -0.0), + (10.0, ::core::$f_scalar::MAX), + (-100.0, ::core::$f_scalar::MAX), + (-::core::$f_scalar::MAX / 5.0, ::core::$f_scalar::MAX), + (-::core::$f_scalar::MAX, ::core::$f_scalar::MAX / 5.0), + (-::core::$f_scalar::MAX * 0.8, ::core::$f_scalar::MAX * 0.7), + (-::core::$f_scalar::MAX, ::core::$f_scalar::MAX), + ]; + for &(low_scalar, high_scalar) in v.iter() { + for lane in 0..<$ty>::lanes() { + let low = <$ty>::splat(0.0 as $f_scalar).replace(lane, low_scalar); + let high = <$ty>::splat(1.0 as $f_scalar).replace(lane, high_scalar); + let my_uniform = Uniform::new(low, high); + let my_incl_uniform = Uniform::new_inclusive(low, high); + for _ in 0..100 { + let v = rng.sample(my_uniform).extract(lane); + assert!(low_scalar <= v && v < high_scalar); + let v = rng.sample(my_incl_uniform).extract(lane); + assert!(low_scalar <= v && v <= high_scalar); + let v = rng.gen_range(low, high).extract(lane); + assert!(low_scalar <= v && v < high_scalar); + } + + assert_eq!( + rng.sample(Uniform::new_inclusive(low, low)).extract(lane), + low_scalar + ); + + assert_eq!(zero_rng.sample(my_uniform).extract(lane), low_scalar); + assert_eq!(zero_rng.sample(my_incl_uniform).extract(lane), low_scalar); + assert_eq!(zero_rng.gen_range(low, high).extract(lane), low_scalar); + assert!(max_rng.sample(my_uniform).extract(lane) < high_scalar); + assert!(max_rng.sample(my_incl_uniform).extract(lane) <= high_scalar); + + // Don't run this test for really tiny differences between high and low + // since for those rounding might result in selecting high for a very + // long time. + if (high_scalar - low_scalar) > 0.0001 { + let mut lowering_max_rng = StepRng::new( + 0xffff_ffff_ffff_ffff, + (-1i64 << $bits_shifted) as u64, + ); + assert!( + lowering_max_rng.gen_range(low, high).extract(lane) < high_scalar + ); + } + } + } + + assert_eq!( + rng.sample(Uniform::new_inclusive( + ::core::$f_scalar::MAX, + ::core::$f_scalar::MAX + )), + ::core::$f_scalar::MAX + ); + assert_eq!( + rng.sample(Uniform::new_inclusive( + -::core::$f_scalar::MAX, + -::core::$f_scalar::MAX + )), + -::core::$f_scalar::MAX + ); + }}; + } + + t!(f32, f32, 32 - 23); + t!(f64, f64, 64 - 52); + #[cfg(feature = "simd_support")] + { + t!(f32x2, f32, 32 - 23); + t!(f32x4, f32, 32 - 23); + t!(f32x8, f32, 32 - 23); + t!(f32x16, f32, 32 - 23); + t!(f64x2, f64, 64 - 52); + t!(f64x4, f64, 64 - 52); + t!(f64x8, f64, 64 - 52); + } + } + + #[test] + #[cfg(all( + feature = "std", + not(target_arch = "wasm32"), + not(target_arch = "asmjs") + ))] + fn test_float_assertions() { + use super::SampleUniform; + use std::panic::catch_unwind; + fn range<T: SampleUniform>(low: T, high: T) { + let mut rng = crate::test::rng(253); + rng.gen_range(low, high); + } + + macro_rules! t { + ($ty:ident, $f_scalar:ident) => {{ + let v: &[($f_scalar, $f_scalar)] = &[ + (::std::$f_scalar::NAN, 0.0), + (1.0, ::std::$f_scalar::NAN), + (::std::$f_scalar::NAN, ::std::$f_scalar::NAN), + (1.0, 0.5), + (::std::$f_scalar::MAX, -::std::$f_scalar::MAX), + (::std::$f_scalar::INFINITY, ::std::$f_scalar::INFINITY), + ( + ::std::$f_scalar::NEG_INFINITY, + ::std::$f_scalar::NEG_INFINITY, + ), + (::std::$f_scalar::NEG_INFINITY, 5.0), + (5.0, ::std::$f_scalar::INFINITY), + (::std::$f_scalar::NAN, ::std::$f_scalar::INFINITY), + (::std::$f_scalar::NEG_INFINITY, ::std::$f_scalar::NAN), + (::std::$f_scalar::NEG_INFINITY, ::std::$f_scalar::INFINITY), + ]; + for &(low_scalar, high_scalar) in v.iter() { + for lane in 0..<$ty>::lanes() { + let low = <$ty>::splat(0.0 as $f_scalar).replace(lane, low_scalar); + let high = <$ty>::splat(1.0 as $f_scalar).replace(lane, high_scalar); + assert!(catch_unwind(|| range(low, high)).is_err()); + assert!(catch_unwind(|| Uniform::new(low, high)).is_err()); + assert!(catch_unwind(|| Uniform::new_inclusive(low, high)).is_err()); + assert!(catch_unwind(|| range(low, low)).is_err()); + assert!(catch_unwind(|| Uniform::new(low, low)).is_err()); + } + } + }}; + } + + t!(f32, f32); + t!(f64, f64); + #[cfg(feature = "simd_support")] + { + t!(f32x2, f32); + t!(f32x4, f32); + t!(f32x8, f32); + t!(f32x16, f32); + t!(f64x2, f64); + t!(f64x4, f64); + t!(f64x8, f64); + } + } + + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_durations() { + #[cfg(not(feature = "std"))] use core::time::Duration; + #[cfg(feature = "std")] use std::time::Duration; + + let mut rng = crate::test::rng(253); + + let v = &[ + (Duration::new(10, 50000), Duration::new(100, 1234)), + (Duration::new(0, 100), Duration::new(1, 50)), + ( + Duration::new(0, 0), + Duration::new(u64::max_value(), 999_999_999), + ), + ]; + for &(low, high) in v.iter() { + let my_uniform = Uniform::new(low, high); + for _ in 0..1000 { + let v = rng.sample(my_uniform); + assert!(low <= v && v < high); + } + } + } + + #[test] + fn test_custom_uniform() { + use crate::distributions::uniform::{ + SampleBorrow, SampleUniform, UniformFloat, UniformSampler, + }; + #[derive(Clone, Copy, PartialEq, PartialOrd)] + struct MyF32 { + x: f32, + } + #[derive(Clone, Copy, Debug)] + struct UniformMyF32(UniformFloat<f32>); + impl UniformSampler for UniformMyF32 { + type X = MyF32; + + fn new<B1, B2>(low: B1, high: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + UniformMyF32(UniformFloat::<f32>::new(low.borrow().x, high.borrow().x)) + } + + fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self + where + B1: SampleBorrow<Self::X> + Sized, + B2: SampleBorrow<Self::X> + Sized, + { + UniformSampler::new(low, high) + } + + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X { + MyF32 { + x: self.0.sample(rng), + } + } + } + impl SampleUniform for MyF32 { + type Sampler = UniformMyF32; + } + + let (low, high) = (MyF32 { x: 17.0f32 }, MyF32 { x: 22.0f32 }); + let uniform = Uniform::new(low, high); + let mut rng = crate::test::rng(804); + for _ in 0..100 { + let x: MyF32 = rng.sample(uniform); + assert!(low <= x && x < high); + } + } + + #[test] + fn test_uniform_from_std_range() { + let r = Uniform::from(2u32..7); + assert_eq!(r.0.low, 2); + assert_eq!(r.0.range, 5); + let r = Uniform::from(2.0f64..7.0); + assert_eq!(r.0.low, 2.0); + assert_eq!(r.0.scale, 5.0); + } + + #[test] + fn test_uniform_from_std_range_inclusive() { + let r = Uniform::from(2u32..=6); + assert_eq!(r.0.low, 2); + assert_eq!(r.0.range, 5); + let r = Uniform::from(2.0f64..=7.0); + assert_eq!(r.0.low, 2.0); + assert!(r.0.scale > 5.0); + assert!(r.0.scale < 5.0 + 1e-14); + } + + #[test] + fn value_stability() { + fn test_samples<T: SampleUniform + Copy + core::fmt::Debug + PartialEq>( + lb: T, ub: T, expected_single: &[T], expected_multiple: &[T], + ) where Uniform<T>: Distribution<T> { + let mut rng = crate::test::rng(897); + let mut buf = [lb; 3]; + + for x in &mut buf { + *x = T::Sampler::sample_single(lb, ub, &mut rng); + } + assert_eq!(&buf, expected_single); + + let distr = Uniform::new(lb, ub); + for x in &mut buf { + *x = rng.sample(&distr); + } + assert_eq!(&buf, expected_multiple); + } + + // We test on a sub-set of types; possibly we should do more. + // TODO: SIMD types + + test_samples(11u8, 219, &[17, 66, 214], &[181, 93, 165]); + test_samples(11u32, 219, &[17, 66, 214], &[181, 93, 165]); + + test_samples(0f32, 1e-2f32, &[0.0003070104, 0.0026630748, 0.00979833], &[ + 0.008194133, + 0.00398172, + 0.007428536, + ]); + test_samples( + -1e10f64, + 1e10f64, + &[-4673848682.871551, 6388267422.932352, 4857075081.198343], + &[1173375212.1808167, 1917642852.109581, 2365076174.3153973], + ); + + test_samples( + Duration::new(2, 0), + Duration::new(4, 0), + &[ + Duration::new(2, 532615131), + Duration::new(3, 638826742), + Duration::new(3, 485707508), + ], + &[ + Duration::new(3, 117337521), + Duration::new(3, 191764285), + Duration::new(3, 236507617), + ], + ); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/unit_circle.rs b/vendor/rand-0.7.3/src/distributions/unit_circle.rs new file mode 100644 index 000000000..37885d8eb --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/unit_circle.rs @@ -0,0 +1,102 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![allow(deprecated)] +#![allow(clippy::all)] + +use crate::distributions::{Distribution, Uniform}; +use crate::Rng; + +/// Samples uniformly from the edge of the unit circle in two dimensions. +/// +/// Implemented via a method by von Neumann[^1]. +/// +/// [^1]: von Neumann, J. (1951) [*Various Techniques Used in Connection with +/// Random Digits.*](https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf) +/// NBS Appl. Math. Ser., No. 12. Washington, DC: U.S. Government Printing +/// Office, pp. 36-38. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct UnitCircle; + +impl UnitCircle { + /// Construct a new `UnitCircle` distribution. + #[inline] + pub fn new() -> UnitCircle { + UnitCircle + } +} + +impl Distribution<[f64; 2]> for UnitCircle { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> [f64; 2] { + let uniform = Uniform::new(-1., 1.); + let mut x1; + let mut x2; + let mut sum; + loop { + x1 = uniform.sample(rng); + x2 = uniform.sample(rng); + sum = x1 * x1 + x2 * x2; + if sum < 1. { + break; + } + } + let diff = x1 * x1 - x2 * x2; + [diff / sum, 2. * x1 * x2 / sum] + } +} + +#[cfg(test)] +mod tests { + use super::UnitCircle; + use crate::distributions::Distribution; + + /// Assert that two numbers are almost equal to each other. + /// + /// On panic, this macro will print the values of the expressions with their + /// debug representations. + macro_rules! assert_almost_eq { + ($a:expr, $b:expr, $prec:expr) => { + let diff = ($a - $b).abs(); + if diff > $prec { + panic!(format!( + "assertion failed: `abs(left - right) = {:.1e} < {:e}`, \ + (left: `{}`, right: `{}`)", + diff, $prec, $a, $b + )); + } + }; + } + + #[test] + fn norm() { + let mut rng = crate::test::rng(1); + let dist = UnitCircle::new(); + for _ in 0..1000 { + let x = dist.sample(&mut rng); + assert_almost_eq!(x[0] * x[0] + x[1] * x[1], 1., 1e-15); + } + } + + #[test] + fn value_stability() { + let mut rng = crate::test::rng(2); + let expected = [ + [-0.9965658683520504, -0.08280380447614634], + [-0.9790853270389644, -0.20345004884984505], + [-0.8449189758898707, 0.5348943112253227], + ]; + let samples = [ + UnitCircle.sample(&mut rng), + UnitCircle.sample(&mut rng), + UnitCircle.sample(&mut rng), + ]; + assert_eq!(samples, expected); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/unit_sphere.rs b/vendor/rand-0.7.3/src/distributions/unit_sphere.rs new file mode 100644 index 000000000..5b8c8ad55 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/unit_sphere.rs @@ -0,0 +1,97 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![allow(deprecated)] +#![allow(clippy::all)] + +use crate::distributions::{Distribution, Uniform}; +use crate::Rng; + +/// Samples uniformly from the surface of the unit sphere in three dimensions. +/// +/// Implemented via a method by Marsaglia[^1]. +/// +/// [^1]: Marsaglia, George (1972). [*Choosing a Point from the Surface of a +/// Sphere.*](https://doi.org/10.1214/aoms/1177692644) +/// Ann. Math. Statist. 43, no. 2, 645--646. +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct UnitSphereSurface; + +impl UnitSphereSurface { + /// Construct a new `UnitSphereSurface` distribution. + #[inline] + pub fn new() -> UnitSphereSurface { + UnitSphereSurface + } +} + +impl Distribution<[f64; 3]> for UnitSphereSurface { + #[inline] + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> [f64; 3] { + let uniform = Uniform::new(-1., 1.); + loop { + let (x1, x2) = (uniform.sample(rng), uniform.sample(rng)); + let sum = x1 * x1 + x2 * x2; + if sum >= 1. { + continue; + } + let factor = 2. * (1.0_f64 - sum).sqrt(); + return [x1 * factor, x2 * factor, 1. - 2. * sum]; + } + } +} + +#[cfg(test)] +mod tests { + use super::UnitSphereSurface; + use crate::distributions::Distribution; + + /// Assert that two numbers are almost equal to each other. + /// + /// On panic, this macro will print the values of the expressions with their + /// debug representations. + macro_rules! assert_almost_eq { + ($a:expr, $b:expr, $prec:expr) => { + let diff = ($a - $b).abs(); + if diff > $prec { + panic!(format!( + "assertion failed: `abs(left - right) = {:.1e} < {:e}`, \ + (left: `{}`, right: `{}`)", + diff, $prec, $a, $b + )); + } + }; + } + + #[test] + fn norm() { + let mut rng = crate::test::rng(1); + let dist = UnitSphereSurface::new(); + for _ in 0..1000 { + let x = dist.sample(&mut rng); + assert_almost_eq!(x[0] * x[0] + x[1] * x[1] + x[2] * x[2], 1., 1e-15); + } + } + + #[test] + fn value_stability() { + let mut rng = crate::test::rng(2); + let expected = [ + [0.03247542860231647, -0.7830477442152738, 0.6211131755296027], + [-0.09978440840914075, 0.9706650829833128, -0.21875184231323952], + [0.2735582468624679, 0.9435374242279655, -0.1868234852870203], + ]; + let samples = [ + UnitSphereSurface.sample(&mut rng), + UnitSphereSurface.sample(&mut rng), + UnitSphereSurface.sample(&mut rng), + ]; + assert_eq!(samples, expected); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/utils.rs b/vendor/rand-0.7.3/src/distributions/utils.rs new file mode 100644 index 000000000..2d36b0226 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/utils.rs @@ -0,0 +1,547 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Math helper functions + +#[cfg(feature = "std")] use crate::distributions::ziggurat_tables; +#[cfg(feature = "std")] use crate::Rng; +#[cfg(feature = "simd_support")] use packed_simd::*; + + +pub trait WideningMultiply<RHS = Self> { + type Output; + + fn wmul(self, x: RHS) -> Self::Output; +} + +macro_rules! wmul_impl { + ($ty:ty, $wide:ty, $shift:expr) => { + impl WideningMultiply for $ty { + type Output = ($ty, $ty); + + #[inline(always)] + fn wmul(self, x: $ty) -> Self::Output { + let tmp = (self as $wide) * (x as $wide); + ((tmp >> $shift) as $ty, tmp as $ty) + } + } + }; + + // simd bulk implementation + ($(($ty:ident, $wide:ident),)+, $shift:expr) => { + $( + impl WideningMultiply for $ty { + type Output = ($ty, $ty); + + #[inline(always)] + fn wmul(self, x: $ty) -> Self::Output { + // For supported vectors, this should compile to a couple + // supported multiply & swizzle instructions (no actual + // casting). + // TODO: optimize + let y: $wide = self.cast(); + let x: $wide = x.cast(); + let tmp = y * x; + let hi: $ty = (tmp >> $shift).cast(); + let lo: $ty = tmp.cast(); + (hi, lo) + } + } + )+ + }; +} +wmul_impl! { u8, u16, 8 } +wmul_impl! { u16, u32, 16 } +wmul_impl! { u32, u64, 32 } +#[cfg(not(target_os = "emscripten"))] +wmul_impl! { u64, u128, 64 } + +// This code is a translation of the __mulddi3 function in LLVM's +// compiler-rt. It is an optimised variant of the common method +// `(a + b) * (c + d) = ac + ad + bc + bd`. +// +// For some reason LLVM can optimise the C version very well, but +// keeps shuffling registers in this Rust translation. +macro_rules! wmul_impl_large { + ($ty:ty, $half:expr) => { + impl WideningMultiply for $ty { + type Output = ($ty, $ty); + + #[inline(always)] + fn wmul(self, b: $ty) -> Self::Output { + const LOWER_MASK: $ty = !0 >> $half; + let mut low = (self & LOWER_MASK).wrapping_mul(b & LOWER_MASK); + let mut t = low >> $half; + low &= LOWER_MASK; + t += (self >> $half).wrapping_mul(b & LOWER_MASK); + low += (t & LOWER_MASK) << $half; + let mut high = t >> $half; + t = low >> $half; + low &= LOWER_MASK; + t += (b >> $half).wrapping_mul(self & LOWER_MASK); + low += (t & LOWER_MASK) << $half; + high += t >> $half; + high += (self >> $half).wrapping_mul(b >> $half); + + (high, low) + } + } + }; + + // simd bulk implementation + (($($ty:ty,)+) $scalar:ty, $half:expr) => { + $( + impl WideningMultiply for $ty { + type Output = ($ty, $ty); + + #[inline(always)] + fn wmul(self, b: $ty) -> Self::Output { + // needs wrapping multiplication + const LOWER_MASK: $scalar = !0 >> $half; + let mut low = (self & LOWER_MASK) * (b & LOWER_MASK); + let mut t = low >> $half; + low &= LOWER_MASK; + t += (self >> $half) * (b & LOWER_MASK); + low += (t & LOWER_MASK) << $half; + let mut high = t >> $half; + t = low >> $half; + low &= LOWER_MASK; + t += (b >> $half) * (self & LOWER_MASK); + low += (t & LOWER_MASK) << $half; + high += t >> $half; + high += (self >> $half) * (b >> $half); + + (high, low) + } + } + )+ + }; +} +#[cfg(target_os = "emscripten")] +wmul_impl_large! { u64, 32 } +#[cfg(not(target_os = "emscripten"))] +wmul_impl_large! { u128, 64 } + +macro_rules! wmul_impl_usize { + ($ty:ty) => { + impl WideningMultiply for usize { + type Output = (usize, usize); + + #[inline(always)] + fn wmul(self, x: usize) -> Self::Output { + let (high, low) = (self as $ty).wmul(x as $ty); + (high as usize, low as usize) + } + } + }; +} +#[cfg(target_pointer_width = "32")] +wmul_impl_usize! { u32 } +#[cfg(target_pointer_width = "64")] +wmul_impl_usize! { u64 } + +#[cfg(all(feature = "simd_support", feature = "nightly"))] +mod simd_wmul { + use super::*; + #[cfg(target_arch = "x86")] use core::arch::x86::*; + #[cfg(target_arch = "x86_64")] use core::arch::x86_64::*; + + wmul_impl! { + (u8x2, u16x2), + (u8x4, u16x4), + (u8x8, u16x8), + (u8x16, u16x16), + (u8x32, u16x32),, + 8 + } + + wmul_impl! { (u16x2, u32x2),, 16 } + #[cfg(not(target_feature = "sse2"))] + wmul_impl! { (u16x4, u32x4),, 16 } + #[cfg(not(target_feature = "sse4.2"))] + wmul_impl! { (u16x8, u32x8),, 16 } + #[cfg(not(target_feature = "avx2"))] + wmul_impl! { (u16x16, u32x16),, 16 } + + // 16-bit lane widths allow use of the x86 `mulhi` instructions, which + // means `wmul` can be implemented with only two instructions. + #[allow(unused_macros)] + macro_rules! wmul_impl_16 { + ($ty:ident, $intrinsic:ident, $mulhi:ident, $mullo:ident) => { + impl WideningMultiply for $ty { + type Output = ($ty, $ty); + + #[inline(always)] + fn wmul(self, x: $ty) -> Self::Output { + let b = $intrinsic::from_bits(x); + let a = $intrinsic::from_bits(self); + let hi = $ty::from_bits(unsafe { $mulhi(a, b) }); + let lo = $ty::from_bits(unsafe { $mullo(a, b) }); + (hi, lo) + } + } + }; + } + + #[cfg(target_feature = "sse2")] + wmul_impl_16! { u16x4, __m64, _mm_mulhi_pu16, _mm_mullo_pi16 } + #[cfg(target_feature = "sse4.2")] + wmul_impl_16! { u16x8, __m128i, _mm_mulhi_epu16, _mm_mullo_epi16 } + #[cfg(target_feature = "avx2")] + wmul_impl_16! { u16x16, __m256i, _mm256_mulhi_epu16, _mm256_mullo_epi16 } + // FIXME: there are no `__m512i` types in stdsimd yet, so `wmul::<u16x32>` + // cannot use the same implementation. + + wmul_impl! { + (u32x2, u64x2), + (u32x4, u64x4), + (u32x8, u64x8),, + 32 + } + + // TODO: optimize, this seems to seriously slow things down + wmul_impl_large! { (u8x64,) u8, 4 } + wmul_impl_large! { (u16x32,) u16, 8 } + wmul_impl_large! { (u32x16,) u32, 16 } + wmul_impl_large! { (u64x2, u64x4, u64x8,) u64, 32 } +} +#[cfg(all(feature = "simd_support", feature = "nightly"))] +pub use self::simd_wmul::*; + + +/// Helper trait when dealing with scalar and SIMD floating point types. +pub(crate) trait FloatSIMDUtils { + // `PartialOrd` for vectors compares lexicographically. We want to compare all + // the individual SIMD lanes instead, and get the combined result over all + // lanes. This is possible using something like `a.lt(b).all()`, but we + // implement it as a trait so we can write the same code for `f32` and `f64`. + // Only the comparison functions we need are implemented. + fn all_lt(self, other: Self) -> bool; + fn all_le(self, other: Self) -> bool; + fn all_finite(self) -> bool; + + type Mask; + fn finite_mask(self) -> Self::Mask; + fn gt_mask(self, other: Self) -> Self::Mask; + fn ge_mask(self, other: Self) -> Self::Mask; + + // Decrease all lanes where the mask is `true` to the next lower value + // representable by the floating-point type. At least one of the lanes + // must be set. + fn decrease_masked(self, mask: Self::Mask) -> Self; + + // Convert from int value. Conversion is done while retaining the numerical + // value, not by retaining the binary representation. + type UInt; + fn cast_from_int(i: Self::UInt) -> Self; +} + +/// Implement functions available in std builds but missing from core primitives +#[cfg(not(std))] +pub(crate) trait Float: Sized { + fn is_nan(self) -> bool; + fn is_infinite(self) -> bool; + fn is_finite(self) -> bool; +} + +/// Implement functions on f32/f64 to give them APIs similar to SIMD types +pub(crate) trait FloatAsSIMD: Sized { + #[inline(always)] + fn lanes() -> usize { + 1 + } + #[inline(always)] + fn splat(scalar: Self) -> Self { + scalar + } + #[inline(always)] + fn extract(self, index: usize) -> Self { + debug_assert_eq!(index, 0); + self + } + #[inline(always)] + fn replace(self, index: usize, new_value: Self) -> Self { + debug_assert_eq!(index, 0); + new_value + } +} + +pub(crate) trait BoolAsSIMD: Sized { + fn any(self) -> bool; + fn all(self) -> bool; + fn none(self) -> bool; +} + +impl BoolAsSIMD for bool { + #[inline(always)] + fn any(self) -> bool { + self + } + + #[inline(always)] + fn all(self) -> bool { + self + } + + #[inline(always)] + fn none(self) -> bool { + !self + } +} + +macro_rules! scalar_float_impl { + ($ty:ident, $uty:ident) => { + #[cfg(not(std))] + impl Float for $ty { + #[inline] + fn is_nan(self) -> bool { + self != self + } + + #[inline] + fn is_infinite(self) -> bool { + self == ::core::$ty::INFINITY || self == ::core::$ty::NEG_INFINITY + } + + #[inline] + fn is_finite(self) -> bool { + !(self.is_nan() || self.is_infinite()) + } + } + + impl FloatSIMDUtils for $ty { + type Mask = bool; + type UInt = $uty; + + #[inline(always)] + fn all_lt(self, other: Self) -> bool { + self < other + } + + #[inline(always)] + fn all_le(self, other: Self) -> bool { + self <= other + } + + #[inline(always)] + fn all_finite(self) -> bool { + self.is_finite() + } + + #[inline(always)] + fn finite_mask(self) -> Self::Mask { + self.is_finite() + } + + #[inline(always)] + fn gt_mask(self, other: Self) -> Self::Mask { + self > other + } + + #[inline(always)] + fn ge_mask(self, other: Self) -> Self::Mask { + self >= other + } + + #[inline(always)] + fn decrease_masked(self, mask: Self::Mask) -> Self { + debug_assert!(mask, "At least one lane must be set"); + <$ty>::from_bits(self.to_bits() - 1) + } + + #[inline] + fn cast_from_int(i: Self::UInt) -> Self { + i as $ty + } + } + + impl FloatAsSIMD for $ty {} + }; +} + +scalar_float_impl!(f32, u32); +scalar_float_impl!(f64, u64); + + +#[cfg(feature = "simd_support")] +macro_rules! simd_impl { + ($ty:ident, $f_scalar:ident, $mty:ident, $uty:ident) => { + impl FloatSIMDUtils for $ty { + type Mask = $mty; + type UInt = $uty; + + #[inline(always)] + fn all_lt(self, other: Self) -> bool { + self.lt(other).all() + } + + #[inline(always)] + fn all_le(self, other: Self) -> bool { + self.le(other).all() + } + + #[inline(always)] + fn all_finite(self) -> bool { + self.finite_mask().all() + } + + #[inline(always)] + fn finite_mask(self) -> Self::Mask { + // This can possibly be done faster by checking bit patterns + let neg_inf = $ty::splat(::core::$f_scalar::NEG_INFINITY); + let pos_inf = $ty::splat(::core::$f_scalar::INFINITY); + self.gt(neg_inf) & self.lt(pos_inf) + } + + #[inline(always)] + fn gt_mask(self, other: Self) -> Self::Mask { + self.gt(other) + } + + #[inline(always)] + fn ge_mask(self, other: Self) -> Self::Mask { + self.ge(other) + } + + #[inline(always)] + fn decrease_masked(self, mask: Self::Mask) -> Self { + // Casting a mask into ints will produce all bits set for + // true, and 0 for false. Adding that to the binary + // representation of a float means subtracting one from + // the binary representation, resulting in the next lower + // value representable by $ty. This works even when the + // current value is infinity. + debug_assert!(mask.any(), "At least one lane must be set"); + <$ty>::from_bits(<$uty>::from_bits(self) + <$uty>::from_bits(mask)) + } + + #[inline] + fn cast_from_int(i: Self::UInt) -> Self { + i.cast() + } + } + }; +} + +#[cfg(feature="simd_support")] simd_impl! { f32x2, f32, m32x2, u32x2 } +#[cfg(feature="simd_support")] simd_impl! { f32x4, f32, m32x4, u32x4 } +#[cfg(feature="simd_support")] simd_impl! { f32x8, f32, m32x8, u32x8 } +#[cfg(feature="simd_support")] simd_impl! { f32x16, f32, m32x16, u32x16 } +#[cfg(feature="simd_support")] simd_impl! { f64x2, f64, m64x2, u64x2 } +#[cfg(feature="simd_support")] simd_impl! { f64x4, f64, m64x4, u64x4 } +#[cfg(feature="simd_support")] simd_impl! { f64x8, f64, m64x8, u64x8 } + +/// Calculates ln(gamma(x)) (natural logarithm of the gamma +/// function) using the Lanczos approximation. +/// +/// The approximation expresses the gamma function as: +/// `gamma(z+1) = sqrt(2*pi)*(z+g+0.5)^(z+0.5)*exp(-z-g-0.5)*Ag(z)` +/// `g` is an arbitrary constant; we use the approximation with `g=5`. +/// +/// Noting that `gamma(z+1) = z*gamma(z)` and applying `ln` to both sides: +/// `ln(gamma(z)) = (z+0.5)*ln(z+g+0.5)-(z+g+0.5) + ln(sqrt(2*pi)*Ag(z)/z)` +/// +/// `Ag(z)` is an infinite series with coefficients that can be calculated +/// ahead of time - we use just the first 6 terms, which is good enough +/// for most purposes. +#[cfg(feature = "std")] +pub fn log_gamma(x: f64) -> f64 { + // precalculated 6 coefficients for the first 6 terms of the series + let coefficients: [f64; 6] = [ + 76.18009172947146, + -86.50532032941677, + 24.01409824083091, + -1.231739572450155, + 0.1208650973866179e-2, + -0.5395239384953e-5, + ]; + + // (x+0.5)*ln(x+g+0.5)-(x+g+0.5) + let tmp = x + 5.5; + let log = (x + 0.5) * tmp.ln() - tmp; + + // the first few terms of the series for Ag(x) + let mut a = 1.000000000190015; + let mut denom = x; + for coeff in &coefficients { + denom += 1.0; + a += coeff / denom; + } + + // get everything together + // a is Ag(x) + // 2.5066... is sqrt(2pi) + log + (2.5066282746310005 * a / x).ln() +} + +/// Sample a random number using the Ziggurat method (specifically the +/// ZIGNOR variant from Doornik 2005). Most of the arguments are +/// directly from the paper: +/// +/// * `rng`: source of randomness +/// * `symmetric`: whether this is a symmetric distribution, or one-sided with P(x < 0) = 0. +/// * `X`: the $x_i$ abscissae. +/// * `F`: precomputed values of the PDF at the $x_i$, (i.e. $f(x_i)$) +/// * `F_DIFF`: precomputed values of $f(x_i) - f(x_{i+1})$ +/// * `pdf`: the probability density function +/// * `zero_case`: manual sampling from the tail when we chose the +/// bottom box (i.e. i == 0) + +// the perf improvement (25-50%) is definitely worth the extra code +// size from force-inlining. +#[cfg(feature = "std")] +#[inline(always)] +pub fn ziggurat<R: Rng + ?Sized, P, Z>( + rng: &mut R, + symmetric: bool, + x_tab: ziggurat_tables::ZigTable, + f_tab: ziggurat_tables::ZigTable, + mut pdf: P, + mut zero_case: Z +) -> f64 +where + P: FnMut(f64) -> f64, + Z: FnMut(&mut R, f64) -> f64, +{ + use crate::distributions::float::IntoFloat; + loop { + // As an optimisation we re-implement the conversion to a f64. + // From the remaining 12 most significant bits we use 8 to construct `i`. + // This saves us generating a whole extra random number, while the added + // precision of using 64 bits for f64 does not buy us much. + let bits = rng.next_u64(); + let i = bits as usize & 0xff; + + let u = if symmetric { + // Convert to a value in the range [2,4) and substract to get [-1,1) + // We can't convert to an open range directly, that would require + // substracting `3.0 - EPSILON`, which is not representable. + // It is possible with an extra step, but an open range does not + // seem neccesary for the ziggurat algorithm anyway. + (bits >> 12).into_float_with_exponent(1) - 3.0 + } else { + // Convert to a value in the range [1,2) and substract to get (0,1) + (bits >> 12).into_float_with_exponent(0) - (1.0 - ::core::f64::EPSILON / 2.0) + }; + let x = u * x_tab[i]; + + let test_x = if symmetric { x.abs() } else { x }; + + // algebraically equivalent to |u| < x_tab[i+1]/x_tab[i] (or u < x_tab[i+1]/x_tab[i]) + if test_x < x_tab[i + 1] { + return x; + } + if i == 0 { + return zero_case(rng, u); + } + // algebraically equivalent to f1 + DRanU()*(f0 - f1) < 1 + if f_tab[i + 1] + (f_tab[i] - f_tab[i + 1]) * rng.gen::<f64>() < pdf(x) { + return x; + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/weibull.rs b/vendor/rand-0.7.3/src/distributions/weibull.rs new file mode 100644 index 000000000..ffbc93b01 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/weibull.rs @@ -0,0 +1,67 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! The Weibull distribution. +#![allow(deprecated)] + +use crate::distributions::{Distribution, OpenClosed01}; +use crate::Rng; + +/// Samples floating-point numbers according to the Weibull distribution +#[deprecated(since = "0.7.0", note = "moved to rand_distr crate")] +#[derive(Clone, Copy, Debug)] +pub struct Weibull { + inv_shape: f64, + scale: f64, +} + +impl Weibull { + /// Construct a new `Weibull` distribution with given `scale` and `shape`. + /// + /// # Panics + /// + /// `scale` and `shape` have to be non-zero and positive. + pub fn new(scale: f64, shape: f64) -> Weibull { + assert!((scale > 0.) & (shape > 0.)); + Weibull { + inv_shape: 1. / shape, + scale, + } + } +} + +impl Distribution<f64> for Weibull { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> f64 { + let x: f64 = rng.sample(OpenClosed01); + self.scale * (-x.ln()).powf(self.inv_shape) + } +} + +#[cfg(test)] +mod tests { + use super::Weibull; + use crate::distributions::Distribution; + + #[test] + #[should_panic] + fn invalid() { + Weibull::new(0., 0.); + } + + #[test] + fn sample() { + let scale = 1.0; + let shape = 2.0; + let d = Weibull::new(scale, shape); + let mut rng = crate::test::rng(1); + for _ in 0..1000 { + let r = d.sample(&mut rng); + assert!(r >= 0.); + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/weighted/alias_method.rs b/vendor/rand-0.7.3/src/distributions/weighted/alias_method.rs new file mode 100644 index 000000000..7d42a3526 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/weighted/alias_method.rs @@ -0,0 +1,517 @@ +//! This module contains an implementation of alias method for sampling random +//! indices with probabilities proportional to a collection of weights. + +use super::WeightedError; +#[cfg(not(feature = "std"))] use crate::alloc::vec; +#[cfg(not(feature = "std"))] use crate::alloc::vec::Vec; +use crate::distributions::uniform::SampleUniform; +use crate::distributions::Distribution; +use crate::distributions::Uniform; +use crate::Rng; +use core::fmt; +use core::iter::Sum; +use core::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign}; + +/// A distribution using weighted sampling to pick a discretely selected item. +/// +/// Sampling a [`WeightedIndex<W>`] distribution returns the index of a randomly +/// selected element from the vector used to create the [`WeightedIndex<W>`]. +/// The chance of a given element being picked is proportional to the value of +/// the element. The weights can have any type `W` for which a implementation of +/// [`Weight`] exists. +/// +/// # Performance +/// +/// Given that `n` is the number of items in the vector used to create an +/// [`WeightedIndex<W>`], [`WeightedIndex<W>`] will require `O(n)` amount of +/// memory. More specifically it takes up some constant amount of memory plus +/// the vector used to create it and a [`Vec<u32>`] with capacity `n`. +/// +/// Time complexity for the creation of a [`WeightedIndex<W>`] is `O(n)`. +/// Sampling is `O(1)`, it makes a call to [`Uniform<u32>::sample`] and a call +/// to [`Uniform<W>::sample`]. +/// +/// # Example +/// +/// ``` +/// use rand::distributions::weighted::alias_method::WeightedIndex; +/// use rand::prelude::*; +/// +/// let choices = vec!['a', 'b', 'c']; +/// let weights = vec![2, 1, 1]; +/// let dist = WeightedIndex::new(weights).unwrap(); +/// let mut rng = thread_rng(); +/// for _ in 0..100 { +/// // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c' +/// println!("{}", choices[dist.sample(&mut rng)]); +/// } +/// +/// let items = [('a', 0), ('b', 3), ('c', 7)]; +/// let dist2 = WeightedIndex::new(items.iter().map(|item| item.1).collect()).unwrap(); +/// for _ in 0..100 { +/// // 0% chance to print 'a', 30% chance to print 'b', 70% chance to print 'c' +/// println!("{}", items[dist2.sample(&mut rng)].0); +/// } +/// ``` +/// +/// [`WeightedIndex<W>`]: crate::distributions::weighted::alias_method::WeightedIndex +/// [`Weight`]: crate::distributions::weighted::alias_method::Weight +/// [`Vec<u32>`]: Vec +/// [`Uniform<u32>::sample`]: Distribution::sample +/// [`Uniform<W>::sample`]: Distribution::sample +pub struct WeightedIndex<W: Weight> { + aliases: Vec<u32>, + no_alias_odds: Vec<W>, + uniform_index: Uniform<u32>, + uniform_within_weight_sum: Uniform<W>, +} + +impl<W: Weight> WeightedIndex<W> { + /// Creates a new [`WeightedIndex`]. + /// + /// Returns an error if: + /// - The vector is empty. + /// - The vector is longer than `u32::MAX`. + /// - For any weight `w`: `w < 0` or `w > max` where `max = W::MAX / + /// weights.len()`. + /// - The sum of weights is zero. + pub fn new(weights: Vec<W>) -> Result<Self, WeightedError> { + let n = weights.len(); + if n == 0 { + return Err(WeightedError::NoItem); + } else if n > ::core::u32::MAX as usize { + return Err(WeightedError::TooMany); + } + let n = n as u32; + + let max_weight_size = W::try_from_u32_lossy(n) + .map(|n| W::MAX / n) + .unwrap_or(W::ZERO); + if !weights + .iter() + .all(|&w| W::ZERO <= w && w <= max_weight_size) + { + return Err(WeightedError::InvalidWeight); + } + + // The sum of weights will represent 100% of no alias odds. + let weight_sum = Weight::sum(weights.as_slice()); + // Prevent floating point overflow due to rounding errors. + let weight_sum = if weight_sum > W::MAX { + W::MAX + } else { + weight_sum + }; + if weight_sum == W::ZERO { + return Err(WeightedError::AllWeightsZero); + } + + // `weight_sum` would have been zero if `try_from_lossy` causes an error here. + let n_converted = W::try_from_u32_lossy(n).unwrap(); + + let mut no_alias_odds = weights; + for odds in no_alias_odds.iter_mut() { + *odds *= n_converted; + // Prevent floating point overflow due to rounding errors. + *odds = if *odds > W::MAX { W::MAX } else { *odds }; + } + + /// This struct is designed to contain three data structures at once, + /// sharing the same memory. More precisely it contains two linked lists + /// and an alias map, which will be the output of this method. To keep + /// the three data structures from getting in each other's way, it must + /// be ensured that a single index is only ever in one of them at the + /// same time. + struct Aliases { + aliases: Vec<u32>, + smalls_head: u32, + bigs_head: u32, + } + + impl Aliases { + fn new(size: u32) -> Self { + Aliases { + aliases: vec![0; size as usize], + smalls_head: ::core::u32::MAX, + bigs_head: ::core::u32::MAX, + } + } + + fn push_small(&mut self, idx: u32) { + self.aliases[idx as usize] = self.smalls_head; + self.smalls_head = idx; + } + + fn push_big(&mut self, idx: u32) { + self.aliases[idx as usize] = self.bigs_head; + self.bigs_head = idx; + } + + fn pop_small(&mut self) -> u32 { + let popped = self.smalls_head; + self.smalls_head = self.aliases[popped as usize]; + popped + } + + fn pop_big(&mut self) -> u32 { + let popped = self.bigs_head; + self.bigs_head = self.aliases[popped as usize]; + popped + } + + fn smalls_is_empty(&self) -> bool { + self.smalls_head == ::core::u32::MAX + } + + fn bigs_is_empty(&self) -> bool { + self.bigs_head == ::core::u32::MAX + } + + fn set_alias(&mut self, idx: u32, alias: u32) { + self.aliases[idx as usize] = alias; + } + } + + let mut aliases = Aliases::new(n); + + // Split indices into those with small weights and those with big weights. + for (index, &odds) in no_alias_odds.iter().enumerate() { + if odds < weight_sum { + aliases.push_small(index as u32); + } else { + aliases.push_big(index as u32); + } + } + + // Build the alias map by finding an alias with big weight for each index with + // small weight. + while !aliases.smalls_is_empty() && !aliases.bigs_is_empty() { + let s = aliases.pop_small(); + let b = aliases.pop_big(); + + aliases.set_alias(s, b); + no_alias_odds[b as usize] = + no_alias_odds[b as usize] - weight_sum + no_alias_odds[s as usize]; + + if no_alias_odds[b as usize] < weight_sum { + aliases.push_small(b); + } else { + aliases.push_big(b); + } + } + + // The remaining indices should have no alias odds of about 100%. This is due to + // numeric accuracy. Otherwise they would be exactly 100%. + while !aliases.smalls_is_empty() { + no_alias_odds[aliases.pop_small() as usize] = weight_sum; + } + while !aliases.bigs_is_empty() { + no_alias_odds[aliases.pop_big() as usize] = weight_sum; + } + + // Prepare distributions for sampling. Creating them beforehand improves + // sampling performance. + let uniform_index = Uniform::new(0, n); + let uniform_within_weight_sum = Uniform::new(W::ZERO, weight_sum); + + Ok(Self { + aliases: aliases.aliases, + no_alias_odds, + uniform_index, + uniform_within_weight_sum, + }) + } +} + +impl<W: Weight> Distribution<usize> for WeightedIndex<W> { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize { + let candidate = rng.sample(self.uniform_index); + if rng.sample(&self.uniform_within_weight_sum) < self.no_alias_odds[candidate as usize] { + candidate as usize + } else { + self.aliases[candidate as usize] as usize + } + } +} + +impl<W: Weight> fmt::Debug for WeightedIndex<W> +where + W: fmt::Debug, + Uniform<W>: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_struct("WeightedIndex") + .field("aliases", &self.aliases) + .field("no_alias_odds", &self.no_alias_odds) + .field("uniform_index", &self.uniform_index) + .field("uniform_within_weight_sum", &self.uniform_within_weight_sum) + .finish() + } +} + +impl<W: Weight> Clone for WeightedIndex<W> +where Uniform<W>: Clone +{ + fn clone(&self) -> Self { + Self { + aliases: self.aliases.clone(), + no_alias_odds: self.no_alias_odds.clone(), + uniform_index: self.uniform_index.clone(), + uniform_within_weight_sum: self.uniform_within_weight_sum.clone(), + } + } +} + +/// Trait that must be implemented for weights, that are used with +/// [`WeightedIndex`]. Currently no guarantees on the correctness of +/// [`WeightedIndex`] are given for custom implementations of this trait. +pub trait Weight: + Sized + + Copy + + SampleUniform + + PartialOrd + + Add<Output = Self> + + AddAssign + + Sub<Output = Self> + + SubAssign + + Mul<Output = Self> + + MulAssign + + Div<Output = Self> + + DivAssign + + Sum +{ + /// Maximum number representable by `Self`. + const MAX: Self; + + /// Element of `Self` equivalent to 0. + const ZERO: Self; + + /// Produce an instance of `Self` from a `u32` value, or return `None` if + /// out of range. Loss of precision (where `Self` is a floating point type) + /// is acceptable. + fn try_from_u32_lossy(n: u32) -> Option<Self>; + + /// Sums all values in slice `values`. + fn sum(values: &[Self]) -> Self { + values.iter().map(|x| *x).sum() + } +} + +macro_rules! impl_weight_for_float { + ($T: ident) => { + impl Weight for $T { + const MAX: Self = ::core::$T::MAX; + const ZERO: Self = 0.0; + + fn try_from_u32_lossy(n: u32) -> Option<Self> { + Some(n as $T) + } + + fn sum(values: &[Self]) -> Self { + pairwise_sum(values) + } + } + }; +} + +/// In comparison to naive accumulation, the pairwise sum algorithm reduces +/// rounding errors when there are many floating point values. +fn pairwise_sum<T: Weight>(values: &[T]) -> T { + if values.len() <= 32 { + values.iter().map(|x| *x).sum() + } else { + let mid = values.len() / 2; + let (a, b) = values.split_at(mid); + pairwise_sum(a) + pairwise_sum(b) + } +} + +macro_rules! impl_weight_for_int { + ($T: ident) => { + impl Weight for $T { + const MAX: Self = ::core::$T::MAX; + const ZERO: Self = 0; + + fn try_from_u32_lossy(n: u32) -> Option<Self> { + let n_converted = n as Self; + if n_converted >= Self::ZERO && n_converted as u32 == n { + Some(n_converted) + } else { + None + } + } + } + }; +} + +impl_weight_for_float!(f64); +impl_weight_for_float!(f32); +impl_weight_for_int!(usize); +#[cfg(not(target_os = "emscripten"))] +impl_weight_for_int!(u128); +impl_weight_for_int!(u64); +impl_weight_for_int!(u32); +impl_weight_for_int!(u16); +impl_weight_for_int!(u8); +impl_weight_for_int!(isize); +#[cfg(not(target_os = "emscripten"))] +impl_weight_for_int!(i128); +impl_weight_for_int!(i64); +impl_weight_for_int!(i32); +impl_weight_for_int!(i16); +impl_weight_for_int!(i8); + +#[cfg(test)] +mod test { + use super::*; + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weighted_index_f32() { + test_weighted_index(f32::into); + + // Floating point special cases + assert_eq!( + WeightedIndex::new(vec![::core::f32::INFINITY]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(vec![-0_f32]).unwrap_err(), + WeightedError::AllWeightsZero + ); + assert_eq!( + WeightedIndex::new(vec![-1_f32]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(vec![-::core::f32::INFINITY]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(vec![::core::f32::NAN]).unwrap_err(), + WeightedError::InvalidWeight + ); + } + + #[cfg(not(target_os = "emscripten"))] + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weighted_index_u128() { + test_weighted_index(|x: u128| x as f64); + } + + #[cfg(all(rustc_1_26, not(target_os = "emscripten")))] + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weighted_index_i128() { + test_weighted_index(|x: i128| x as f64); + + // Signed integer special cases + assert_eq!( + WeightedIndex::new(vec![-1_i128]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(vec![::core::i128::MIN]).unwrap_err(), + WeightedError::InvalidWeight + ); + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weighted_index_u8() { + test_weighted_index(u8::into); + } + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weighted_index_i8() { + test_weighted_index(i8::into); + + // Signed integer special cases + assert_eq!( + WeightedIndex::new(vec![-1_i8]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(vec![::core::i8::MIN]).unwrap_err(), + WeightedError::InvalidWeight + ); + } + + fn test_weighted_index<W: Weight, F: Fn(W) -> f64>(w_to_f64: F) + where WeightedIndex<W>: fmt::Debug { + const NUM_WEIGHTS: u32 = 10; + const ZERO_WEIGHT_INDEX: u32 = 3; + const NUM_SAMPLES: u32 = 15000; + let mut rng = crate::test::rng(0x9c9fa0b0580a7031); + + let weights = { + let mut weights = Vec::with_capacity(NUM_WEIGHTS as usize); + let random_weight_distribution = crate::distributions::Uniform::new_inclusive( + W::ZERO, + W::MAX / W::try_from_u32_lossy(NUM_WEIGHTS).unwrap(), + ); + for _ in 0..NUM_WEIGHTS { + weights.push(rng.sample(&random_weight_distribution)); + } + weights[ZERO_WEIGHT_INDEX as usize] = W::ZERO; + weights + }; + let weight_sum = weights.iter().map(|w| *w).sum::<W>(); + let expected_counts = weights + .iter() + .map(|&w| w_to_f64(w) / w_to_f64(weight_sum) * NUM_SAMPLES as f64) + .collect::<Vec<f64>>(); + let weight_distribution = WeightedIndex::new(weights).unwrap(); + + let mut counts = vec![0; NUM_WEIGHTS as usize]; + for _ in 0..NUM_SAMPLES { + counts[rng.sample(&weight_distribution)] += 1; + } + + assert_eq!(counts[ZERO_WEIGHT_INDEX as usize], 0); + for (count, expected_count) in counts.into_iter().zip(expected_counts) { + let difference = (count as f64 - expected_count).abs(); + let max_allowed_difference = NUM_SAMPLES as f64 / NUM_WEIGHTS as f64 * 0.1; + assert!(difference <= max_allowed_difference); + } + + assert_eq!( + WeightedIndex::<W>::new(vec![]).unwrap_err(), + WeightedError::NoItem + ); + assert_eq!( + WeightedIndex::new(vec![W::ZERO]).unwrap_err(), + WeightedError::AllWeightsZero + ); + assert_eq!( + WeightedIndex::new(vec![W::MAX, W::MAX]).unwrap_err(), + WeightedError::InvalidWeight + ); + } + + #[test] + fn value_stability() { + fn test_samples<W: Weight>(weights: Vec<W>, buf: &mut [usize], expected: &[usize]) { + assert_eq!(buf.len(), expected.len()); + let distr = WeightedIndex::new(weights).unwrap(); + let mut rng = crate::test::rng(0x9c9fa0b0580a7031); + for r in buf.iter_mut() { + *r = rng.sample(&distr); + } + assert_eq!(buf, expected); + } + + let mut buf = [0; 10]; + test_samples(vec![1i32, 1, 1, 1, 1, 1, 1, 1, 1], &mut buf, &[ + 6, 5, 7, 5, 8, 7, 6, 2, 3, 7, + ]); + test_samples(vec![0.7f32, 0.1, 0.1, 0.1], &mut buf, &[ + 2, 0, 0, 0, 0, 0, 0, 0, 1, 3, + ]); + test_samples(vec![1.0f64, 0.999, 0.998, 0.997], &mut buf, &[ + 2, 1, 2, 3, 2, 1, 3, 2, 1, 1, + ]); + } +} diff --git a/vendor/rand-0.7.3/src/distributions/weighted/mod.rs b/vendor/rand-0.7.3/src/distributions/weighted/mod.rs new file mode 100644 index 000000000..357e3a9f0 --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/weighted/mod.rs @@ -0,0 +1,413 @@ +// Copyright 2018 Developers of the Rand project. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Weighted index sampling +//! +//! This module provides two implementations for sampling indices: +//! +//! * [`WeightedIndex`] allows `O(log N)` sampling +//! * [`alias_method::WeightedIndex`] allows `O(1)` sampling, but with +//! much greater set-up cost +//! +//! [`alias_method::WeightedIndex`]: alias_method/struct.WeightedIndex.html + +pub mod alias_method; + +use crate::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler}; +use crate::distributions::Distribution; +use crate::Rng; +use core::cmp::PartialOrd; +use core::fmt; + +// Note that this whole module is only imported if feature="alloc" is enabled. +#[cfg(not(feature = "std"))] use crate::alloc::vec::Vec; + +/// A distribution using weighted sampling to pick a discretely selected +/// item. +/// +/// Sampling a `WeightedIndex` distribution returns the index of a randomly +/// selected element from the iterator used when the `WeightedIndex` was +/// created. The chance of a given element being picked is proportional to the +/// value of the element. The weights can use any type `X` for which an +/// implementation of [`Uniform<X>`] exists. +/// +/// # Performance +/// +/// A `WeightedIndex<X>` contains a `Vec<X>` and a [`Uniform<X>`] and so its +/// size is the sum of the size of those objects, possibly plus some alignment. +/// +/// Creating a `WeightedIndex<X>` will allocate enough space to hold `N - 1` +/// weights of type `X`, where `N` is the number of weights. However, since +/// `Vec` doesn't guarantee a particular growth strategy, additional memory +/// might be allocated but not used. Since the `WeightedIndex` object also +/// contains, this might cause additional allocations, though for primitive +/// types, ['Uniform<X>`] doesn't allocate any memory. +/// +/// Time complexity of sampling from `WeightedIndex` is `O(log N)` where +/// `N` is the number of weights. +/// +/// Sampling from `WeightedIndex` will result in a single call to +/// `Uniform<X>::sample` (method of the [`Distribution`] trait), which typically +/// will request a single value from the underlying [`RngCore`], though the +/// exact number depends on the implementaiton of `Uniform<X>::sample`. +/// +/// # Example +/// +/// ``` +/// use rand::prelude::*; +/// use rand::distributions::WeightedIndex; +/// +/// let choices = ['a', 'b', 'c']; +/// let weights = [2, 1, 1]; +/// let dist = WeightedIndex::new(&weights).unwrap(); +/// let mut rng = thread_rng(); +/// for _ in 0..100 { +/// // 50% chance to print 'a', 25% chance to print 'b', 25% chance to print 'c' +/// println!("{}", choices[dist.sample(&mut rng)]); +/// } +/// +/// let items = [('a', 0), ('b', 3), ('c', 7)]; +/// let dist2 = WeightedIndex::new(items.iter().map(|item| item.1)).unwrap(); +/// for _ in 0..100 { +/// // 0% chance to print 'a', 30% chance to print 'b', 70% chance to print 'c' +/// println!("{}", items[dist2.sample(&mut rng)].0); +/// } +/// ``` +/// +/// [`Uniform<X>`]: crate::distributions::uniform::Uniform +/// [`RngCore`]: crate::RngCore +#[derive(Debug, Clone)] +pub struct WeightedIndex<X: SampleUniform + PartialOrd> { + cumulative_weights: Vec<X>, + total_weight: X, + weight_distribution: X::Sampler, +} + +impl<X: SampleUniform + PartialOrd> WeightedIndex<X> { + /// Creates a new a `WeightedIndex` [`Distribution`] using the values + /// in `weights`. The weights can use any type `X` for which an + /// implementation of [`Uniform<X>`] exists. + /// + /// Returns an error if the iterator is empty, if any weight is `< 0`, or + /// if its total value is 0. + /// + /// [`Uniform<X>`]: crate::distributions::uniform::Uniform + pub fn new<I>(weights: I) -> Result<WeightedIndex<X>, WeightedError> + where + I: IntoIterator, + I::Item: SampleBorrow<X>, + X: for<'a> ::core::ops::AddAssign<&'a X> + Clone + Default, + { + let mut iter = weights.into_iter(); + let mut total_weight: X = iter.next().ok_or(WeightedError::NoItem)?.borrow().clone(); + + let zero = <X as Default>::default(); + if total_weight < zero { + return Err(WeightedError::InvalidWeight); + } + + let mut weights = Vec::<X>::with_capacity(iter.size_hint().0); + for w in iter { + if *w.borrow() < zero { + return Err(WeightedError::InvalidWeight); + } + weights.push(total_weight.clone()); + total_weight += w.borrow(); + } + + if total_weight == zero { + return Err(WeightedError::AllWeightsZero); + } + let distr = X::Sampler::new(zero, total_weight.clone()); + + Ok(WeightedIndex { + cumulative_weights: weights, + total_weight, + weight_distribution: distr, + }) + } + + /// Update a subset of weights, without changing the number of weights. + /// + /// `new_weights` must be sorted by the index. + /// + /// Using this method instead of `new` might be more efficient if only a small number of + /// weights is modified. No allocations are performed, unless the weight type `X` uses + /// allocation internally. + /// + /// In case of error, `self` is not modified. + pub fn update_weights(&mut self, new_weights: &[(usize, &X)]) -> Result<(), WeightedError> + where X: for<'a> ::core::ops::AddAssign<&'a X> + + for<'a> ::core::ops::SubAssign<&'a X> + + Clone + + Default { + if new_weights.is_empty() { + return Ok(()); + } + + let zero = <X as Default>::default(); + + let mut total_weight = self.total_weight.clone(); + + // Check for errors first, so we don't modify `self` in case something + // goes wrong. + let mut prev_i = None; + for &(i, w) in new_weights { + if let Some(old_i) = prev_i { + if old_i >= i { + return Err(WeightedError::InvalidWeight); + } + } + if *w < zero { + return Err(WeightedError::InvalidWeight); + } + if i >= self.cumulative_weights.len() + 1 { + return Err(WeightedError::TooMany); + } + + let mut old_w = if i < self.cumulative_weights.len() { + self.cumulative_weights[i].clone() + } else { + self.total_weight.clone() + }; + if i > 0 { + old_w -= &self.cumulative_weights[i - 1]; + } + + total_weight -= &old_w; + total_weight += w; + prev_i = Some(i); + } + if total_weight == zero { + return Err(WeightedError::AllWeightsZero); + } + + // Update the weights. Because we checked all the preconditions in the + // previous loop, this should never panic. + let mut iter = new_weights.iter(); + + let mut prev_weight = zero.clone(); + let mut next_new_weight = iter.next(); + let &(first_new_index, _) = next_new_weight.unwrap(); + let mut cumulative_weight = if first_new_index > 0 { + self.cumulative_weights[first_new_index - 1].clone() + } else { + zero.clone() + }; + for i in first_new_index..self.cumulative_weights.len() { + match next_new_weight { + Some(&(j, w)) if i == j => { + cumulative_weight += w; + next_new_weight = iter.next(); + } + _ => { + let mut tmp = self.cumulative_weights[i].clone(); + tmp -= &prev_weight; // We know this is positive. + cumulative_weight += &tmp; + } + } + prev_weight = cumulative_weight.clone(); + core::mem::swap(&mut prev_weight, &mut self.cumulative_weights[i]); + } + + self.total_weight = total_weight; + self.weight_distribution = X::Sampler::new(zero, self.total_weight.clone()); + + Ok(()) + } +} + +impl<X> Distribution<usize> for WeightedIndex<X> +where X: SampleUniform + PartialOrd +{ + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> usize { + use ::core::cmp::Ordering; + let chosen_weight = self.weight_distribution.sample(rng); + // Find the first item which has a weight *higher* than the chosen weight. + self.cumulative_weights + .binary_search_by(|w| { + if *w <= chosen_weight { + Ordering::Less + } else { + Ordering::Greater + } + }) + .unwrap_err() + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + #[cfg_attr(miri, ignore)] // Miri is too slow + fn test_weightedindex() { + let mut r = crate::test::rng(700); + const N_REPS: u32 = 5000; + let weights = [1u32, 2, 3, 0, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]; + let total_weight = weights.iter().sum::<u32>() as f32; + + let verify = |result: [i32; 14]| { + for (i, count) in result.iter().enumerate() { + let exp = (weights[i] * N_REPS) as f32 / total_weight; + let mut err = (*count as f32 - exp).abs(); + if err != 0.0 { + err /= exp; + } + assert!(err <= 0.25); + } + }; + + // WeightedIndex from vec + let mut chosen = [0i32; 14]; + let distr = WeightedIndex::new(weights.to_vec()).unwrap(); + for _ in 0..N_REPS { + chosen[distr.sample(&mut r)] += 1; + } + verify(chosen); + + // WeightedIndex from slice + chosen = [0i32; 14]; + let distr = WeightedIndex::new(&weights[..]).unwrap(); + for _ in 0..N_REPS { + chosen[distr.sample(&mut r)] += 1; + } + verify(chosen); + + // WeightedIndex from iterator + chosen = [0i32; 14]; + let distr = WeightedIndex::new(weights.iter()).unwrap(); + for _ in 0..N_REPS { + chosen[distr.sample(&mut r)] += 1; + } + verify(chosen); + + for _ in 0..5 { + assert_eq!(WeightedIndex::new(&[0, 1]).unwrap().sample(&mut r), 1); + assert_eq!(WeightedIndex::new(&[1, 0]).unwrap().sample(&mut r), 0); + assert_eq!( + WeightedIndex::new(&[0, 0, 0, 0, 10, 0]) + .unwrap() + .sample(&mut r), + 4 + ); + } + + assert_eq!( + WeightedIndex::new(&[10][0..0]).unwrap_err(), + WeightedError::NoItem + ); + assert_eq!( + WeightedIndex::new(&[0]).unwrap_err(), + WeightedError::AllWeightsZero + ); + assert_eq!( + WeightedIndex::new(&[10, 20, -1, 30]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(&[-10, 20, 1, 30]).unwrap_err(), + WeightedError::InvalidWeight + ); + assert_eq!( + WeightedIndex::new(&[-10]).unwrap_err(), + WeightedError::InvalidWeight + ); + } + + #[test] + fn test_update_weights() { + let data = [ + ( + &[10u32, 2, 3, 4][..], + &[(1, &100), (2, &4)][..], // positive change + &[10, 100, 4, 4][..], + ), + ( + &[1u32, 2, 3, 0, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7][..], + &[(2, &1), (5, &1), (13, &100)][..], // negative change and last element + &[1u32, 2, 1, 0, 5, 1, 7, 1, 2, 3, 4, 5, 6, 100][..], + ), + ]; + + for (weights, update, expected_weights) in data.iter() { + let total_weight = weights.iter().sum::<u32>(); + let mut distr = WeightedIndex::new(weights.to_vec()).unwrap(); + assert_eq!(distr.total_weight, total_weight); + + distr.update_weights(update).unwrap(); + let expected_total_weight = expected_weights.iter().sum::<u32>(); + let expected_distr = WeightedIndex::new(expected_weights.to_vec()).unwrap(); + assert_eq!(distr.total_weight, expected_total_weight); + assert_eq!(distr.total_weight, expected_distr.total_weight); + assert_eq!(distr.cumulative_weights, expected_distr.cumulative_weights); + } + } + + #[test] + fn value_stability() { + fn test_samples<X: SampleUniform + PartialOrd, I>( + weights: I, buf: &mut [usize], expected: &[usize], + ) where + I: IntoIterator, + I::Item: SampleBorrow<X>, + X: for<'a> ::core::ops::AddAssign<&'a X> + Clone + Default, + { + assert_eq!(buf.len(), expected.len()); + let distr = WeightedIndex::new(weights).unwrap(); + let mut rng = crate::test::rng(701); + for r in buf.iter_mut() { + *r = rng.sample(&distr); + } + assert_eq!(buf, expected); + } + + let mut buf = [0; 10]; + test_samples(&[1i32, 1, 1, 1, 1, 1, 1, 1, 1], &mut buf, &[ + 0, 6, 2, 6, 3, 4, 7, 8, 2, 5, + ]); + test_samples(&[0.7f32, 0.1, 0.1, 0.1], &mut buf, &[ + 0, 0, 0, 1, 0, 0, 2, 3, 0, 0, + ]); + test_samples(&[1.0f64, 0.999, 0.998, 0.997], &mut buf, &[ + 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, + ]); + } +} + +/// Error type returned from `WeightedIndex::new`. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum WeightedError { + /// The provided weight collection contains no items. + NoItem, + + /// A weight is either less than zero, greater than the supported maximum or + /// otherwise invalid. + InvalidWeight, + + /// All items in the provided weight collection are zero. + AllWeightsZero, + + /// Too many weights are provided (length greater than `u32::MAX`) + TooMany, +} + +#[cfg(feature = "std")] +impl ::std::error::Error for WeightedError {} + +impl fmt::Display for WeightedError { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + WeightedError::NoItem => write!(f, "No weights provided."), + WeightedError::InvalidWeight => write!(f, "A weight is invalid."), + WeightedError::AllWeightsZero => write!(f, "All weights are zero."), + WeightedError::TooMany => write!(f, "Too many weights (hit u32::MAX)"), + } + } +} diff --git a/vendor/rand-0.7.3/src/distributions/ziggurat_tables.rs b/vendor/rand-0.7.3/src/distributions/ziggurat_tables.rs new file mode 100644 index 000000000..f830a601b --- /dev/null +++ b/vendor/rand-0.7.3/src/distributions/ziggurat_tables.rs @@ -0,0 +1,283 @@ +// Copyright 2018 Developers of the Rand project. +// Copyright 2013 The Rust Project Developers. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Tables for distributions which are sampled using the ziggurat +// algorithm. Autogenerated by `ziggurat_tables.py`. + +pub type ZigTable = &'static [f64; 257]; +pub const ZIG_NORM_R: f64 = 3.654152885361008796; +#[rustfmt::skip] +pub static ZIG_NORM_X: [f64; 257] = + [3.910757959537090045, 3.654152885361008796, 3.449278298560964462, 3.320244733839166074, + 3.224575052047029100, 3.147889289517149969, 3.083526132001233044, 3.027837791768635434, + 2.978603279880844834, 2.934366867207854224, 2.894121053612348060, 2.857138730872132548, + 2.822877396825325125, 2.790921174000785765, 2.760944005278822555, 2.732685359042827056, + 2.705933656121858100, 2.680514643284522158, 2.656283037575502437, 2.633116393630324570, + 2.610910518487548515, 2.589575986706995181, 2.569035452680536569, 2.549221550323460761, + 2.530075232158516929, 2.511544441625342294, 2.493583041269680667, 2.476149939669143318, + 2.459208374333311298, 2.442725318198956774, 2.426670984935725972, 2.411018413899685520, + 2.395743119780480601, 2.380822795170626005, 2.366237056715818632, 2.351967227377659952, + 2.337996148795031370, 2.324308018869623016, 2.310888250599850036, 2.297723348901329565, + 2.284800802722946056, 2.272108990226823888, 2.259637095172217780, 2.247375032945807760, + 2.235313384928327984, 2.223443340090905718, 2.211756642882544366, 2.200245546609647995, + 2.188902771624720689, 2.177721467738641614, 2.166695180352645966, 2.155817819875063268, + 2.145083634046203613, 2.134487182844320152, 2.124023315687815661, 2.113687150684933957, + 2.103474055713146829, 2.093379631137050279, 2.083399693996551783, 2.073530263516978778, + 2.063767547809956415, 2.054107931648864849, 2.044547965215732788, 2.035084353727808715, + 2.025713947862032960, 2.016433734904371722, 2.007240830558684852, 1.998132471356564244, + 1.989106007615571325, 1.980158896898598364, 1.971288697931769640, 1.962493064942461896, + 1.953769742382734043, 1.945116560006753925, 1.936531428273758904, 1.928012334050718257, + 1.919557336591228847, 1.911164563769282232, 1.902832208548446369, 1.894558525668710081, + 1.886341828534776388, 1.878180486290977669, 1.870072921069236838, 1.862017605397632281, + 1.854013059758148119, 1.846057850283119750, 1.838150586580728607, 1.830289919680666566, + 1.822474540091783224, 1.814703175964167636, 1.806974591348693426, 1.799287584547580199, + 1.791640986550010028, 1.784033659547276329, 1.776464495522344977, 1.768932414909077933, + 1.761436365316706665, 1.753975320315455111, 1.746548278279492994, 1.739154261283669012, + 1.731792314050707216, 1.724461502945775715, 1.717160915015540690, 1.709889657069006086, + 1.702646854797613907, 1.695431651932238548, 1.688243209434858727, 1.681080704722823338, + 1.673943330923760353, 1.666830296159286684, 1.659740822855789499, 1.652674147080648526, + 1.645629517902360339, 1.638606196773111146, 1.631603456932422036, 1.624620582830568427, + 1.617656869570534228, 1.610711622367333673, 1.603784156023583041, 1.596873794420261339, + 1.589979870021648534, 1.583101723393471438, 1.576238702733332886, 1.569390163412534456, + 1.562555467528439657, 1.555733983466554893, 1.548925085471535512, 1.542128153226347553, + 1.535342571438843118, 1.528567729435024614, 1.521803020758293101, 1.515047842773992404, + 1.508301596278571965, 1.501563685112706548, 1.494833515777718391, 1.488110497054654369, + 1.481394039625375747, 1.474683555695025516, 1.467978458615230908, 1.461278162507407830, + 1.454582081885523293, 1.447889631277669675, 1.441200224845798017, 1.434513276002946425, + 1.427828197027290358, 1.421144398672323117, 1.414461289772464658, 1.407778276843371534, + 1.401094763676202559, 1.394410150925071257, 1.387723835686884621, 1.381035211072741964, + 1.374343665770030531, 1.367648583594317957, 1.360949343030101844, 1.354245316759430606, + 1.347535871177359290, 1.340820365893152122, 1.334098153216083604, 1.327368577624624679, + 1.320630975217730096, 1.313884673146868964, 1.307128989027353860, 1.300363230327433728, + 1.293586693733517645, 1.286798664489786415, 1.279998415710333237, 1.273185207661843732, + 1.266358287014688333, 1.259516886060144225, 1.252660221891297887, 1.245787495544997903, + 1.238897891102027415, 1.231990574742445110, 1.225064693752808020, 1.218119375481726552, + 1.211153726239911244, 1.204166830140560140, 1.197157747875585931, 1.190125515422801650, + 1.183069142678760732, 1.175987612011489825, 1.168879876726833800, 1.161744859441574240, + 1.154581450355851802, 1.147388505416733873, 1.140164844363995789, 1.132909248648336975, + 1.125620459211294389, 1.118297174115062909, 1.110938046009249502, 1.103541679420268151, + 1.096106627847603487, 1.088631390649514197, 1.081114409698889389, 1.073554065787871714, + 1.065948674757506653, 1.058296483326006454, 1.050595664586207123, 1.042844313139370538, + 1.035040439828605274, 1.027181966030751292, 1.019266717460529215, 1.011292417434978441, + 1.003256679539591412, 0.995156999629943084, 0.986990747093846266, 0.978755155288937750, + 0.970447311058864615, 0.962064143217605250, 0.953602409875572654, 0.945058684462571130, + 0.936429340280896860, 0.927710533396234771, 0.918898183643734989, 0.909987953490768997, + 0.900975224455174528, 0.891855070726792376, 0.882622229578910122, 0.873271068082494550, + 0.863795545546826915, 0.854189171001560554, 0.844444954902423661, 0.834555354079518752, + 0.824512208745288633, 0.814306670128064347, 0.803929116982664893, 0.793369058833152785, + 0.782615023299588763, 0.771654424216739354, 0.760473406422083165, 0.749056662009581653, + 0.737387211425838629, 0.725446140901303549, 0.713212285182022732, 0.700661841097584448, + 0.687767892786257717, 0.674499822827436479, 0.660822574234205984, 0.646695714884388928, + 0.632072236375024632, 0.616896989996235545, 0.601104617743940417, 0.584616766093722262, + 0.567338257040473026, 0.549151702313026790, 0.529909720646495108, 0.509423329585933393, + 0.487443966121754335, 0.463634336771763245, 0.437518402186662658, 0.408389134588000746, + 0.375121332850465727, 0.335737519180459465, 0.286174591747260509, 0.215241895913273806, + 0.000000000000000000]; +#[rustfmt::skip] +pub static ZIG_NORM_F: [f64; 257] = + [0.000477467764586655, 0.001260285930498598, 0.002609072746106363, 0.004037972593371872, + 0.005522403299264754, 0.007050875471392110, 0.008616582769422917, 0.010214971439731100, + 0.011842757857943104, 0.013497450601780807, 0.015177088307982072, 0.016880083152595839, + 0.018605121275783350, 0.020351096230109354, 0.022117062707379922, 0.023902203305873237, + 0.025705804008632656, 0.027527235669693315, 0.029365939758230111, 0.031221417192023690, + 0.033093219458688698, 0.034980941461833073, 0.036884215688691151, 0.038802707404656918, + 0.040736110656078753, 0.042684144916619378, 0.044646552251446536, 0.046623094902089664, + 0.048613553216035145, 0.050617723861121788, 0.052635418276973649, 0.054666461325077916, + 0.056710690106399467, 0.058767952921137984, 0.060838108349751806, 0.062921024437977854, + 0.065016577971470438, 0.067124653828023989, 0.069245144397250269, 0.071377949059141965, + 0.073522973714240991, 0.075680130359194964, 0.077849336702372207, 0.080030515814947509, + 0.082223595813495684, 0.084428509570654661, 0.086645194450867782, 0.088873592068594229, + 0.091113648066700734, 0.093365311913026619, 0.095628536713353335, 0.097903279039215627, + 0.100189498769172020, 0.102487158942306270, 0.104796225622867056, 0.107116667775072880, + 0.109448457147210021, 0.111791568164245583, 0.114145977828255210, 0.116511665626037014, + 0.118888613443345698, 0.121276805485235437, 0.123676228202051403, 0.126086870220650349, + 0.128508722280473636, 0.130941777174128166, 0.133386029692162844, 0.135841476571757352, + 0.138308116449064322, 0.140785949814968309, 0.143274978974047118, 0.145775208006537926, + 0.148286642733128721, 0.150809290682410169, 0.153343161060837674, 0.155888264725064563, + 0.158444614156520225, 0.161012223438117663, 0.163591108232982951, 0.166181285765110071, + 0.168782774801850333, 0.171395595638155623, 0.174019770082499359, 0.176655321444406654, + 0.179302274523530397, 0.181960655600216487, 0.184630492427504539, 0.187311814224516926, + 0.190004651671193070, 0.192709036904328807, 0.195425003514885592, 0.198152586546538112, + 0.200891822495431333, 0.203642749311121501, 0.206405406398679298, 0.209179834621935651, + 0.211966076307852941, 0.214764175252008499, 0.217574176725178370, 0.220396127481011589, + 0.223230075764789593, 0.226076071323264877, 0.228934165415577484, 0.231804410825248525, + 0.234686861873252689, 0.237581574432173676, 0.240488605941449107, 0.243408015423711988, + 0.246339863502238771, 0.249284212419516704, 0.252241126056943765, 0.255210669955677150, + 0.258192911338648023, 0.261187919133763713, 0.264195763998317568, 0.267216518344631837, + 0.270250256366959984, 0.273297054069675804, 0.276356989296781264, 0.279430141762765316, + 0.282516593084849388, 0.285616426816658109, 0.288729728483353931, 0.291856585618280984, + 0.294997087801162572, 0.298151326697901342, 0.301319396102034120, 0.304501391977896274, + 0.307697412505553769, 0.310907558127563710, 0.314131931597630143, 0.317370638031222396, + 0.320623784958230129, 0.323891482377732021, 0.327173842814958593, 0.330470981380537099, + 0.333783015832108509, 0.337110066638412809, 0.340452257045945450, 0.343809713148291340, + 0.347182563958251478, 0.350570941482881204, 0.353974980801569250, 0.357394820147290515, + 0.360830600991175754, 0.364282468130549597, 0.367750569780596226, 0.371235057669821344, + 0.374736087139491414, 0.378253817247238111, 0.381788410875031348, 0.385340034841733958, + 0.388908860020464597, 0.392495061461010764, 0.396098818517547080, 0.399720314981931668, + 0.403359739222868885, 0.407017284331247953, 0.410693148271983222, 0.414387534042706784, + 0.418100649839684591, 0.421832709231353298, 0.425583931339900579, 0.429354541031341519, + 0.433144769114574058, 0.436954852549929273, 0.440785034667769915, 0.444635565397727750, + 0.448506701509214067, 0.452398706863882505, 0.456311852680773566, 0.460246417814923481, + 0.464202689050278838, 0.468180961407822172, 0.472181538469883255, 0.476204732721683788, + 0.480250865911249714, 0.484320269428911598, 0.488413284707712059, 0.492530263646148658, + 0.496671569054796314, 0.500837575128482149, 0.505028667945828791, 0.509245245998136142, + 0.513487720749743026, 0.517756517232200619, 0.522052074674794864, 0.526374847174186700, + 0.530725304406193921, 0.535103932383019565, 0.539511234259544614, 0.543947731192649941, + 0.548413963257921133, 0.552910490428519918, 0.557437893621486324, 0.561996775817277916, + 0.566587763258951771, 0.571211506738074970, 0.575868682975210544, 0.580559996103683473, + 0.585286179266300333, 0.590047996335791969, 0.594846243770991268, 0.599681752622167719, + 0.604555390700549533, 0.609468064928895381, 0.614420723892076803, 0.619414360609039205, + 0.624450015550274240, 0.629528779928128279, 0.634651799290960050, 0.639820277456438991, + 0.645035480824251883, 0.650298743114294586, 0.655611470583224665, 0.660975147780241357, + 0.666391343912380640, 0.671861719900766374, 0.677388036222513090, 0.682972161648791376, + 0.688616083008527058, 0.694321916130032579, 0.700091918140490099, 0.705928501336797409, + 0.711834248882358467, 0.717811932634901395, 0.723864533472881599, 0.729995264565802437, + 0.736207598131266683, 0.742505296344636245, 0.748892447223726720, 0.755373506511754500, + 0.761953346841546475, 0.768637315803334831, 0.775431304986138326, 0.782341832659861902, + 0.789376143571198563, 0.796542330428254619, 0.803849483176389490, 0.811307874318219935, + 0.818929191609414797, 0.826726833952094231, 0.834716292992930375, 0.842915653118441077, + 0.851346258465123684, 0.860033621203008636, 0.869008688043793165, 0.878309655816146839, + 0.887984660763399880, 0.898095921906304051, 0.908726440060562912, 0.919991505048360247, + 0.932060075968990209, 0.945198953453078028, 0.959879091812415930, 0.977101701282731328, + 1.000000000000000000]; +pub const ZIG_EXP_R: f64 = 7.697117470131050077; +#[rustfmt::skip] +pub static ZIG_EXP_X: [f64; 257] = + [8.697117470131052741, 7.697117470131050077, 6.941033629377212577, 6.478378493832569696, + 6.144164665772472667, 5.882144315795399869, 5.666410167454033697, 5.482890627526062488, + 5.323090505754398016, 5.181487281301500047, 5.054288489981304089, 4.938777085901250530, + 4.832939741025112035, 4.735242996601741083, 4.644491885420085175, 4.559737061707351380, + 4.480211746528421912, 4.405287693473573185, 4.334443680317273007, 4.267242480277365857, + 4.203313713735184365, 4.142340865664051464, 4.084051310408297830, 4.028208544647936762, + 3.974606066673788796, 3.923062500135489739, 3.873417670399509127, 3.825529418522336744, + 3.779270992411667862, 3.734528894039797375, 3.691201090237418825, 3.649195515760853770, + 3.608428813128909507, 3.568825265648337020, 3.530315889129343354, 3.492837654774059608, + 3.456332821132760191, 3.420748357251119920, 3.386035442460300970, 3.352149030900109405, + 3.319047470970748037, 3.286692171599068679, 3.255047308570449882, 3.224079565286264160, + 3.193757903212240290, 3.164053358025972873, 3.134938858084440394, 3.106389062339824481, + 3.078380215254090224, 3.050890016615455114, 3.023897504455676621, 2.997382949516130601, + 2.971327759921089662, 2.945714394895045718, 2.920526286512740821, 2.895747768600141825, + 2.871364012015536371, 2.847360965635188812, 2.823725302450035279, 2.800444370250737780, + 2.777506146439756574, 2.754899196562344610, 2.732612636194700073, 2.710636095867928752, + 2.688959688741803689, 2.667573980773266573, 2.646469963151809157, 2.625639026797788489, + 2.605072938740835564, 2.584763820214140750, 2.564704126316905253, 2.544886627111869970, + 2.525304390037828028, 2.505950763528594027, 2.486819361740209455, 2.467904050297364815, + 2.449198932978249754, 2.430698339264419694, 2.412396812688870629, 2.394289099921457886, + 2.376370140536140596, 2.358635057409337321, 2.341079147703034380, 2.323697874390196372, + 2.306486858283579799, 2.289441870532269441, 2.272558825553154804, 2.255833774367219213, + 2.239262898312909034, 2.222842503111036816, 2.206569013257663858, 2.190438966723220027, + 2.174449009937774679, 2.158595893043885994, 2.142876465399842001, 2.127287671317368289, + 2.111826546019042183, 2.096490211801715020, 2.081275874393225145, 2.066180819490575526, + 2.051202409468584786, 2.036338080248769611, 2.021585338318926173, 2.006941757894518563, + 1.992404978213576650, 1.977972700957360441, 1.963642687789548313, 1.949412758007184943, + 1.935280786297051359, 1.921244700591528076, 1.907302480018387536, 1.893452152939308242, + 1.879691795072211180, 1.866019527692827973, 1.852433515911175554, 1.838931967018879954, + 1.825513128903519799, 1.812175288526390649, 1.798916770460290859, 1.785735935484126014, + 1.772631179231305643, 1.759600930889074766, 1.746643651946074405, 1.733757834985571566, + 1.720942002521935299, 1.708194705878057773, 1.695514524101537912, 1.682900062917553896, + 1.670349953716452118, 1.657862852574172763, 1.645437439303723659, 1.633072416535991334, + 1.620766508828257901, 1.608518461798858379, 1.596327041286483395, 1.584191032532688892, + 1.572109239386229707, 1.560080483527888084, 1.548103603714513499, 1.536177455041032092, + 1.524300908219226258, 1.512472848872117082, 1.500692176842816750, 1.488957805516746058, + 1.477268661156133867, 1.465623682245745352, 1.454021818848793446, 1.442462031972012504, + 1.430943292938879674, 1.419464582769983219, 1.408024891569535697, 1.396623217917042137, + 1.385258568263121992, 1.373929956328490576, 1.362636402505086775, 1.351376933258335189, + 1.340150580529504643, 1.328956381137116560, 1.317793376176324749, 1.306660610415174117, + 1.295557131686601027, 1.284481990275012642, 1.273434238296241139, 1.262412929069615330, + 1.251417116480852521, 1.240445854334406572, 1.229498195693849105, 1.218573192208790124, + 1.207669893426761121, 1.196787346088403092, 1.185924593404202199, 1.175080674310911677, + 1.164254622705678921, 1.153445466655774743, 1.142652227581672841, 1.131873919411078511, + 1.121109547701330200, 1.110358108727411031, 1.099618588532597308, 1.088889961938546813, + 1.078171191511372307, 1.067461226479967662, 1.056759001602551429, 1.046063435977044209, + 1.035373431790528542, 1.024687873002617211, 1.014005623957096480, 1.003325527915696735, + 0.992646405507275897, 0.981967053085062602, 0.971286240983903260, 0.960602711668666509, + 0.949915177764075969, 0.939222319955262286, 0.928522784747210395, 0.917815182070044311, + 0.907098082715690257, 0.896370015589889935, 0.885629464761751528, 0.874874866291025066, + 0.864104604811004484, 0.853317009842373353, 0.842510351810368485, 0.831682837734273206, + 0.820832606554411814, 0.809957724057418282, 0.799056177355487174, 0.788125868869492430, + 0.777164609759129710, 0.766170112735434672, 0.755139984181982249, 0.744071715500508102, + 0.732962673584365398, 0.721810090308756203, 0.710611050909655040, 0.699362481103231959, + 0.688061132773747808, 0.676703568029522584, 0.665286141392677943, 0.653804979847664947, + 0.642255960424536365, 0.630634684933490286, 0.618936451394876075, 0.607156221620300030, + 0.595288584291502887, 0.583327712748769489, 0.571267316532588332, 0.559100585511540626, + 0.546820125163310577, 0.534417881237165604, 0.521885051592135052, 0.509211982443654398, + 0.496388045518671162, 0.483401491653461857, 0.470239275082169006, 0.456886840931420235, + 0.443327866073552401, 0.429543940225410703, 0.415514169600356364, 0.401214678896277765, + 0.386617977941119573, 0.371692145329917234, 0.356399760258393816, 0.340696481064849122, + 0.324529117016909452, 0.307832954674932158, 0.290527955491230394, 0.272513185478464703, + 0.253658363385912022, 0.233790483059674731, 0.212671510630966620, 0.189958689622431842, + 0.165127622564187282, 0.137304980940012589, 0.104838507565818778, 0.063852163815001570, + 0.000000000000000000]; +#[rustfmt::skip] +pub static ZIG_EXP_F: [f64; 257] = + [0.000167066692307963, 0.000454134353841497, 0.000967269282327174, 0.001536299780301573, + 0.002145967743718907, 0.002788798793574076, 0.003460264777836904, 0.004157295120833797, + 0.004877655983542396, 0.005619642207205489, 0.006381905937319183, 0.007163353183634991, + 0.007963077438017043, 0.008780314985808977, 0.009614413642502212, 0.010464810181029981, + 0.011331013597834600, 0.012212592426255378, 0.013109164931254991, 0.014020391403181943, + 0.014945968011691148, 0.015885621839973156, 0.016839106826039941, 0.017806200410911355, + 0.018786700744696024, 0.019780424338009740, 0.020787204072578114, 0.021806887504283581, + 0.022839335406385240, 0.023884420511558174, 0.024942026419731787, 0.026012046645134221, + 0.027094383780955803, 0.028188948763978646, 0.029295660224637411, 0.030414443910466622, + 0.031545232172893622, 0.032687963508959555, 0.033842582150874358, 0.035009037697397431, + 0.036187284781931443, 0.037377282772959382, 0.038578995503074871, 0.039792391023374139, + 0.041017441380414840, 0.042254122413316254, 0.043502413568888197, 0.044762297732943289, + 0.046033761076175184, 0.047316792913181561, 0.048611385573379504, 0.049917534282706379, + 0.051235237055126281, 0.052564494593071685, 0.053905310196046080, 0.055257689676697030, + 0.056621641283742870, 0.057997175631200659, 0.059384305633420280, 0.060783046445479660, + 0.062193415408541036, 0.063615431999807376, 0.065049117786753805, 0.066494496385339816, + 0.067951593421936643, 0.069420436498728783, 0.070901055162371843, 0.072393480875708752, + 0.073897746992364746, 0.075413888734058410, 0.076941943170480517, 0.078481949201606435, + 0.080033947542319905, 0.081597980709237419, 0.083174093009632397, 0.084762330532368146, + 0.086362741140756927, 0.087975374467270231, 0.089600281910032886, 0.091237516631040197, + 0.092887133556043569, 0.094549189376055873, 0.096223742550432825, 0.097910853311492213, + 0.099610583670637132, 0.101322997425953631, 0.103048160171257702, 0.104786139306570145, + 0.106537004050001632, 0.108300825451033755, 0.110077676405185357, 0.111867631670056283, + 0.113670767882744286, 0.115487163578633506, 0.117316899211555525, 0.119160057175327641, + 0.121016721826674792, 0.122886979509545108, 0.124770918580830933, 0.126668629437510671, + 0.128580204545228199, 0.130505738468330773, 0.132445327901387494, 0.134399071702213602, + 0.136367070926428829, 0.138349428863580176, 0.140346251074862399, 0.142357645432472146, + 0.144383722160634720, 0.146424593878344889, 0.148480375643866735, 0.150551185001039839, + 0.152637142027442801, 0.154738369384468027, 0.156854992369365148, 0.158987138969314129, + 0.161134939917591952, 0.163298528751901734, 0.165478041874935922, 0.167673618617250081, + 0.169885401302527550, 0.172113535315319977, 0.174358169171353411, 0.176619454590494829, + 0.178897546572478278, 0.181192603475496261, 0.183504787097767436, 0.185834262762197083, + 0.188181199404254262, 0.190545769663195363, 0.192928149976771296, 0.195328520679563189, + 0.197747066105098818, 0.200183974691911210, 0.202639439093708962, 0.205113656293837654, + 0.207606827724221982, 0.210119159388988230, 0.212650861992978224, 0.215202151075378628, + 0.217773247148700472, 0.220364375843359439, 0.222975768058120111, 0.225607660116683956, + 0.228260293930716618, 0.230933917169627356, 0.233628783437433291, 0.236345152457059560, + 0.239083290262449094, 0.241843469398877131, 0.244625969131892024, 0.247431075665327543, + 0.250259082368862240, 0.253110290015629402, 0.255985007030415324, 0.258883549749016173, + 0.261806242689362922, 0.264753418835062149, 0.267725419932044739, 0.270722596799059967, + 0.273745309652802915, 0.276793928448517301, 0.279868833236972869, 0.282970414538780746, + 0.286099073737076826, 0.289255223489677693, 0.292439288161892630, 0.295651704281261252, + 0.298892921015581847, 0.302163400675693528, 0.305463619244590256, 0.308794066934560185, + 0.312155248774179606, 0.315547685227128949, 0.318971912844957239, 0.322428484956089223, + 0.325917972393556354, 0.329440964264136438, 0.332998068761809096, 0.336589914028677717, + 0.340217149066780189, 0.343880444704502575, 0.347580494621637148, 0.351318016437483449, + 0.355093752866787626, 0.358908472948750001, 0.362762973354817997, 0.366658079781514379, + 0.370594648435146223, 0.374573567615902381, 0.378595759409581067, 0.382662181496010056, + 0.386773829084137932, 0.390931736984797384, 0.395136981833290435, 0.399390684475231350, + 0.403694012530530555, 0.408048183152032673, 0.412454465997161457, 0.416914186433003209, + 0.421428728997616908, 0.425999541143034677, 0.430628137288459167, 0.435316103215636907, + 0.440065100842354173, 0.444876873414548846, 0.449753251162755330, 0.454696157474615836, + 0.459707615642138023, 0.464789756250426511, 0.469944825283960310, 0.475175193037377708, + 0.480483363930454543, 0.485871987341885248, 0.491343869594032867, 0.496901987241549881, + 0.502549501841348056, 0.508289776410643213, 0.514126393814748894, 0.520063177368233931, + 0.526104213983620062, 0.532253880263043655, 0.538516872002862246, 0.544898237672440056, + 0.551403416540641733, 0.558038282262587892, 0.564809192912400615, 0.571723048664826150, + 0.578787358602845359, 0.586010318477268366, 0.593400901691733762, 0.600968966365232560, + 0.608725382079622346, 0.616682180915207878, 0.624852738703666200, 0.633251994214366398, + 0.641896716427266423, 0.650805833414571433, 0.660000841079000145, 0.669506316731925177, + 0.679350572264765806, 0.689566496117078431, 0.700192655082788606, 0.711274760805076456, + 0.722867659593572465, 0.735038092431424039, 0.747868621985195658, 0.761463388849896838, + 0.775956852040116218, 0.791527636972496285, 0.808421651523009044, 0.826993296643051101, + 0.847785500623990496, 0.871704332381204705, 0.900469929925747703, 0.938143680862176477, + 1.000000000000000000]; |