[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Jonathan Wakely changed: What|Removed |Added Status|NEW |RESOLVED Resolution|--- |FIXED --- Comment #15 from Jonathan Wakely --- Fixed for GCC 15
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #14 from GCC Commits --- The master branch has been updated by Jonathan Wakely : https://gcc.gnu.org/g:125bab23ad75449333983c9389898c5b92b3aa0d commit r15-3129-g125bab23ad75449333983c9389898c5b92b3aa0d Author: Giovanni Bajo Date: Wed Jul 31 20:03:40 2024 +0100 libstdc++: Fix std::random_shuffle for low RAND_MAX [PR88935] When RAND_MAX is small and the number of elements being shuffled is close to it, we get very uneven distributions in std::random_shuffle. This uses a simple xorshift generator seeded by std::rand if we can't rely on std::rand itself. libstdc++-v3/ChangeLog: PR libstdc++/88935 * include/bits/stl_algo.h (random_shuffle) [RAND_MAX < INT_MAX]: Use xorshift instead of rand(). * testsuite/25_algorithms/random_shuffle/88935.cc: New test. Co-authored-by: Jonathan Wakely Signed-off-by: Giovanni Bajo
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Jonathan Wakely changed: What|Removed |Added Target Milestone|--- |15.0
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #13 from Jonathan Wakely --- 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.
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Andrea Griffini changed: What|Removed |Added CC||agriff at tin dot it --- Comment #12 from Andrea Griffini --- 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #11 from Jonathan Wakely --- 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #10 from Xi Ruoyao --- (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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Jonathan Wakely 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #9 from Jonathan Wakely --- (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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #8 from Xi Ruoyao --- (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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Xi Ruoyao changed: What|Removed |Added Severity|normal |enhancement CC||xry111 at gcc dot gnu.org --- Comment #7 from Xi Ruoyao --- 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
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 Jonathan Wakely changed: What|Removed |Added Status|UNCONFIRMED |NEW Last reconfirmed||2019-01-21 Ever confirmed|0 |1
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #6 from Giovanni Bajo --- A patch has been posted here: https://gcc.gnu.org/ml/libstdc++/2018-12/msg00038.html
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #5 from Giovanni Bajo --- Created attachment 45474 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45474&action=edit Chart generated by chart.cpp that highlights broken distribution
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #4 from Giovanni Bajo --- Created attachment 45473 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45473&action=edit What test.cpp actually does output with std::random_shuffle
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #3 from Giovanni Bajo --- Created attachment 45472 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45472&action=edit What test.cpp should output if random_shuffle worked
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #2 from Giovanni Bajo --- Created attachment 45471 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45471&action=edit Test code to draw a chart of distributions
[Bug libstdc++/88935] std::random_shuffle does not work if the sequence is longer than RAND_MAX elements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88935 --- Comment #1 from Giovanni Bajo --- Created attachment 45470 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=45470&action=edit Test code to reproduce bug
