[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.