1 // Copyright 2018 Developers of the Rand project.
2 // Copyright 2017 The Rust Project Developers.
4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5 // https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
7 // option. This file may not be copied, modified, or distributed
8 // except according to those terms.
10 //! A distribution uniformly sampling numbers within a given range.
12 //! [`Uniform`] is the standard distribution to sample uniformly from a range;
13 //! e.g. `Uniform::new_inclusive(1, 6)` can sample integers from 1 to 6, like a
14 //! standard die. [`Rng::gen_range`] supports any type supported by
17 //! This distribution is provided with support for several primitive types
18 //! (all integer and floating-point types) as well as [`std::time::Duration`],
19 //! and supports extension to user-defined types via a type-specific *back-end*
22 //! The types [`UniformInt`], [`UniformFloat`] and [`UniformDuration`] are the
23 //! back-ends supporting sampling from primitive integer and floating-point
24 //! ranges as well as from [`std::time::Duration`]; these types do not normally
25 //! need to be used directly (unless implementing a derived back-end).
30 //! use rand::{Rng, thread_rng};
31 //! use rand::distributions::Uniform;
33 //! let mut rng = thread_rng();
34 //! let side = Uniform::new(-10.0, 10.0);
36 //! // sample between 1 and 10 points
37 //! for _ in 0..rng.gen_range(1, 11) {
38 //! // sample a point from the square with sides -10 - 10 in two dimensions
39 //! let (x, y) = (rng.sample(side), rng.sample(side));
40 //! println!("Point: {}, {}", x, y);
44 //! # Extending `Uniform` to support a custom type
46 //! To extend [`Uniform`] to support your own types, write a back-end which
47 //! implements the [`UniformSampler`] trait, then implement the [`SampleUniform`]
48 //! helper trait to "register" your back-end. See the `MyF32` example below.
50 //! At a minimum, the back-end needs to store any parameters needed for sampling
51 //! (e.g. the target range) and implement `new`, `new_inclusive` and `sample`.
52 //! Those methods should include an assert to check the range is valid (i.e.
53 //! `low < high`). The example below merely wraps another back-end.
55 //! The `new`, `new_inclusive` and `sample_single` functions use arguments of
56 //! type SampleBorrow<X> in order to support passing in values by reference or
57 //! by value. In the implementation of these functions, you can choose to
58 //! simply use the reference returned by [`SampleBorrow::borrow`], or you can choose
59 //! to copy or clone the value, whatever is appropriate for your type.
62 //! use rand::prelude::*;
63 //! use rand::distributions::uniform::{Uniform, SampleUniform,
64 //! UniformSampler, UniformFloat, SampleBorrow};
66 //! struct MyF32(f32);
68 //! #[derive(Clone, Copy, Debug)]
69 //! struct UniformMyF32(UniformFloat<f32>);
71 //! impl UniformSampler for UniformMyF32 {
73 //! fn new<B1, B2>(low: B1, high: B2) -> Self
74 //! where B1: SampleBorrow<Self::X> + Sized,
75 //! B2: SampleBorrow<Self::X> + Sized
77 //! UniformMyF32(UniformFloat::<f32>::new(low.borrow().0, high.borrow().0))
79 //! fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self
80 //! where B1: SampleBorrow<Self::X> + Sized,
81 //! B2: SampleBorrow<Self::X> + Sized
83 //! UniformSampler::new(low, high)
85 //! fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
86 //! MyF32(self.0.sample(rng))
90 //! impl SampleUniform for MyF32 {
91 //! type Sampler = UniformMyF32;
94 //! let (low, high) = (MyF32(17.0f32), MyF32(22.0f32));
95 //! let uniform = Uniform::new(low, high);
96 //! let x = uniform.sample(&mut thread_rng());
99 //! [`SampleUniform`]: crate::distributions::uniform::SampleUniform
100 //! [`UniformSampler`]: crate::distributions::uniform::UniformSampler
101 //! [`UniformInt`]: crate::distributions::uniform::UniformInt
102 //! [`UniformFloat`]: crate::distributions::uniform::UniformFloat
103 //! [`UniformDuration`]: crate::distributions::uniform::UniformDuration
104 //! [`SampleBorrow::borrow`]: crate::distributions::uniform::SampleBorrow::borrow
106 #[cfg(not(feature = "std"))] use core::time::Duration;
107 #[cfg(feature = "std")] use std::time::Duration;
109 use crate::distributions
::float
::IntoFloat
;
110 use crate::distributions
::utils
::{BoolAsSIMD, FloatAsSIMD, FloatSIMDUtils, WideningMultiply}
;
111 use crate::distributions
::Distribution
;
114 #[cfg(not(feature = "std"))]
115 #[allow(unused_imports)] // rustc doesn't detect that this is actually used
116 use crate::distributions
::utils
::Float
;
119 #[cfg(feature = "simd_support")] use packed_simd::*;
121 /// Sample values uniformly between two bounds.
123 /// [`Uniform::new`] and [`Uniform::new_inclusive`] construct a uniform
124 /// distribution sampling from the given range; these functions may do extra
125 /// work up front to make sampling of multiple values faster.
127 /// When sampling from a constant range, many calculations can happen at
128 /// compile-time and all methods should be fast; for floating-point ranges and
129 /// the full range of integer types this should have comparable performance to
130 /// the `Standard` distribution.
132 /// Steps are taken to avoid bias which might be present in naive
133 /// implementations; for example `rng.gen::<u8>() % 170` samples from the range
134 /// `[0, 169]` but is twice as likely to select numbers less than 85 than other
135 /// values. Further, the implementations here give more weight to the high-bits
136 /// generated by the RNG than the low bits, since with some RNGs the low-bits
137 /// are of lower quality than the high bits.
139 /// Implementations must sample in `[low, high)` range for
140 /// `Uniform::new(low, high)`, i.e., excluding `high`. In particular care must
141 /// be taken to ensure that rounding never results values `< low` or `>= high`.
146 /// use rand::distributions::{Distribution, Uniform};
149 /// let between = Uniform::from(10..10000);
150 /// let mut rng = rand::thread_rng();
152 /// for _ in 0..1000 {
153 /// sum += between.sample(&mut rng);
155 /// println!("{}", sum);
159 /// [`new`]: Uniform::new
160 /// [`new_inclusive`]: Uniform::new_inclusive
161 #[derive(Clone, Copy, Debug)]
162 pub struct Uniform
<X
: SampleUniform
>(X
::Sampler
);
164 impl<X
: SampleUniform
> Uniform
<X
> {
165 /// Create a new `Uniform` instance which samples uniformly from the half
166 /// open range `[low, high)` (excluding `high`). Panics if `low >= high`.
167 pub fn new
<B1
, B2
>(low
: B1
, high
: B2
) -> Uniform
<X
>
169 B1
: SampleBorrow
<X
> + Sized
,
170 B2
: SampleBorrow
<X
> + Sized
,
172 Uniform(X
::Sampler
::new(low
, high
))
175 /// Create a new `Uniform` instance which samples uniformly from the closed
176 /// range `[low, high]` (inclusive). Panics if `low > high`.
177 pub fn new_inclusive
<B1
, B2
>(low
: B1
, high
: B2
) -> Uniform
<X
>
179 B1
: SampleBorrow
<X
> + Sized
,
180 B2
: SampleBorrow
<X
> + Sized
,
182 Uniform(X
::Sampler
::new_inclusive(low
, high
))
186 impl<X
: SampleUniform
> Distribution
<X
> for Uniform
<X
> {
187 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> X
{
192 /// Helper trait for creating objects using the correct implementation of
193 /// [`UniformSampler`] for the sampling type.
195 /// See the [module documentation] on how to implement [`Uniform`] range
196 /// sampling for a custom type.
198 /// [module documentation]: crate::distributions::uniform
199 pub trait SampleUniform
: Sized
{
200 /// The `UniformSampler` implementation supporting type `X`.
201 type Sampler
: UniformSampler
<X
= Self>;
204 /// Helper trait handling actual uniform sampling.
206 /// See the [module documentation] on how to implement [`Uniform`] range
207 /// sampling for a custom type.
209 /// Implementation of [`sample_single`] is optional, and is only useful when
210 /// the implementation can be faster than `Self::new(low, high).sample(rng)`.
212 /// [module documentation]: crate::distributions::uniform
213 /// [`sample_single`]: UniformSampler::sample_single
214 pub trait UniformSampler
: Sized
{
215 /// The type sampled by this implementation.
218 /// Construct self, with inclusive lower bound and exclusive upper bound
221 /// Usually users should not call this directly but instead use
222 /// `Uniform::new`, which asserts that `low < high` before calling this.
223 fn new
<B1
, B2
>(low
: B1
, high
: B2
) -> Self
225 B1
: SampleBorrow
<Self::X
> + Sized
,
226 B2
: SampleBorrow
<Self::X
> + Sized
;
228 /// Construct self, with inclusive bounds `[low, high]`.
230 /// Usually users should not call this directly but instead use
231 /// `Uniform::new_inclusive`, which asserts that `low <= high` before
233 fn new_inclusive
<B1
, B2
>(low
: B1
, high
: B2
) -> Self
235 B1
: SampleBorrow
<Self::X
> + Sized
,
236 B2
: SampleBorrow
<Self::X
> + Sized
;
239 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Self::X
;
241 /// Sample a single value uniformly from a range with inclusive lower bound
242 /// and exclusive upper bound `[low, high)`.
244 /// By default this is implemented using
245 /// `UniformSampler::new(low, high).sample(rng)`. However, for some types
246 /// more optimal implementations for single usage may be provided via this
247 /// method (which is the case for integers and floats).
248 /// Results may not be identical.
250 /// Note that to use this method in a generic context, the type needs to be
251 /// retrieved via `SampleUniform::Sampler` as follows:
253 /// use rand::{thread_rng, distributions::uniform::{SampleUniform, UniformSampler}};
254 /// # #[allow(unused)]
255 /// fn sample_from_range<T: SampleUniform>(lb: T, ub: T) -> T {
256 /// let mut rng = thread_rng();
257 /// <T as SampleUniform>::Sampler::sample_single(lb, ub, &mut rng)
260 fn sample_single
<R
: Rng
+ ?Sized
, B1
, B2
>(low
: B1
, high
: B2
, rng
: &mut R
) -> Self::X
262 B1
: SampleBorrow
<Self::X
> + Sized
,
263 B2
: SampleBorrow
<Self::X
> + Sized
,
265 let uniform
: Self = UniformSampler
::new(low
, high
);
270 impl<X
: SampleUniform
> From
<::core
::ops
::Range
<X
>> for Uniform
<X
> {
271 fn from(r
: ::core
::ops
::Range
<X
>) -> Uniform
<X
> {
272 Uniform
::new(r
.start
, r
.end
)
276 impl<X
: SampleUniform
> From
<::core
::ops
::RangeInclusive
<X
>> for Uniform
<X
> {
277 fn from(r
: ::core
::ops
::RangeInclusive
<X
>) -> Uniform
<X
> {
278 Uniform
::new_inclusive(r
.start(), r
.end())
282 /// Helper trait similar to [`Borrow`] but implemented
283 /// only for SampleUniform and references to SampleUniform in
284 /// order to resolve ambiguity issues.
286 /// [`Borrow`]: std::borrow::Borrow
287 pub trait SampleBorrow
<Borrowed
> {
288 /// Immutably borrows from an owned value. See [`Borrow::borrow`]
290 /// [`Borrow::borrow`]: std::borrow::Borrow::borrow
291 fn borrow(&self) -> &Borrowed
;
293 impl<Borrowed
> SampleBorrow
<Borrowed
> for Borrowed
294 where Borrowed
: SampleUniform
297 fn borrow(&self) -> &Borrowed
{
301 impl<'a
, Borrowed
> SampleBorrow
<Borrowed
> for &'a Borrowed
302 where Borrowed
: SampleUniform
305 fn borrow(&self) -> &Borrowed
{
310 ////////////////////////////////////////////////////////////////////////////////
312 // What follows are all back-ends.
315 /// The back-end implementing [`UniformSampler`] for integer types.
317 /// Unless you are implementing [`UniformSampler`] for your own type, this type
318 /// should not be used directly, use [`Uniform`] instead.
320 /// # Implementation notes
322 /// For simplicity, we use the same generic struct `UniformInt<X>` for all
323 /// integer types `X`. This gives us only one field type, `X`; to store unsigned
324 /// values of this size, we take use the fact that these conversions are no-ops.
326 /// For a closed range, the number of possible numbers we should generate is
327 /// `range = (high - low + 1)`. To avoid bias, we must ensure that the size of
328 /// our sample space, `zone`, is a multiple of `range`; other values must be
329 /// rejected (by replacing with a new random sample).
331 /// As a special case, we use `range = 0` to represent the full range of the
332 /// result type (i.e. for `new_inclusive($ty::MIN, $ty::MAX)`).
334 /// The optimum `zone` is the largest product of `range` which fits in our
335 /// (unsigned) target type. We calculate this by calculating how many numbers we
336 /// must reject: `reject = (MAX + 1) % range = (MAX - range + 1) % range`. Any (large)
337 /// product of `range` will suffice, thus in `sample_single` we multiply by a
338 /// power of 2 via bit-shifting (faster but may cause more rejections).
340 /// The smallest integer PRNGs generate is `u32`. For 8- and 16-bit outputs we
341 /// use `u32` for our `zone` and samples (because it's not slower and because
342 /// it reduces the chance of having to reject a sample). In this case we cannot
343 /// store `zone` in the target type since it is too large, however we know
344 /// `ints_to_reject < range <= $unsigned::MAX`.
346 /// An alternative to using a modulus is widening multiply: After a widening
347 /// multiply by `range`, the result is in the high word. Then comparing the low
348 /// word against `zone` makes sure our distribution is uniform.
349 #[derive(Clone, Copy, Debug)]
350 pub struct UniformInt
<X
> {
353 z
: X
, // either ints_to_reject or zone depending on implementation
356 macro_rules
! uniform_int_impl
{
357 ($ty
:ty
, $unsigned
:ident
, $u_large
:ident
) => {
358 impl SampleUniform
for $ty
{
359 type Sampler
= UniformInt
<$ty
>;
362 impl UniformSampler
for UniformInt
<$ty
> {
363 // We play free and fast with unsigned vs signed here
364 // (when $ty is signed), but that's fine, since the
365 // contract of this macro is for $ty and $unsigned to be
366 // "bit-equal", so casting between them is a no-op.
370 #[inline] // if the range is constant, this helps LLVM to do the
371 // calculations at compile-time.
372 fn new
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
374 B1
: SampleBorrow
<Self::X
> + Sized
,
375 B2
: SampleBorrow
<Self::X
> + Sized
,
377 let low
= *low_b
.borrow();
378 let high
= *high_b
.borrow();
379 assert
!(low
< high
, "Uniform::new called with `low >= high`");
380 UniformSampler
::new_inclusive(low
, high
- 1)
383 #[inline] // if the range is constant, this helps LLVM to do the
384 // calculations at compile-time.
385 fn new_inclusive
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
387 B1
: SampleBorrow
<Self::X
> + Sized
,
388 B2
: SampleBorrow
<Self::X
> + Sized
,
390 let low
= *low_b
.borrow();
391 let high
= *high_b
.borrow();
394 "Uniform::new_inclusive called with `low > high`"
396 let unsigned_max
= ::core
::$u_large
::MAX
;
398 let range
= high
.wrapping_sub(low
).wrapping_add(1) as $unsigned
;
399 let ints_to_reject
= if range
> 0 {
400 let range
= $u_large
::from(range
);
401 (unsigned_max
- range
+ 1) % range
408 // These are really $unsigned values, but store as $ty:
410 z
: ints_to_reject
as $unsigned
as $ty
,
414 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Self::X
{
415 let range
= self.range
as $unsigned
as $u_large
;
417 let unsigned_max
= ::core
::$u_large
::MAX
;
418 let zone
= unsigned_max
- (self.z
as $unsigned
as $u_large
);
420 let v
: $u_large
= rng
.gen();
421 let (hi
, lo
) = v
.wmul(range
);
423 return self.low
.wrapping_add(hi
as $ty
);
427 // Sample from the entire integer range.
432 fn sample_single
<R
: Rng
+ ?Sized
, B1
, B2
>(low_b
: B1
, high_b
: B2
, rng
: &mut R
) -> Self::X
434 B1
: SampleBorrow
<Self::X
> + Sized
,
435 B2
: SampleBorrow
<Self::X
> + Sized
,
437 let low
= *low_b
.borrow();
438 let high
= *high_b
.borrow();
439 assert
!(low
< high
, "UniformSampler::sample_single: low >= high");
440 let range
= high
.wrapping_sub(low
) as $unsigned
as $u_large
;
441 let zone
= if ::core
::$unsigned
::MAX
<= ::core
::u16::MAX
as $unsigned
{
442 // Using a modulus is faster than the approximation for
443 // i8 and i16. I suppose we trade the cost of one
444 // modulus for near-perfect branch prediction.
445 let unsigned_max
: $u_large
= ::core
::$u_large
::MAX
;
446 let ints_to_reject
= (unsigned_max
- range
+ 1) % range
;
447 unsigned_max
- ints_to_reject
449 // conservative but fast approximation. `- 1` is necessary to allow the
450 // same comparison without bias.
451 (range
<< range
.leading_zeros()).wrapping_sub(1)
455 let v
: $u_large
= rng
.gen();
456 let (hi
, lo
) = v
.wmul(range
);
458 return low
.wrapping_add(hi
as $ty
);
466 uniform_int_impl
! { i8, u8, u32 }
467 uniform_int_impl
! { i16, u16, u32 }
468 uniform_int_impl
! { i32, u32, u32 }
469 uniform_int_impl
! { i64, u64, u64 }
470 #[cfg(not(target_os = "emscripten"))]
471 uniform_int_impl
! { i128, u128, u128 }
472 uniform_int_impl
! { isize, usize, usize }
473 uniform_int_impl
! { u8, u8, u32 }
474 uniform_int_impl
! { u16, u16, u32 }
475 uniform_int_impl
! { u32, u32, u32 }
476 uniform_int_impl
! { u64, u64, u64 }
477 uniform_int_impl
! { usize, usize, usize }
478 #[cfg(not(target_os = "emscripten"))]
479 uniform_int_impl
! { u128, u128, u128 }
481 #[cfg(all(feature = "simd_support", feature = "nightly"))]
482 macro_rules
! uniform_simd_int_impl
{
483 ($ty
:ident
, $unsigned
:ident
, $u_scalar
:ident
) => {
484 // The "pick the largest zone that can fit in an `u32`" optimization
485 // is less useful here. Multiple lanes complicate things, we don't
486 // know the PRNG's minimal output size, and casting to a larger vector
487 // is generally a bad idea for SIMD performance. The user can still
488 // implement it manually.
490 // TODO: look into `Uniform::<u32x4>::new(0u32, 100)` functionality
491 // perhaps `impl SampleUniform for $u_scalar`?
492 impl SampleUniform
for $ty
{
493 type Sampler
= UniformInt
<$ty
>;
496 impl UniformSampler
for UniformInt
<$ty
> {
499 #[inline] // if the range is constant, this helps LLVM to do the
500 // calculations at compile-time.
501 fn new
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
502 where B1
: SampleBorrow
<Self::X
> + Sized
,
503 B2
: SampleBorrow
<Self::X
> + Sized
505 let low
= *low_b
.borrow();
506 let high
= *high_b
.borrow();
507 assert
!(low
.lt(high
).all(), "Uniform::new called with `low >= high`");
508 UniformSampler
::new_inclusive(low
, high
- 1)
511 #[inline] // if the range is constant, this helps LLVM to do the
512 // calculations at compile-time.
513 fn new_inclusive
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
514 where B1
: SampleBorrow
<Self::X
> + Sized
,
515 B2
: SampleBorrow
<Self::X
> + Sized
517 let low
= *low_b
.borrow();
518 let high
= *high_b
.borrow();
519 assert
!(low
.le(high
).all(),
520 "Uniform::new_inclusive called with `low > high`");
521 let unsigned_max
= ::core
::$u_scalar
::MAX
;
523 // NOTE: these may need to be replaced with explicitly
524 // wrapping operations if `packed_simd` changes
525 let range
: $unsigned
= ((high
- low
) + 1).cast();
526 // `% 0` will panic at runtime.
527 let not_full_range
= range
.gt($unsigned
::splat(0));
528 // replacing 0 with `unsigned_max` allows a faster `select`
530 let modulo
= not_full_range
.select(range
, $unsigned
::splat(unsigned_max
));
532 let ints_to_reject
= (unsigned_max
- range
+ 1) % modulo
;
533 // When `range` is 0, `lo` of `v.wmul(range)` will always be
534 // zero which means only one sample is needed.
535 let zone
= unsigned_max
- ints_to_reject
;
539 // These are really $unsigned values, but store as $ty:
545 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Self::X
{
546 let range
: $unsigned
= self.range
.cast();
547 let zone
: $unsigned
= self.z
.cast();
549 // This might seem very slow, generating a whole new
550 // SIMD vector for every sample rejection. For most uses
551 // though, the chance of rejection is small and provides good
552 // general performance. With multiple lanes, that chance is
553 // multiplied. To mitigate this, we replace only the lanes of
554 // the vector which fail, iteratively reducing the chance of
555 // rejection. The replacement method does however add a little
556 // overhead. Benchmarking or calculating probabilities might
557 // reveal contexts where this replacement method is slower.
558 let mut v
: $unsigned
= rng
.gen();
560 let (hi
, lo
) = v
.wmul(range
);
561 let mask
= lo
.le(zone
);
563 let hi
: $ty
= hi
.cast();
565 let result
= self.low
+ hi
;
566 // `select` here compiles to a blend operation
567 // When `range.eq(0).none()` the compare and blend
568 // operations are avoided.
569 let v
: $ty
= v
.cast();
570 return range
.gt($unsigned
::splat(0)).select(result
, v
);
572 // Replace only the failing lanes
573 v
= mask
.select(v
, rng
.gen());
579 // bulk implementation
580 ($
(($unsigned
:ident
, $signed
:ident
),)+ $u_scalar
:ident
) => {
582 uniform_simd_int_impl
!($unsigned
, $unsigned
, $u_scalar
);
583 uniform_simd_int_impl
!($signed
, $unsigned
, $u_scalar
);
588 #[cfg(all(feature = "simd_support", feature = "nightly"))]
589 uniform_simd_int_impl
! {
596 #[cfg(all(feature = "simd_support", feature = "nightly"))]
597 uniform_simd_int_impl
! {
605 #[cfg(all(feature = "simd_support", feature = "nightly"))]
606 uniform_simd_int_impl
! {
615 #[cfg(all(feature = "simd_support", feature = "nightly"))]
616 uniform_simd_int_impl
! {
627 /// The back-end implementing [`UniformSampler`] for floating-point types.
629 /// Unless you are implementing [`UniformSampler`] for your own type, this type
630 /// should not be used directly, use [`Uniform`] instead.
632 /// # Implementation notes
634 /// Instead of generating a float in the `[0, 1)` range using [`Standard`], the
635 /// `UniformFloat` implementation converts the output of an PRNG itself. This
636 /// way one or two steps can be optimized out.
638 /// The floats are first converted to a value in the `[1, 2)` interval using a
639 /// transmute-based method, and then mapped to the expected range with a
640 /// multiply and addition. Values produced this way have what equals 23 bits of
641 /// random digits for an `f32`, and 52 for an `f64`.
643 /// [`new`]: UniformSampler::new
644 /// [`new_inclusive`]: UniformSampler::new_inclusive
645 /// [`Standard`]: crate::distributions::Standard
646 #[derive(Clone, Copy, Debug)]
647 pub struct UniformFloat
<X
> {
652 macro_rules
! uniform_float_impl
{
653 ($ty
:ty
, $uty
:ident
, $f_scalar
:ident
, $u_scalar
:ident
, $bits_to_discard
:expr
) => {
654 impl SampleUniform
for $ty
{
655 type Sampler
= UniformFloat
<$ty
>;
658 impl UniformSampler
for UniformFloat
<$ty
> {
661 fn new
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
663 B1
: SampleBorrow
<Self::X
> + Sized
,
664 B2
: SampleBorrow
<Self::X
> + Sized
,
666 let low
= *low_b
.borrow();
667 let high
= *high_b
.borrow();
668 assert
!(low
.all_lt(high
), "Uniform::new called with `low >= high`");
670 low
.all_finite() && high
.all_finite(),
671 "Uniform::new called with non-finite boundaries"
673 let max_rand
= <$ty
>::splat(
674 (::core
::$u_scalar
::MAX
>> $bits_to_discard
).into_float_with_exponent(0) - 1.0,
677 let mut scale
= high
- low
;
680 let mask
= (scale
* max_rand
+ low
).ge_mask(high
);
684 scale
= scale
.decrease_masked(mask
);
687 debug_assert
!(<$ty
>::splat(0.0).all_le(scale
));
689 UniformFloat { low, scale }
692 fn new_inclusive
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
694 B1
: SampleBorrow
<Self::X
> + Sized
,
695 B2
: SampleBorrow
<Self::X
> + Sized
,
697 let low
= *low_b
.borrow();
698 let high
= *high_b
.borrow();
701 "Uniform::new_inclusive called with `low > high`"
704 low
.all_finite() && high
.all_finite(),
705 "Uniform::new_inclusive called with non-finite boundaries"
707 let max_rand
= <$ty
>::splat(
708 (::core
::$u_scalar
::MAX
>> $bits_to_discard
).into_float_with_exponent(0) - 1.0,
711 let mut scale
= (high
- low
) / max_rand
;
714 let mask
= (scale
* max_rand
+ low
).gt_mask(high
);
718 scale
= scale
.decrease_masked(mask
);
721 debug_assert
!(<$ty
>::splat(0.0).all_le(scale
));
723 UniformFloat { low, scale }
726 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Self::X
{
727 // Generate a value in the range [1, 2)
728 let value1_2
= (rng
.gen
::<$uty
>() >> $bits_to_discard
).into_float_with_exponent(0);
730 // Get a value in the range [0, 1) in order to avoid
731 // overflowing into infinity when multiplying with scale
732 let value0_1
= value1_2
- 1.0;
734 // We don't use `f64::mul_add`, because it is not available with
735 // `no_std`. Furthermore, it is slower for some targets (but
736 // faster for others). However, the order of multiplication and
737 // addition is important, because on some platforms (e.g. ARM)
738 // it will be optimized to a single (non-FMA) instruction.
739 value0_1
* self.scale
+ self.low
743 fn sample_single
<R
: Rng
+ ?Sized
, B1
, B2
>(low_b
: B1
, high_b
: B2
, rng
: &mut R
) -> Self::X
745 B1
: SampleBorrow
<Self::X
> + Sized
,
746 B2
: SampleBorrow
<Self::X
> + Sized
,
748 let low
= *low_b
.borrow();
749 let high
= *high_b
.borrow();
752 "UniformSampler::sample_single: low >= high"
754 let mut scale
= high
- low
;
757 // Generate a value in the range [1, 2)
759 (rng
.gen
::<$uty
>() >> $bits_to_discard
).into_float_with_exponent(0);
761 // Get a value in the range [0, 1) in order to avoid
762 // overflowing into infinity when multiplying with scale
763 let value0_1
= value1_2
- 1.0;
765 // Doing multiply before addition allows some architectures
766 // to use a single instruction.
767 let res
= value0_1
* scale
+ low
;
769 debug_assert
!(low
.all_le(res
) || !scale
.all_finite());
770 if res
.all_lt(high
) {
774 // This handles a number of edge cases.
775 // * `low` or `high` is NaN. In this case `scale` and
776 // `res` are going to end up as NaN.
777 // * `low` is negative infinity and `high` is finite.
778 // `scale` is going to be infinite and `res` will be
780 // * `high` is positive infinity and `low` is finite.
781 // `scale` is going to be infinite and `res` will
782 // be infinite or NaN (if value0_1 is 0).
783 // * `low` is negative infinity and `high` is positive
784 // infinity. `scale` will be infinite and `res` will
786 // * `low` and `high` are finite, but `high - low`
787 // overflows to infinite. `scale` will be infinite
788 // and `res` will be infinite or NaN (if value0_1 is 0).
789 // So if `high` or `low` are non-finite, we are guaranteed
790 // to fail the `res < high` check above and end up here.
792 // While we technically should check for non-finite `low`
793 // and `high` before entering the loop, by doing the checks
794 // here instead, we allow the common case to avoid these
795 // checks. But we are still guaranteed that if `low` or
796 // `high` are non-finite we'll end up here and can do the
797 // appropriate checks.
799 // Likewise `high - low` overflowing to infinity is also
800 // rare, so handle it here after the common case.
801 let mask
= !scale
.finite_mask();
804 low
.all_finite() && high
.all_finite(),
805 "Uniform::sample_single: low and high must be finite"
807 scale
= scale
.decrease_masked(mask
);
815 uniform_float_impl
! { f32, u32, f32, u32, 32 - 23 }
816 uniform_float_impl
! { f64, u64, f64, u64, 64 - 52 }
818 #[cfg(feature = "simd_support")]
819 uniform_float_impl
! { f32x2, u32x2, f32, u32, 32 - 23 }
820 #[cfg(feature = "simd_support")]
821 uniform_float_impl
! { f32x4, u32x4, f32, u32, 32 - 23 }
822 #[cfg(feature = "simd_support")]
823 uniform_float_impl
! { f32x8, u32x8, f32, u32, 32 - 23 }
824 #[cfg(feature = "simd_support")]
825 uniform_float_impl
! { f32x16, u32x16, f32, u32, 32 - 23 }
827 #[cfg(feature = "simd_support")]
828 uniform_float_impl
! { f64x2, u64x2, f64, u64, 64 - 52 }
829 #[cfg(feature = "simd_support")]
830 uniform_float_impl
! { f64x4, u64x4, f64, u64, 64 - 52 }
831 #[cfg(feature = "simd_support")]
832 uniform_float_impl
! { f64x8, u64x8, f64, u64, 64 - 52 }
835 /// The back-end implementing [`UniformSampler`] for `Duration`.
837 /// Unless you are implementing [`UniformSampler`] for your own types, this type
838 /// should not be used directly, use [`Uniform`] instead.
839 #[derive(Clone, Copy, Debug)]
840 pub struct UniformDuration
{
841 mode
: UniformDurationMode
,
845 #[derive(Debug, Copy, Clone)]
846 enum UniformDurationMode
{
861 impl SampleUniform
for Duration
{
862 type Sampler
= UniformDuration
;
865 impl UniformSampler
for UniformDuration
{
869 fn new
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
871 B1
: SampleBorrow
<Self::X
> + Sized
,
872 B2
: SampleBorrow
<Self::X
> + Sized
,
874 let low
= *low_b
.borrow();
875 let high
= *high_b
.borrow();
876 assert
!(low
< high
, "Uniform::new called with `low >= high`");
877 UniformDuration
::new_inclusive(low
, high
- Duration
::new(0, 1))
881 fn new_inclusive
<B1
, B2
>(low_b
: B1
, high_b
: B2
) -> Self
883 B1
: SampleBorrow
<Self::X
> + Sized
,
884 B2
: SampleBorrow
<Self::X
> + Sized
,
886 let low
= *low_b
.borrow();
887 let high
= *high_b
.borrow();
890 "Uniform::new_inclusive called with `low > high`"
893 let low_s
= low
.as_secs();
894 let low_n
= low
.subsec_nanos();
895 let mut high_s
= high
.as_secs();
896 let mut high_n
= high
.subsec_nanos();
900 high_n
+= 1_000_000_000;
903 let mode
= if low_s
== high_s
{
904 UniformDurationMode
::Small
{
906 nanos
: Uniform
::new_inclusive(low_n
, high_n
),
910 .checked_mul(1_000_000_000)
911 .and_then(|n
| n
.checked_add(u64::from(high_n
)));
913 if let Some(higher_bound
) = max
{
914 let lower_bound
= low_s
* 1_000_000_000 + u64::from(low_n
);
915 UniformDurationMode
::Medium
{
916 nanos
: Uniform
::new_inclusive(lower_bound
, higher_bound
),
919 // An offset is applied to simplify generation of nanoseconds
920 let max_nanos
= high_n
- low_n
;
921 UniformDurationMode
::Large
{
924 secs
: Uniform
::new_inclusive(low_s
, high_s
),
935 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Duration
{
937 UniformDurationMode
::Small { secs, nanos }
=> {
938 let n
= nanos
.sample(rng
);
939 Duration
::new(secs
, n
)
941 UniformDurationMode
::Medium { nanos }
=> {
942 let nanos
= nanos
.sample(rng
);
943 Duration
::new(nanos
/ 1_000_000_000, (nanos
% 1_000_000_000) as u32)
945 UniformDurationMode
::Large
{
950 // constant folding means this is at least as fast as `gen_range`
951 let nano_range
= Uniform
::new(0, 1_000_000_000);
953 let s
= secs
.sample(rng
);
954 let n
= nano_range
.sample(rng
);
955 if !(s
== max_secs
&& n
> max_nanos
) {
956 let sum
= n
+ self.offset
;
957 break Duration
::new(s
, sum
);
968 use crate::rngs
::mock
::StepRng
;
972 fn test_uniform_bad_limits_equal_int() {
973 Uniform
::new(10, 10);
977 fn test_uniform_good_limits_equal_int() {
978 let mut rng
= crate::test
::rng(804);
979 let dist
= Uniform
::new_inclusive(10, 10);
981 assert_eq
!(rng
.sample(dist
), 10);
987 fn test_uniform_bad_limits_flipped_int() {
992 #[cfg_attr(miri, ignore)] // Miri is too slow
994 #[cfg(not(target_os = "emscripten"))] use core::{i128, u128};
995 use core
::{i16, i32, i64, i8, isize}
;
996 use core
::{u16, u32, u64, u8, usize}
;
998 let mut rng
= crate::test
::rng(251);
1000 ($ty
:ident
, $v
:expr
, $le
:expr
, $lt
:expr
) => {{
1001 for &(low
, high
) in $v
.iter() {
1002 let my_uniform
= Uniform
::new(low
, high
);
1004 let v
: $ty
= rng
.sample(my_uniform
);
1005 assert
!($
le(low
, v
) && $
lt(v
, high
));
1008 let my_uniform
= Uniform
::new_inclusive(low
, high
);
1010 let v
: $ty
= rng
.sample(my_uniform
);
1011 assert
!($
le(low
, v
) && $
le(v
, high
));
1014 let my_uniform
= Uniform
::new(&low
, high
);
1016 let v
: $ty
= rng
.sample(my_uniform
);
1017 assert
!($
le(low
, v
) && $
lt(v
, high
));
1020 let my_uniform
= Uniform
::new_inclusive(&low
, &high
);
1022 let v
: $ty
= rng
.sample(my_uniform
);
1023 assert
!($
le(low
, v
) && $
le(v
, high
));
1027 let v
: $ty
= rng
.gen_range(low
, high
);
1028 assert
!($
le(low
, v
) && $
lt(v
, high
));
1034 ($
($ty
:ident
),*) => {{
1037 [(0, 10), (10, 127), ($ty
::MIN
, $ty
::MAX
)],
1044 ($
($ty
:ident
),* => $scalar
:ident
) => {{
1048 ($ty
::splat(0), $ty
::splat(10)),
1049 ($ty
::splat(10), $ty
::splat(127)),
1050 ($ty
::splat($scalar
::MIN
), $ty
::splat($scalar
::MAX
)),
1052 |x
: $ty
, y
| x
.le(y
).all(),
1053 |x
: $ty
, y
| x
.lt(y
).all()
1057 t
!(i8, i16, i32, i64, isize, u8, u16, u32, u64, usize);
1058 #[cfg(not(target_os = "emscripten"))]
1061 #[cfg(all(feature = "simd_support", feature = "nightly"))]
1063 t
!(u8x2
, u8x4
, u8x8
, u8x16
, u8x32
, u8x64
=> u8);
1064 t
!(i8x2
, i8x4
, i8x8
, i8x16
, i8x32
, i8x64
=> i8);
1065 t
!(u16x2
, u16x4
, u16x8
, u16x16
, u16x32
=> u16);
1066 t
!(i16x2
, i16x4
, i16x8
, i16x16
, i16x32
=> i16);
1067 t
!(u32x2
, u32x4
, u32x8
, u32x16
=> u32);
1068 t
!(i32x2
, i32x4
, i32x8
, i32x16
=> i32);
1069 t
!(u64x2
, u64x4
, u64x8
=> u64);
1070 t
!(i64x2
, i64x4
, i64x8
=> i64);
1075 #[cfg_attr(miri, ignore)] // Miri is too slow
1077 let mut rng
= crate::test
::rng(252);
1078 let mut zero_rng
= StepRng
::new(0, 0);
1079 let mut max_rng
= StepRng
::new(0xffff_ffff_ffff_ffff, 0);
1081 ($ty
:ty
, $f_scalar
:ident
, $bits_shifted
:expr
) => {{
1082 let v
: &[($f_scalar
, $f_scalar
)] = &[
1087 (<$f_scalar
>::from_bits(0), <$f_scalar
>::from_bits(3)),
1088 (-<$f_scalar
>::from_bits(10), -<$f_scalar
>::from_bits(1)),
1089 (-<$f_scalar
>::from_bits(5), 0.0),
1090 (-<$f_scalar
>::from_bits(7), -0.0),
1091 (10.0, ::core
::$f_scalar
::MAX
),
1092 (-100.0, ::core
::$f_scalar
::MAX
),
1093 (-::core
::$f_scalar
::MAX
/ 5.0, ::core
::$f_scalar
::MAX
),
1094 (-::core
::$f_scalar
::MAX
, ::core
::$f_scalar
::MAX
/ 5.0),
1095 (-::core
::$f_scalar
::MAX
* 0.8, ::core
::$f_scalar
::MAX
* 0.7),
1096 (-::core
::$f_scalar
::MAX
, ::core
::$f_scalar
::MAX
),
1098 for &(low_scalar
, high_scalar
) in v
.iter() {
1099 for lane
in 0..<$ty
>::lanes() {
1100 let low
= <$ty
>::splat(0.0 as $f_scalar
).replace(lane
, low_scalar
);
1101 let high
= <$ty
>::splat(1.0 as $f_scalar
).replace(lane
, high_scalar
);
1102 let my_uniform
= Uniform
::new(low
, high
);
1103 let my_incl_uniform
= Uniform
::new_inclusive(low
, high
);
1105 let v
= rng
.sample(my_uniform
).extract(lane
);
1106 assert
!(low_scalar
<= v
&& v
< high_scalar
);
1107 let v
= rng
.sample(my_incl_uniform
).extract(lane
);
1108 assert
!(low_scalar
<= v
&& v
<= high_scalar
);
1109 let v
= rng
.gen_range(low
, high
).extract(lane
);
1110 assert
!(low_scalar
<= v
&& v
< high_scalar
);
1114 rng
.sample(Uniform
::new_inclusive(low
, low
)).extract(lane
),
1118 assert_eq
!(zero_rng
.sample(my_uniform
).extract(lane
), low_scalar
);
1119 assert_eq
!(zero_rng
.sample(my_incl_uniform
).extract(lane
), low_scalar
);
1120 assert_eq
!(zero_rng
.gen_range(low
, high
).extract(lane
), low_scalar
);
1121 assert
!(max_rng
.sample(my_uniform
).extract(lane
) < high_scalar
);
1122 assert
!(max_rng
.sample(my_incl_uniform
).extract(lane
) <= high_scalar
);
1124 // Don't run this test for really tiny differences between high and low
1125 // since for those rounding might result in selecting high for a very
1127 if (high_scalar
- low_scalar
) > 0.0001 {
1128 let mut lowering_max_rng
= StepRng
::new(
1129 0xffff_ffff_ffff_ffff,
1130 (-1i64 << $bits_shifted
) as u64,
1133 lowering_max_rng
.gen_range(low
, high
).extract(lane
) < high_scalar
1140 rng
.sample(Uniform
::new_inclusive(
1141 ::core
::$f_scalar
::MAX
,
1142 ::core
::$f_scalar
::MAX
1144 ::core
::$f_scalar
::MAX
1147 rng
.sample(Uniform
::new_inclusive(
1148 -::core
::$f_scalar
::MAX
,
1149 -::core
::$f_scalar
::MAX
1151 -::core
::$f_scalar
::MAX
1156 t
!(f32, f32, 32 - 23);
1157 t
!(f64, f64, 64 - 52);
1158 #[cfg(feature = "simd_support")]
1160 t
!(f32x2
, f32, 32 - 23);
1161 t
!(f32x4
, f32, 32 - 23);
1162 t
!(f32x8
, f32, 32 - 23);
1163 t
!(f32x16
, f32, 32 - 23);
1164 t
!(f64x2
, f64, 64 - 52);
1165 t
!(f64x4
, f64, 64 - 52);
1166 t
!(f64x8
, f64, 64 - 52);
1173 not(target_arch
= "wasm32"),
1174 not(target_arch
= "asmjs")
1176 fn test_float_assertions() {
1177 use super::SampleUniform
;
1178 use std
::panic
::catch_unwind
;
1179 fn range
<T
: SampleUniform
>(low
: T
, high
: T
) {
1180 let mut rng
= crate::test
::rng(253);
1181 rng
.gen_range(low
, high
);
1185 ($ty
:ident
, $f_scalar
:ident
) => {{
1186 let v
: &[($f_scalar
, $f_scalar
)] = &[
1187 (::std
::$f_scalar
::NAN
, 0.0),
1188 (1.0, ::std
::$f_scalar
::NAN
),
1189 (::std
::$f_scalar
::NAN
, ::std
::$f_scalar
::NAN
),
1191 (::std
::$f_scalar
::MAX
, -::std
::$f_scalar
::MAX
),
1192 (::std
::$f_scalar
::INFINITY
, ::std
::$f_scalar
::INFINITY
),
1194 ::std
::$f_scalar
::NEG_INFINITY
,
1195 ::std
::$f_scalar
::NEG_INFINITY
,
1197 (::std
::$f_scalar
::NEG_INFINITY
, 5.0),
1198 (5.0, ::std
::$f_scalar
::INFINITY
),
1199 (::std
::$f_scalar
::NAN
, ::std
::$f_scalar
::INFINITY
),
1200 (::std
::$f_scalar
::NEG_INFINITY
, ::std
::$f_scalar
::NAN
),
1201 (::std
::$f_scalar
::NEG_INFINITY
, ::std
::$f_scalar
::INFINITY
),
1203 for &(low_scalar
, high_scalar
) in v
.iter() {
1204 for lane
in 0..<$ty
>::lanes() {
1205 let low
= <$ty
>::splat(0.0 as $f_scalar
).replace(lane
, low_scalar
);
1206 let high
= <$ty
>::splat(1.0 as $f_scalar
).replace(lane
, high_scalar
);
1207 assert
!(catch_unwind(|| range(low
, high
)).is_err());
1208 assert
!(catch_unwind(|| Uniform
::new(low
, high
)).is_err());
1209 assert
!(catch_unwind(|| Uniform
::new_inclusive(low
, high
)).is_err());
1210 assert
!(catch_unwind(|| range(low
, low
)).is_err());
1211 assert
!(catch_unwind(|| Uniform
::new(low
, low
)).is_err());
1219 #[cfg(feature = "simd_support")]
1233 #[cfg_attr(miri, ignore)] // Miri is too slow
1234 fn test_durations() {
1235 #[cfg(not(feature = "std"))] use core::time::Duration;
1236 #[cfg(feature = "std")] use std::time::Duration;
1238 let mut rng
= crate::test
::rng(253);
1241 (Duration
::new(10, 50000), Duration
::new(100, 1234)),
1242 (Duration
::new(0, 100), Duration
::new(1, 50)),
1244 Duration
::new(0, 0),
1245 Duration
::new(u64::max_value(), 999_999_999),
1248 for &(low
, high
) in v
.iter() {
1249 let my_uniform
= Uniform
::new(low
, high
);
1251 let v
= rng
.sample(my_uniform
);
1252 assert
!(low
<= v
&& v
< high
);
1258 fn test_custom_uniform() {
1259 use crate::distributions
::uniform
::{
1260 SampleBorrow
, SampleUniform
, UniformFloat
, UniformSampler
,
1262 #[derive(Clone, Copy, PartialEq, PartialOrd)]
1266 #[derive(Clone, Copy, Debug)]
1267 struct UniformMyF32(UniformFloat
<f32>);
1268 impl UniformSampler
for UniformMyF32
{
1271 fn new
<B1
, B2
>(low
: B1
, high
: B2
) -> Self
1273 B1
: SampleBorrow
<Self::X
> + Sized
,
1274 B2
: SampleBorrow
<Self::X
> + Sized
,
1276 UniformMyF32(UniformFloat
::<f32>::new(low
.borrow().x
, high
.borrow().x
))
1279 fn new_inclusive
<B1
, B2
>(low
: B1
, high
: B2
) -> Self
1281 B1
: SampleBorrow
<Self::X
> + Sized
,
1282 B2
: SampleBorrow
<Self::X
> + Sized
,
1284 UniformSampler
::new(low
, high
)
1287 fn sample
<R
: Rng
+ ?Sized
>(&self, rng
: &mut R
) -> Self::X
{
1289 x
: self.0.sample(rng
),
1293 impl SampleUniform
for MyF32
{
1294 type Sampler
= UniformMyF32
;
1297 let (low
, high
) = (MyF32 { x: 17.0f32 }
, MyF32 { x: 22.0f32 }
);
1298 let uniform
= Uniform
::new(low
, high
);
1299 let mut rng
= crate::test
::rng(804);
1301 let x
: MyF32
= rng
.sample(uniform
);
1302 assert
!(low
<= x
&& x
< high
);
1307 fn test_uniform_from_std_range() {
1308 let r
= Uniform
::from(2u32..7);
1309 assert_eq
!(r
.0.low
, 2);
1310 assert_eq
!(r
.0.range
, 5);
1311 let r
= Uniform
::from(2.0f64..7.0);
1312 assert_eq
!(r
.0.low
, 2.0);
1313 assert_eq
!(r
.0.scale
, 5.0);
1317 fn test_uniform_from_std_range_inclusive() {
1318 let r
= Uniform
::from(2u32..=6);
1319 assert_eq
!(r
.0.low
, 2);
1320 assert_eq
!(r
.0.range
, 5);
1321 let r
= Uniform
::from(2.0f64..=7.0);
1322 assert_eq
!(r
.0.low
, 2.0);
1323 assert
!(r
.0.scale
> 5.0);
1324 assert
!(r
.0.scale
< 5.0 + 1e
-14);
1328 fn value_stability() {
1329 fn test_samples
<T
: SampleUniform
+ Copy
+ core
::fmt
::Debug
+ PartialEq
>(
1330 lb
: T
, ub
: T
, expected_single
: &[T
], expected_multiple
: &[T
],
1331 ) where Uniform
<T
>: Distribution
<T
> {
1332 let mut rng
= crate::test
::rng(897);
1333 let mut buf
= [lb
; 3];
1336 *x
= T
::Sampler
::sample_single(lb
, ub
, &mut rng
);
1338 assert_eq
!(&buf
, expected_single
);
1340 let distr
= Uniform
::new(lb
, ub
);
1342 *x
= rng
.sample(&distr
);
1344 assert_eq
!(&buf
, expected_multiple
);
1347 // We test on a sub-set of types; possibly we should do more.
1350 test_samples(11u8, 219, &[17, 66, 214], &[181, 93, 165]);
1351 test_samples(11u32, 219, &[17, 66, 214], &[181, 93, 165]);
1353 test_samples(0f32, 1e
-2f32, &[0.0003070104, 0.0026630748, 0.00979833], &[
1361 &[-4673848682.871551, 6388267422.932352, 4857075081.198343],
1362 &[1173375212.1808167, 1917642852.109581, 2365076174.3153973],
1366 Duration
::new(2, 0),
1367 Duration
::new(4, 0),
1369 Duration
::new(2, 532615131),
1370 Duration
::new(3, 638826742),
1371 Duration
::new(3, 485707508),
1374 Duration
::new(3, 117337521),
1375 Duration
::new(3, 191764285),
1376 Duration
::new(3, 236507617),