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