1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
use super::*;
mod float;
mod int;
pub use self::float::UniformFloat;
pub use self::int::UniformInt;
/// Helper trait specifies the concrete sampler for the sampling type.
pub trait SampleUniform: Sized {
/// The concrete distribution type used to sample from `Self`.
type Sampler: UniformSampler<Self>;
}
/// Error type returned from [`UniformSampler`] constructors.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum UniformError {
/// `low > high`, or equal in case of exclusive range.
EmptyRange,
/// Input or range `high - low` is non-finite. Not relevant to integer types.
NonFinite,
}
impl fmt::Display for UniformError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(match self {
UniformError::EmptyRange => "low > high (or equal if exclusive) in uniform distribution",
UniformError::NonFinite => "Non-finite range in uniform distribution",
})
}
}
#[cfg(feature = "std")]
impl std::error::Error for UniformError {}
/// Helper trait for constructing uniform samplers from inclusive and exclusive ranges.
pub trait UniformSampler<T>: Distribution<T> {
/// Creates a new instance which samples uniformly from the half-open range `[low, high)` (excluding high).
fn try_new(low: T, high: T) -> Result<Self, UniformError> where Self: Sized;
/// Creates a new instance which samples uniformly from the closed range `[low, high]` (inclusive).
fn try_new_inclusive(low: T, high: T) -> Result<Self, UniformError> where Self: Sized;
}
/// Sample values uniformly between two bounds.
///
/// Steps are taken to avoid bias which might be present in naive implementations;
/// for example `rand.next::<u8>() % 170` samples from the interval `[0, 170)` 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 within the given interval. It is a bug if an implementation returns a result outside the requested interval.
///
/// For one-off samples see also: [`Random::range`] for convenient samples directly from the `Rng`.
/// For more than one sample it is recommended to reuse the `Uniform` instance.
///
/// # Examples
///
/// ```
/// use urandom::distr::Uniform;
///
/// let between = Uniform::new(10, 10000);
/// let mut rand = urandom::new();
/// let mut sum = 0;
/// for _ in 0..1000 {
/// sum += rand.sample(&between);
/// }
/// println!("{sum}");
/// ```
///
/// # Custom implementations
///
/// Different types may have completely different uniform sampling implementations (such as the integers vs floating point types).
/// Start by creating a custom sampler struct which will later be linked to the `Uniform` type.
///
/// For your custom sampler implement [`Distribution`](Distribution) for your custom type and [`UniformSampler`](UniformSampler) to add constructors to it.
///
/// Once that's done you can specify that your custom type uses your custom sampler by implementing [`SampleUniform`](SampleUniform)
/// and pointing its associated [`Sampler`](SampleUniform::Sampler) type to your custom sampler.
///
/// ```
/// use urandom::{Distribution, Random, Rng};
/// use urandom::distr::{SampleUniform, UniformError, UniformFloat, UniformSampler};
///
/// // The custom type for which to implement uniform sampling.
/// struct MyF32(f32);
///
/// // The custom sampler for the type.
/// struct UniformMyF32(UniformFloat<f32>);
///
/// // Add constructors for your sampler.
/// impl UniformSampler<MyF32> for UniformMyF32 {
/// fn try_new(low: MyF32, high: MyF32) -> Result<Self, UniformError> {
/// UniformFloat::try_new(low.0, high.0).map(UniformMyF32)
/// }
/// fn try_new_inclusive(low: MyF32, high: MyF32) -> Result<Self, UniformError> {
/// UniformFloat::try_new_inclusive(low.0, high.0).map(UniformMyF32)
/// }
/// }
///
/// // Make it a Distribution.
/// impl Distribution<MyF32> for UniformMyF32 {
/// fn sample<R: Rng + ?Sized>(&self, rand: &mut Random<R>) -> MyF32 {
/// MyF32(self.0.sample(rand))
/// }
/// }
///
/// // Tell everyone where to find the uniform sampler for your type.
/// impl SampleUniform for MyF32 {
/// type Sampler = UniformMyF32;
/// }
///
/// // Now it can be used to generate random samples.
/// let mut rand = urandom::new();
/// let value = rand.range(MyF32(13.0)..MyF32(42.0));
/// assert!(value.0 >= 13.0 && value.0 < 42.0);
/// ```
#[derive(Copy, Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(bound(serialize = "T::Sampler: serde::Serialize")))]
#[cfg_attr(feature = "serde", serde(bound(deserialize = "T::Sampler: serde::Deserialize<'de>")))]
#[repr(transparent)]
pub struct Uniform<T: SampleUniform> {
#[cfg_attr(feature = "serde", serde(flatten))]
sampler: T::Sampler,
}
impl<T: SampleUniform> From<ops::Range<T>> for Uniform<T> {
#[track_caller]
#[inline]
fn from(range: ops::Range<T>) -> Uniform<T> {
Uniform { sampler: T::Sampler::try_new(range.start, range.end).unwrap() }
}
}
impl<T: SampleUniform> From<ops::RangeInclusive<T>> for Uniform<T> {
#[track_caller]
#[inline]
fn from(range: ops::RangeInclusive<T>) -> Uniform<T> {
let (start, end) = range.into_inner();
Uniform { sampler: T::Sampler::try_new_inclusive(start, end).unwrap() }
}
}
impl<T: SampleUniform> UniformSampler<T> for Uniform<T> {
#[inline]
fn try_new(low: T, high: T) -> Result<Self, UniformError> {
T::Sampler::try_new(low, high).map(|sampler| Uniform { sampler })
}
#[inline]
fn try_new_inclusive(low: T, high: T) -> Result<Self, UniformError> {
T::Sampler::try_new_inclusive(low, high).map(|sampler| Uniform { sampler })
}
}
impl<T: SampleUniform> Uniform<T> {
/// Creates a new instance which samples uniformly from the half-open range `[low, high)` (excluding high).
#[inline]
pub fn try_new(low: T, high: T) -> Result<Uniform<T>, UniformError> {
T::Sampler::try_new(low, high).map(|sampler| Uniform { sampler })
}
/// Creates a new instance which samples uniformly from the half-open range `[low, high)` (excluding high).
///
/// May panic if `low >= high`.
#[track_caller]
#[inline]
pub fn new(low: T, high: T) -> Uniform<T> {
let sampler = T::Sampler::try_new(low, high).unwrap();
Uniform { sampler }
}
/// Creates a new instance which samples uniformly from the closed range `[low, high]` (inclusive).
#[inline]
pub fn try_new_inclusive(low: T, high: T) -> Result<Uniform<T>, UniformError> {
T::Sampler::try_new_inclusive(low, high).map(|sampler| Uniform { sampler })
}
/// Creates a new instance which samples uniformly from the closed range `[low, high]` (inclusive).
///
/// May panic if `low > high`.
#[track_caller]
#[inline]
pub fn new_inclusive(low: T, high: T) -> Uniform<T> {
let sampler = T::Sampler::try_new_inclusive(low, high).unwrap();
Uniform { sampler }
}
}
impl<T: SampleUniform> Distribution<T> for Uniform<T> {
#[inline]
fn sample<R: Rng + ?Sized>(&self, rand: &mut Random<R>) -> T {
self.sampler.sample(rand)
}
}
#[cfg(test)]
mod tests;