[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

Xi Ruoyao <xry111 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
                 CC|                            |xry111 at gcc dot gnu.org

--- Comment #7 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
The C++11 standard explicitly allows to use rand() as the random source for
random_shuffle, thus this is not a bug but an enhancement.

As random_shuffle is deprecated since C++14 and removed in C++17 (the interface
is just broken beyond any repair), I think we should just emit a deprecation
warning telling to use shuffle (it needs an uniform random bit generator to be
passed) instead.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

--- Comment #8 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
(In reply to Xi Ruoyao from comment #7)
> The C++11 standard explicitly allows to use rand() as the random source for
> random_shuffle, thus this is not a bug but an enhancement.
> 
> As random_shuffle is deprecated since C++14 and removed in C++17 (the
> interface is just broken beyond any repair), I think we should just emit a
> deprecation warning telling to use shuffle (it needs an uniform random bit
> generator to be passed) instead.

The deprecation warning has been added at r14-2796.  I'm inclined to close this
as WONTFIX because people who care about the strict correctness **shall** just
use std::shuffle instead.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Xi Ruoyao from comment #7)
> The C++11 standard explicitly allows to use rand() as the random source for
> random_shuffle, thus this is not a bug but an enhancement.

It doesn't just allow it, it requires it. But the standard also requires a
uniform distribution, and we fail to meet that requirement because of the range
of RAND_MAX. (We actually fail to meet it on all targets, because we use %
which is not uniformly distributed unless RAND_MAX is an exact multiple of
(last - first), so we always have a bias.)

The proposed patch still uses rand() as the source of randomness, it just uses
that source as input to another level of pseudo-randomness. That is conforming
to the C++11 standard.

Using std::shuffle isn't possible in C++98 code. Using the other overload of
std::random_shuffle is possible though, and that allows you to provide a PRNG
that returns values greater than RAND_MAX.

Please don't close this bug, that serves no purpose. It's a bug and should be
fixed.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |normal

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

--- Comment #10 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #9)
> (In reply to Xi Ruoyao from comment #7)
> > The C++11 standard explicitly allows to use rand() as the random source for
> > random_shuffle, thus this is not a bug but an enhancement.
> 
> It doesn't just allow it, it requires it. But the standard also requires a
> uniform distribution, and we fail to meet that requirement because of the
> range of RAND_MAX. (We actually fail to meet it on all targets, because we
> use % which is not uniformly distributed unless RAND_MAX is an exact
> multiple of (last - first), so we always have a bias.)

I cannot see how it is possible to guarantee an uniform distribution with
rand() because the C standard even says rand() is allowed to be very stupid:

> There are no guarantees as to the quality of the random sequence produced
> and some implementations are known to produce sequences with distressingly
> non-random low-order bits. Applications with particular requirements should
> use a generator that is known to be sufficient for their needs.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Yes, but in practice that's not the problem with mingw. The problem is the low
RAND_MAX. The distribution within the range of numbers produced is acceptable.
Good enough for std::random_shuffle anyway.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[agriff at tin dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

Andrea Griffini <agriff at tin dot it> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |agriff at tin dot it

--- Comment #12 from Andrea Griffini <agriff at tin dot it> ---
Even assuming rand() were generating hardware random numbers (not allowed by
the standard because of srand, obviously), gcc would still be broken and
performing a terrible random_shuffle with ranges larger than 64k elements
(indeed non-uniformity becomes evident even at much smaller ranges).

Mingw's rand() numbers are decent enough (and the period is not just 2**16, for
example) but they're only 16 bit. This is allowed.

The gcc bug is that it uses rand() (that can be just 16) bit to pick a random
number between 0 and the size of the range even when the range is much bigger
than 65536. Using rand() to feed data into a xorshift64 or something similar
only for large ranges would fix, and would also keep shuffle of small ranges
backward compatible (shuffling elements in small ranges exactly as current
implementation does if starting from the same random seed).

I've somewhere an half backed patch for doing that but quite frankly I don't
know if I should polish it and submit here as, in all honesty, seems that in
this case the maintainers simply don't want to have this bug fixed, for reasons
that I really cannot understand.

[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
std::random_shuffle was removed from the C++ standard years ago, precisely
because it uses low quality randomness. So it's not a high priority to fix
something that is no longer even in the standard, because it's known to have
unfixable problems. We also don't waste time on std::auto_ptr and
std::strstream.

I do intend to revisit Giovanni's patch for GCC 15, but it's not a high
priority.