dashu_ratio/third_party/

rand.rs

//! Random rational numbers generation with the `rand` crate.
//!
//! There are two new distributions for generating random floats. The first one is [Uniform01],
//! which supports generating rationals between 0 and 1. This is also the underlying implementation
//! of the builtin `rand` distributions [Standard], [Open01], [OpenClosed01]. The other one is
//! [UniformRBig], which supports generating rationals in a certain range. This is also the
//! backend for the [SampleUniform] trait.
//!
//! Note that [Uniform01] supports generating both [RBig] and [Relaxed], but [UniformRBig] currently
//! only supports generating [RBig].
//!
//! # Examples
//!
//! ```
//! use dashu_ratio::{RBig, Relaxed, rand::Uniform01};
//! # use rand_v08::{distributions::uniform::Uniform, thread_rng, Rng};
//!
//! // generate RBigs in a [0, 1) or [0, 1] with a given precision
//! let a: RBig = thread_rng().sample(Uniform01::new(&10u8.into()));
//! let b: Relaxed = thread_rng().sample(Uniform01::new_closed(&10u8.into()));
//! let c: RBig = thread_rng().gen(); // the default distribution generates in [0, 1)
//! assert!(a >= RBig::ZERO && a < RBig::ONE);
//! assert!(b >= Relaxed::ZERO && b <= Relaxed::ONE);
//! assert!(c >= RBig::ZERO && c < RBig::ONE);
//!
//! // generate RBigs in a range
//! let a = thread_rng().gen_range(RBig::from(3)..RBig::from(10));
//! let b = thread_rng().sample(Uniform::new(RBig::from(-5), &a));
//! assert!(a >= RBig::from(3) && a < RBig::from(10));
//! assert!(b >= RBig::from(-5) && b < a);
//! ```
//!
//! # Denominator
//!
//! The denominator of a rational generated by different distributions is explained below:
//! * [Uniform01] will generate rationals with a denominator decided by the constructor.
//! * [Standard], [Open01], [OpenClosed01] will generate rationals with [DoubleWord::MAX] as
//!   the denominator.
//! * [UniformRBig] will generate rationals with the denominator being the least common multiple
//!   of the denominators of the interval boundaries.
//!
//! Note that in the current implementation, the denominator of a rational generated in a closed interval
//! will be less by one than that generated in an open or half-open interval.
//!

use crate::{rbig::RBig, repr::Repr, Relaxed};

use dashu_base::Gcd;
use dashu_int::{
    rand::{UniformBelow, UniformIBig},
    DoubleWord, IBig, UBig,
};
use rand_v08::{
    distributions::{
        uniform::{SampleBorrow, SampleUniform, UniformSampler},
        Open01, OpenClosed01, Standard,
    },
    prelude::Distribution,
    Rng,
};

/// A uniform distribution between 0 and 1. It can be used to replace the [Standard], [Open01],
/// [OpenClosed01] distributions from the `rand` crate when you want to customize the denominator
/// limit of the generated float number.
pub struct Uniform01<'a> {
    limit: &'a UBig,
    include_zero: bool, // whether include the zero
    include_one: bool,  // whether include the one
}

impl<'a> Uniform01<'a> {
    /// Create a uniform distribution in `[0, 1)` with a given limit of the denominator.
    #[inline]
    pub fn new(limit: &'a UBig) -> Self {
        Self {
            limit,
            include_zero: true,
            include_one: false,
        }
    }

    /// Create a uniform distribution in `[0, 1]` with a given limit of the denominator.
    #[inline]
    pub fn new_closed(limit: &'a UBig) -> Self {
        Self {
            limit,
            include_zero: true,
            include_one: true,
        }
    }

    /// Create a uniform distribution in `(0, 1)` with a given limit of the denominator.
    #[inline]
    pub fn new_open(limit: &'a UBig) -> Self {
        Self {
            limit,
            include_zero: false,
            include_one: false,
        }
    }

    /// Create a uniform distribution in `(0, 1]` with a given limit of the denominator.
    #[inline]
    pub fn new_open_closed(limit: &'a UBig) -> Self {
        Self {
            limit,
            include_zero: false,
            include_one: true,
        }
    }
}

