https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118665
--- Comment #6 from Tomasz Kamiński <tkaminsk at gcc dot gnu.org> ---
As for Lemiere algorithm, it is not important what number are rejected, only
that we reject __threshold from range of 2^_Up_traits::__digits, we could
address the above by alternating rejecting from beging/end of range:
diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h
b/libstdc++-v3/include/bits/uniform_int_dist.h
index 9c5514c7c13..d6b3bf108c1 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -273,6 +273,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Up __threshold = -__range % __range;
while (__low < __threshold)
{
+ // Rejection is modified to alternate between rejecting from
+ // begining (__low) and end (__high) of the range.
+ // This guarantee stop for biased generators that always
+ // results in __low value.
+ __product = _Wp(__g()) * _Wp(__range);
+ _Up __high = _Up(__product);
+ if (__high <= _Up_traits::__max - __threshold)
+ break;
+
__product = _Wp(__g()) * _Wp(__range);
__low = _Up(__product);
}
This will guarantee that we will finish for generator that constantly returns
any number.
It would be still possible to have it run forever by having an generator that
also alternate between low and high numbers. However, I think that apply to any
algorithm that rejects range of input, including independent bits engine.
