CODEWITHSUNDEEP
randomrust
Lucy
Lucy

Reputation: 31

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?

Upvotes: 1

Views: 107

Answers (1)

Lucy
Lucy

Reputation: 31

Alright, I got it to work. I use a wrapping add around <$type>::MAX / 2 + 1 to map the range of a signed integer to an unsigned integer.

fn random_range<B: RangeBounds<Self>>(r: &mut R, bounds: B) -> Self {
    const SIGNED_MAPPING: u64 = <u64>::MAX / 2 + 1;
    let lower = match bounds.start_bound() {
        Bound::Included(lower) => *lower,
        Bound::Excluded(lower) => lower.saturating_add(1),
        Bound::Unbounded => <i64>::MIN
    };
    let upper = match bounds.end_bound() {
        Bound::Included(upper) => *upper,
        Bound::Excluded(upper) => upper.saturating_sub(1),
        Bound::Unbounded => <i64>::MAX,
    };
    let lower = (lower as u64).wrapping_add(SIGNED_MAPPING);
    let upper = (upper as u64).wrapping_add(SIGNED_MAPPING);
    assert!(upper >= lower, "{} >= {}", upper, lower);
    <u64>::random_range(r, lower..=upper).wrapping_add(SIGNED_MAPPING) as i64
}

Upvotes: 1

Related Questions