Repository navigation
WeightedIndex produces unexpected results when sum of weights does not fit in the integer type #1309
Description
WeightedIndex distribution does not explicitely check that the sum of weights fits into the target type X (if it is an integer). When compiling in release mode (with overflow checking disabled), this code will almost always print 0 rather than the expected 1.
use rand::thread_rng;
use rand_distr::{WeightedIndex, Distribution};
fn main() {
let dist = WeightedIndex::new([2, usize::MAX]).unwrap();
println!("{}", dist.sample(&mut thread_rng()));
}I would expect WeightedIndex::new to either return an Err or panic if the sum of weights does not fit into X.
Activity
dhardy commentedon Apr 17, 2023
Reproduced:
newpanics in debug builds but succeeds in release builds.The standard way to check for overflow would be using
checked_add, unfortunately we can't here: we're using generics overX: SampleUniform + PartialOrd + for<'a> ::core::ops::AddAssign<&'a X> + Clone + Default.Alternative approach: check that the sum is not less than either operand. This fails in debug builds with a panic instead of an
Err(..). I don't like the idea of deliberately introducing deviations between debug and release behaviour, even if it's only different failure modes.We can't circumvent this with
wrapping_addeither.We could use separate impls of
newfor integer types vs float types, however:So I'm not sure how to solve this!
dhardy commentedon Apr 17, 2023
Hacky patch: master...dhardy:rand:weighted_index_overflow