mercredi 7 juillet 2021

How to implement an unbiased random method for signed integers within a range?

I've been creating a slim library for random number generation, and I've been struggling with generating signed integers within a range.

Unsigned integers are easy, I've implemented Lemire's debiased integer multiplication method. However, it does not extend easily to signed integers:

impl<R: Rng> RandomRange<R> for u64 {
    fn random_range<B: RangeBounds<Self>>(r: &mut R, bounds: B) -> Self {
        const BITS: u128 = core::mem::size_of::<u64>() as u128 * 8;
        let lower = match bounds.start_bound() {
            Bound::Included(lower) => *lower,
            Bound::Excluded(lower) => lower.saturating_add(1),
            Bound::Unbounded => <u64>::MIN,
        };
        let upper = match bounds.end_bound() {
            Bound::Included(upper) => upper.saturating_sub(lower).saturating_add(1),
            Bound::Excluded(upper) => upper.saturating_sub(lower),
            Bound::Unbounded => <u64>::MAX,
        };
        let mut value = Self::random(r);
        let mut m = (upper as u128).wrapping_mul(value as u128);
        if (m as u64) < upper {
            let t = (!upper + 1) % upper;
            while (m as u64) < t {
                value = Self::random(r);
                m = (upper as u128).wrapping_mul(value as u128);
            }
        }
        (m >> BITS) as u64 + lower
    }
}

How would I implement mostly debiased random number generation within a min/max range for signed integers?




Aucun commentaire:

Enregistrer un commentaire