Handle generators with non-zero min in uniform_int_distribution
Fixed `uniform_int_distribution` to correctly handle random number generators whose range does not start at zero.
The Lemire’s algorithm used in uniform_int_distribution incorrectly assumed that random number generators (engines) always produced values starting from zero. This commit corrects this assumption by subtracting the minimum value of the generator’s range before producing output. This ensures uniformity for user-provided engines whose ranges are offset, resolving a failure in testDiscreteDist.
In Details
This commit addresses PR libstdc++/118665, fixing an assumption in Lemire's algorithm for uniform_int_distribution (_S_nd in bits/uniform_int_dist.h). The algorithm incorrectly assumed that engines generating ranges of 2^32 or 2^64 would always start from zero. This is not true for user-defined engines. The fix subtracts __min (equivalent to _Urbg::min()) from the generated number, ensuring uniformity even for engines with a non-zero minimum. Since __min is a compile-time constant, this has no performance impact for standard engines.
- uniform_int_distribution
- A C++ standard library class that generates random integers uniformly distributed over a specified range [min, max].
- random number generator engine
- A component in a random number generation library that produces a sequence of pseudo-random bits or numbers, which are then often processed by distributions.
- Lemire's algorithm
- An efficient algorithm for generating uniformly distributed integers within a given range, often used in pseudo-random number generation.
- PR
- Problem Report. A bug or issue filed against a piece of software, often used as a reference in commit messages.