The fix to bug 63176 causes std::generate_canonical to loop until the result is less than 1.0. As noted in the discussion, this breaks the complexity requirement in [rand.util.canonical]/p3. There is a simple solution which also fixes 63176 but which doesn't violate the standard's complexity requirement. Instead of looping, do: if (__builtin_expect(__ret >= _RealType(1), 0)) return _RealType(std::nextafter(_RealType(1), _RealType(0))); else return _ret;
The misbehavior is observable by comparing an rng that is invoked directly with one that is invoked via generate_canonical. drdws0134$ cat skippy.cpp #include <iostream> #include <random> int main() { std::mt19937 rng; std::seed_seq sequence{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; rng.seed(sequence); rng.discard(12 * 629143); std::mt19937 rng2{rng}; for(int i=0; i<20; ++i) { // mt19937 produces more than 23 bits per invocation, so // generate_canonical should invoke rng once. (void)std::generate_canonical<float, 23>(rng); // invoke rng2 once as well (void)rng2(); // they should still be in sync if( rng2 != rng ) { std::cout << "Bug at 12* 629143 + " << i << "!\n"; return 1; } } return 0; } drdws0134$ g++ -Wall -std=c++11 skippy.cpp drdws0134$ ./a.out Bug at 12* 629143 + 6! drdws0134$ drdws0134$ g++ --version g++ (GCC) 6.3.0 Copyright (C) 2016 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. drdws0134$
We need to handle targets without C99's nextafter, but maybe this would be OK: if (__builtin_expect(__ret >= _RealType(1), 0)) { #if _GLIBCXX_USE_C99_MATH_TR1 __ret = std::nextafter(_RealType(1), _RealType(0)); #else __ret = _RealType(0); #endif } If we reach 1.0 it's because we're rounding up or to nearest, and so returning zero in that case would counteract the decreased probability of getting zero otherwise.
It's easy to overthink this. 0.0 is perfectly acceptable, as is any other _RealType in the range [0, 1.). But since rounding was, presumably, to-nearest or up, it's slightly disconcerting that 0.0 is neither near nor up from the "exact" value. How about: if (__builtin_expect(__ret >= _RealType(1), 0)) { #if _GLIBCXX_USE_C99_MATH_TR1 __ret = std::nextafter(_RealType(1), _RealType(0)); #else __ret = _RealType(1) - std::numeric_limits<_RealType>::epsilon()/2.; #endif } I.e., if there's no nextafter, then use numeric_limits::epsilon() to find the value just below 1.0. John Salmon
Ah, I tried that but not halving the epsilon, and so got a different result that I wasn't happy with. I sugested _RealType(0) because if the analysis at http://stackoverflow.com/a/25669510 is correct then the current code is biased against 0, so using it when we round up to 1.0 would offset that, to a greater or lesser extent. I don't know which :-) I'll go with your suggestion, thanks.
Author: redi Date: Tue Mar 28 16:09:49 2017 New Revision: 246542 URL: https://gcc.gnu.org/viewcvs?rev=246542&root=gcc&view=rev Log: PR libstdc++/80137 use std::nextafter instead of looping PR libstdc++/80137 * include/bits/random.tcc (generate_canonical): Use std::nextafter or numeric_limits::epsilon() to reduce out-of-range values. * testsuite/26_numerics/random/uniform_real_distribution/operators/ 64351.cc: Verify complexity requirement is met. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/random.tcc trunk/libstdc++-v3/testsuite/26_numerics/random/uniform_real_distribution/operators/64351.cc
Fixed on trunk so far.
Author: redi Date: Tue Mar 28 17:18:42 2017 New Revision: 246549 URL: https://gcc.gnu.org/viewcvs?rev=246549&root=gcc&view=rev Log: PR libstdc++/80137 use std::nextafter instead of looping PR libstdc++/80137 * include/bits/random.tcc (generate_canonical): Use std::nextafter or numeric_limits::epsilon() to reduce out-of-range values. * testsuite/26_numerics/random/uniform_real_distribution/operators/ 64351.cc: Verify complexity requirement is met. Modified: branches/gcc-6-branch/libstdc++-v3/ChangeLog branches/gcc-6-branch/libstdc++-v3/include/bits/random.tcc branches/gcc-6-branch/libstdc++-v3/testsuite/26_numerics/random/uniform_real_distribution/operators/64351.cc
And also for 6.4
Author: redi Date: Thu May 18 14:35:23 2017 New Revision: 248212 URL: https://gcc.gnu.org/viewcvs?rev=248212&root=gcc&view=rev Log: PR libstdc++/80137 use std::nextafter instead of looping Backport from mainline 2017-03-28 Jonathan Wakely <jwakely@redhat.com> PR libstdc++/80137 * include/bits/random.tcc (generate_canonical): Use std::nextafter or numeric_limits::epsilon() to reduce out-of-range values. * testsuite/26_numerics/random/uniform_real_distribution/operators/ 64351.cc: Verify complexity requirement is met. Modified: branches/gcc-6-branch/libstdc++-v3/ChangeLog
(In reply to Jonathan Wakely from comment #9) > Author: redi > Date: Thu May 18 14:35:23 2017 > New Revision: 248212 > > URL: https://gcc.gnu.org/viewcvs?rev=248212&root=gcc&view=rev Doh, I managed to cherry-pick a fix that was already on the branch.