On Mon, 27 Jul 2026 at 16:21, 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.
Oops, good catch. I think we were assuming that if the generator's range is equal to UINT32_MAX or UINT64_MAX then it generates the entire range of the output, from 0 to numeric_limits<result_type>::max(). But if result_type is uint64_t we could have a range of UINT32_MAX that doesn't begin with zero. Nice test case. > > 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. > --- > I realized that this is another regressions from Lemiere's algorithm, > for some unusuall generators, and may affects ones that emit range of > size 2^N, with N != 32 or != 64. > > Testing on x86_64-linux. Additionally *random* test passed > in all standard modes, debug, -m32. OK for trunk? OK for trunk. > > We should for backport this with the previous change (alternating > rejection), and may do it idependently. Yes, this should be on all active branches, even if we don't backport the alternating rejection to all active branches. > libstdc++-v3/include/bits/uniform_int_dist.h | 7 +++--- > .../operators/values.cc | 22 +++++++++++++++++++ > 2 files changed, 26 insertions(+), 3 deletions(-) > > diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h > b/libstdc++-v3/include/bits/uniform_int_dist.h > index 8ffce793482..1b472e7b93a 100644 > --- a/libstdc++-v3/include/bits/uniform_int_dist.h > +++ b/libstdc++-v3/include/bits/uniform_int_dist.h > @@ -262,11 +262,12 @@ _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) > { > @@ -277,12 +278,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > // begining (__low) and end (__high) of the range. This > // guarantee stop for non-uniform engines that always > results > // in __low value. > - __product = _Wp(__g()) * _Wp(__range); > + __product = _Wp(__g() - __min) * _Wp(__range); > _Up __high = _Up(__product); > if (__high <= _Up_traits::__max - __threshold) > break; > > - __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 >
