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

[Jonathan Wakely]

On Fri, 28 Aug 2026, 07:02 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.
>
> 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 <jwakely@redhat.com>
> Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
> ---
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260828/c0fd6ca3/attachment.htm>