On Fri, 28 Aug 2026, 07:02 Tomasz Kamiński, <[email protected]> wrote:
> The commit r11-3757-g98c37d3bacbb2f that introduced Lemire's algorithm in > uniform_int_distribution, assumed that any engine that generates range of > size 2^32 or 2^64, returns a range starting from zero. While this is true > for all standard providede engines, it may not be true for user provided > ranges. In such case the produced output is no longer uniform: > testDiscreteDist was failing for such engine. > > This patch simply substract __min (_Urbg::min()) from the generated number > (__g()). As this value is compile time constant, this has no performance > impact for generators producing ranges starting from zero. > > PR libstdc++/118665 > > libstdc++-v3/ChangeLog: > > * include/bits/uniform_int_dist.h > (uniform_int_distribution::_S_nd): > Substract __min (_Urbg::min()) from each generator invocation. > * > testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc: > Add testDiscreteDist for shifted (with non-zero min()) engine. > > Reviewed-by: Jonathan Wakely <[email protected]> > Signed-off-by: Tomasz Kamiński <[email protected]> > --- > v2 rebases this on top of the trunk, instead of hanging fix, so it is > easier to backport. > > OK for trunk/16/15/14? > OK for all, thanks > libstdc++-v3/include/bits/uniform_int_dist.h | 5 +++-- > .../operators/values.cc | 22 +++++++++++++++++++ > 2 files changed, 25 insertions(+), 2 deletions(-) > > diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h > b/libstdc++-v3/include/bits/uniform_int_dist.h > index 9c5514c7c13..072c6351e1f 100644 > --- a/libstdc++-v3/include/bits/uniform_int_dist.h > +++ b/libstdc++-v3/include/bits/uniform_int_dist.h > @@ -262,18 +262,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > static_assert(!_Wp_traits::__is_signed, "W must be unsigned"); > static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits), > "W must be twice as wide as U"); > + constexpr auto __min = _Urbg::min(); > > // reference: Fast Random Integer Generation in an Interval > // ACM Transactions on Modeling and Computer Simulation 29 (1), > 2019 > // https://arxiv.org/abs/1805.10941 > - _Wp __product = _Wp(__g()) * _Wp(__range); > + _Wp __product = _Wp(__g() - __min) * _Wp(__range); > _Up __low = _Up(__product); > if (__low < __range) > { > _Up __threshold = -__range % __range; > while (__low < __threshold) > { > - __product = _Wp(__g()) * _Wp(__range); > + __product = _Wp(__g() - __min) * _Wp(__range); > __low = _Up(__product); > } > } > diff --git > a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc > b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc > index 11758a3e2b6..fce14944d88 100644 > --- > a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc > +++ > b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc > @@ -21,6 +21,7 @@ > // 26.5.8.2.1 Class template uniform_int_distribution [rand.dist.uni.int] > > #include <random> > +#include <cstdint> > #include <functional> > #include <testsuite_random.h> > > @@ -32,6 +33,19 @@ > # define ARGS > #endif > > +template<std::uint64_t Offset> > +struct shifted > +{ > + using result_type = std::uint64_t; > + static constexpr result_type min() { return Offset; } > + static constexpr result_type max() { return Offset + > std::mt19937::max(); } > + > + result_type operator()() > + { return Offset + eng(); } > + > + std::mt19937 eng; > +}; > + > void test01() > { > using namespace __gnu_test; > @@ -49,6 +63,14 @@ void test01() > std::uniform_int_distribution<> uid3(1, 20); > auto buid3 = std::bind(uid3, eng); > testDiscreteDist<ARGS>(buid3, [](int n) { return uniform_int_pdf(n, 1, > 20); } ); > + > + shifted<(std::uint64_t(1) << 16)> s16e; > + auto buid4 = std::bind(uid3, s16e); > + testDiscreteDist<ARGS>(buid4, [](int n) { return uniform_int_pdf(n, 1, > 20); } ); > + > + shifted<(std::uint64_t(1) << 32)> s32e; > + auto buid5 = std::bind(uid3, s32e); > + testDiscreteDist<ARGS>(buid5, [](int n) { return uniform_int_pdf(n, 1, > 20); } ); > } > > int main() > -- > 2.55.0 > >