impl<'a> Distribution<Repr> for Uniform01<'a> {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Repr {
        match (self.include_zero, self.include_one) {
            (true, false) => {
                // sample in [0, 1)
                let num: UBig = UniformBelow::new(self.limit).sample(rng);
                Repr {
                    numerator: num.into(),
                    denominator: self.limit.clone(),
                }
            }
            (true, true) => {
                // sample in [0, 1]
                let num: UBig = UniformBelow::new(self.limit).sample(rng);
                Repr {
                    numerator: num.into(),
                    denominator: self.limit.clone() - UBig::ONE,
                }
            }
            (false, false) => {
                // sample in (0, 1)
                let num = loop {
                    // simply reject zero
                    let n: UBig = UniformBelow::new(self.limit).sample(rng);
                    if !n.is_zero() {
                        break n;
                    }
                };
                Repr {
                    numerator: num.into(),
                    denominator: self.limit.clone(),
                }
            }
            (false, true) => {
                // sample in (0, 1]
                let num: UBig = UniformBelow::new(self.limit).sample(rng);
                Repr {
                    numerator: (num + UBig::ONE).into(),
                    denominator: self.limit.clone(),
                }
            }
        }
    }
}

impl<'a> Distribution<RBig> for Uniform01<'a> {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> RBig {
        RBig(Distribution::<Repr>::sample(self, rng).reduce())
    }
}

impl<'a> Distribution<Relaxed> for Uniform01<'a> {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Relaxed {
        Relaxed(Distribution::<Repr>::sample(self, rng).reduce2())
    }
}

/// The back-end implementing [UniformSampler] for [RBig].
///
/// See the module ([rand][crate::rand]) level documentation for examples.
pub struct UniformRBig {
    num_sampler: UniformIBig,
    den: UBig,
}

impl UniformRBig {
    // parse the bounds `(low, high)` to a `(numerator low, numerator high, denominator)`
    fn parse_bounds<B1, B2>(low: B1, high: B2) -> (IBig, IBig, UBig)
    where
        B1: SampleBorrow<RBig> + Sized,
        B2: SampleBorrow<RBig> + Sized,
    {
        let (low_d, high_d) = (low.borrow().denominator(), high.borrow().denominator());
        let g = low_d.gcd(high_d);
        let low_n = high_d / &g * low.borrow().numerator();
        let high_n = low_d / &g * high.borrow().numerator();
        let den = low_d / g * high_d;
        (low_n, high_n, den)
    }
}

impl UniformSampler for UniformRBig {
    type X = RBig;

    #[inline]
    fn new<B1, B2>(low: B1, high: B2) -> Self
    where
        B1: SampleBorrow<Self::X> + Sized,
        B2: SampleBorrow<Self::X> + Sized,
    {
        let (low_n, high_n, den) = Self::parse_bounds(low, high);
        UniformRBig {
            num_sampler: UniformIBig::new(low_n, high_n),
            den,
        }
    }

    #[inline]
    fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self
    where
        B1: SampleBorrow<Self::X> + Sized,
        B2: SampleBorrow<Self::X> + Sized,
    {
        let (low_n, high_n, den) = Self::parse_bounds(low, high);
        UniformRBig {
            num_sampler: UniformIBig::new_inclusive(low_n, high_n),
            den,
        }
    }

    #[inline]
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> RBig {
        RBig::from_parts(self.num_sampler.sample(rng), self.den.clone())
    }
}

impl SampleUniform for RBig {
    type Sampler = UniformRBig;
}

macro_rules! impl_builtin_distr {
    (impl $trait:ident for $t:ty, $ctor:ident) => {
        impl Distribution<$t> for $trait {
            #[inline]
            fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> $t {
                let limit = UBig::from_dword(DoubleWord::MAX);
                Uniform01::$ctor(&limit).sample(rng)
            }
        }
    };
}

impl_builtin_distr!(impl Standard for RBig, new);
impl_builtin_distr!(impl Standard for Relaxed, new);
impl_builtin_distr!(impl Open01 for RBig, new_open);
impl_builtin_distr!(impl Open01 for Relaxed, new_open);
impl_builtin_distr!(impl OpenClosed01 for RBig, new_open_closed);
impl_builtin_distr!(impl OpenClosed01 for Relaxed, new_open_closed);