[PATCH] libstdc++: Handle generators with non-zero min in uniform_int_distribution [PR118665]

[Jonathan Wakely]

On Mon, 27 Jul 2026 at 16:21, Tomasz Kamiński <tkaminsk@redhat.com> 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
>