如何实现一个范围内有符号整数的无偏随机方法

Question

我一直在创建一个用于生成随机数的精简库，并且一直在努力生成范围内的有符号整数。

无符号整数很容易，我已经实现了Lemire的去偏整数乘法方法。然而，它并不容易扩展到有符号整数：

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
}
}

对于有符号整数，我将如何在最小/最大范围内实现大部分去偏随机数生成？

Answer 1

好吧，我开始工作了。我使用环绕<$type>::MAX / 2 + 1的包装加法将有符号整数的范围映射到无符号整数。

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
}