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.
---
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?
We should for backport this with the previous change (alternating
rejection), and may do it idependently.
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
