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

Question

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?

For those not wanting to _implement_ it, see also [How to generate a random Rust integer in a range without introducing bias?](https://stackoverflow.com/q/52454677/155423). — Shepmaster, Jul 07 '21 at 18:45
See also my section: [`RNDINTRANGE`](https://peteroupc.github.io/randomfunc.html#RNDINTRANGE_Random_Integers_in_N_M). — Peter O., Jul 07 '21 at 18:56
It's not clear what you find difficult about converting the algorithm to signed numbers. You know the width of the range and the start of the range. Can you not generate an unsigned range with the same width, then shift the resulting value by the start? — Shepmaster, Jul 07 '21 at 18:56
@Shepmaster: Wait yeah, you're right... Gimme a bit, I'll try to answer this myself for clarity. — Lucy, Jul 07 '21 at 19:27
i am now struggling with the whole i32-u32 conversion thing, ugh. — Lucy, Jul 07 '21 at 20:42
nvm i just refactored the code to be simpler and it just worked lmao — Lucy, Jul 07 '21 at 21:16

score 1 · Accepted Answer · answered Jul 07 '21 at 21:17

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
}

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

1 Answers1