/rust/registry/src/index.crates.io-1949cf8c6b5b557f/rand_distr-0.5.1/src/zeta.rs
Line | Count | Source |
1 | | // Copyright 2021 Developers of the Rand project. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
4 | | // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
5 | | // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your |
6 | | // option. This file may not be copied, modified, or distributed |
7 | | // except according to those terms. |
8 | | |
9 | | //! The Zeta distribution. |
10 | | |
11 | | use crate::{Distribution, StandardUniform}; |
12 | | use core::fmt; |
13 | | use num_traits::Float; |
14 | | use rand::{distr::OpenClosed01, Rng}; |
15 | | |
16 | | /// The [Zeta distribution](https://en.wikipedia.org/wiki/Zeta_distribution) `Zeta(s)`. |
17 | | /// |
18 | | /// The [Zeta distribution](https://en.wikipedia.org/wiki/Zeta_distribution) |
19 | | /// is a discrete probability distribution with parameter `s`. |
20 | | /// It is a special case of the [`Zipf`](crate::Zipf) distribution with `n = ∞`. |
21 | | /// It is also known as the discrete Pareto, Riemann-Zeta, Zipf, or Zipf–Estoup distribution. |
22 | | /// |
23 | | /// # Density function |
24 | | /// |
25 | | /// `f(k) = k^(-s) / ζ(s)` for `k >= 1`, where `ζ` is the |
26 | | /// [Riemann zeta function](https://en.wikipedia.org/wiki/Riemann_zeta_function). |
27 | | /// |
28 | | /// # Plot |
29 | | /// |
30 | | /// The following plot illustrates the zeta distribution for various values of `s`. |
31 | | /// |
32 | | ///  |
33 | | /// |
34 | | /// # Example |
35 | | /// ``` |
36 | | /// use rand::prelude::*; |
37 | | /// use rand_distr::Zeta; |
38 | | /// |
39 | | /// let val: f64 = rand::rng().sample(Zeta::new(1.5).unwrap()); |
40 | | /// println!("{}", val); |
41 | | /// ``` |
42 | | /// |
43 | | /// # Integer vs FP return type |
44 | | /// |
45 | | /// This implementation uses floating-point (FP) logic internally, which can |
46 | | /// potentially generate very large samples (exceeding e.g. `u64::MAX`). |
47 | | /// |
48 | | /// It is *safe* to cast such results to an integer type using `as` |
49 | | /// (e.g. `distr.sample(&mut rng) as u64`), since such casts are saturating |
50 | | /// (e.g. `2f64.powi(64) as u64 == u64::MAX`). It is up to the user to |
51 | | /// determine whether this potential loss of accuracy is acceptable |
52 | | /// (this determination may depend on the distribution's parameters). |
53 | | /// |
54 | | /// # Notes |
55 | | /// |
56 | | /// The zeta distribution has no upper limit. Sampled values may be infinite. |
57 | | /// In particular, a value of infinity might be returned for the following |
58 | | /// reasons: |
59 | | /// 1. it is the best representation in the type `F` of the actual sample. |
60 | | /// 2. to prevent infinite loops for very small `s`. |
61 | | /// |
62 | | /// # Implementation details |
63 | | /// |
64 | | /// We are using the algorithm from |
65 | | /// [Non-Uniform Random Variate Generation](https://doi.org/10.1007/978-1-4613-8643-8), |
66 | | /// Section 6.1, page 551. |
67 | | #[derive(Clone, Copy, Debug, PartialEq)] |
68 | | pub struct Zeta<F> |
69 | | where |
70 | | F: Float, |
71 | | StandardUniform: Distribution<F>, |
72 | | OpenClosed01: Distribution<F>, |
73 | | { |
74 | | s_minus_1: F, |
75 | | b: F, |
76 | | } |
77 | | |
78 | | /// Error type returned from [`Zeta::new`]. |
79 | | #[derive(Clone, Copy, Debug, PartialEq, Eq)] |
80 | | pub enum Error { |
81 | | /// `s <= 1` or `nan`. |
82 | | STooSmall, |
83 | | } |
84 | | |
85 | | impl fmt::Display for Error { |
86 | 0 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
87 | 0 | f.write_str(match self { |
88 | 0 | Error::STooSmall => "s <= 1 or is NaN in Zeta distribution", |
89 | | }) |
90 | 0 | } |
91 | | } |
92 | | |
93 | | #[cfg(feature = "std")] |
94 | | impl std::error::Error for Error {} |
95 | | |
96 | | impl<F> Zeta<F> |
97 | | where |
98 | | F: Float, |
99 | | StandardUniform: Distribution<F>, |
100 | | OpenClosed01: Distribution<F>, |
101 | | { |
102 | | /// Construct a new `Zeta` distribution with given `s` parameter. |
103 | | #[inline] |
104 | 0 | pub fn new(s: F) -> Result<Zeta<F>, Error> { |
105 | 0 | if !(s > F::one()) { |
106 | 0 | return Err(Error::STooSmall); |
107 | 0 | } |
108 | 0 | let s_minus_1 = s - F::one(); |
109 | 0 | let two = F::one() + F::one(); |
110 | 0 | Ok(Zeta { |
111 | 0 | s_minus_1, |
112 | 0 | b: two.powf(s_minus_1), |
113 | 0 | }) |
114 | 0 | } |
115 | | } |
116 | | |
117 | | impl<F> Distribution<F> for Zeta<F> |
118 | | where |
119 | | F: Float, |
120 | | StandardUniform: Distribution<F>, |
121 | | OpenClosed01: Distribution<F>, |
122 | | { |
123 | | #[inline] |
124 | 0 | fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> F { |
125 | | loop { |
126 | 0 | let u = rng.sample(OpenClosed01); |
127 | 0 | let x = u.powf(-F::one() / self.s_minus_1).floor(); |
128 | 0 | debug_assert!(x >= F::one()); |
129 | 0 | if x.is_infinite() { |
130 | | // For sufficiently small `s`, `x` will always be infinite, |
131 | | // which is rejected, resulting in an infinite loop. We avoid |
132 | | // this by always returning infinity instead. |
133 | 0 | return x; |
134 | 0 | } |
135 | | |
136 | 0 | let t = (F::one() + F::one() / x).powf(self.s_minus_1); |
137 | | |
138 | 0 | let v = rng.sample(StandardUniform); |
139 | 0 | if v * x * (t - F::one()) * self.b <= t * (self.b - F::one()) { |
140 | 0 | return x; |
141 | 0 | } |
142 | | } |
143 | 0 | } |
144 | | } |
145 | | |
146 | | #[cfg(test)] |
147 | | mod tests { |
148 | | use super::*; |
149 | | |
150 | | fn test_samples<F: Float + fmt::Debug, D: Distribution<F>>(distr: D, zero: F, expected: &[F]) { |
151 | | let mut rng = crate::test::rng(213); |
152 | | let mut buf = [zero; 4]; |
153 | | for x in &mut buf { |
154 | | *x = rng.sample(&distr); |
155 | | } |
156 | | assert_eq!(buf, expected); |
157 | | } |
158 | | |
159 | | #[test] |
160 | | #[should_panic] |
161 | | fn zeta_invalid() { |
162 | | Zeta::new(1.).unwrap(); |
163 | | } |
164 | | |
165 | | #[test] |
166 | | #[should_panic] |
167 | | fn zeta_nan() { |
168 | | Zeta::new(f64::NAN).unwrap(); |
169 | | } |
170 | | |
171 | | #[test] |
172 | | fn zeta_sample() { |
173 | | let a = 2.0; |
174 | | let d = Zeta::new(a).unwrap(); |
175 | | let mut rng = crate::test::rng(1); |
176 | | for _ in 0..1000 { |
177 | | let r = d.sample(&mut rng); |
178 | | assert!(r >= 1.); |
179 | | } |
180 | | } |
181 | | |
182 | | #[test] |
183 | | fn zeta_small_a() { |
184 | | let a = 1. + 1e-15; |
185 | | let d = Zeta::new(a).unwrap(); |
186 | | let mut rng = crate::test::rng(2); |
187 | | for _ in 0..1000 { |
188 | | let r = d.sample(&mut rng); |
189 | | assert!(r >= 1.); |
190 | | } |
191 | | } |
192 | | |
193 | | #[test] |
194 | | fn zeta_value_stability() { |
195 | | test_samples(Zeta::new(1.5).unwrap(), 0f32, &[1.0, 2.0, 1.0, 1.0]); |
196 | | test_samples(Zeta::new(2.0).unwrap(), 0f64, &[2.0, 1.0, 1.0, 1.0]); |
197 | | } |
198 | | |
199 | | #[test] |
200 | | fn zeta_distributions_can_be_compared() { |
201 | | assert_eq!(Zeta::new(1.0), Zeta::new(1.0)); |
202 | | } |
203 | | } |