public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing
@ 2010-04-06 1:56 debian-gcc at lists dot debian dot org
2010-04-06 10:38 ` [Bug libstdc++/43660] " redi at gcc dot gnu dot org
` (3 more replies)
0 siblings, 4 replies; 6+ messages in thread
From: debian-gcc at lists dot debian dot org @ 2010-04-06 1:56 UTC (permalink / raw)
To: gcc-bugs
[forwarded from http://bugs.debian.org/568616]
Matthias
The random-number distributions in C++0x <random> include a special
"one-shot" facility, where the random bounds can be passed to the
generator function. This is explicitly intended (judging from committee
writings, and source comments in the libstdc++ header files) for use as
a rng generator for std::random_shuffle.
e.g.:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1933.pdf
As best as I can tell, std::random_shuffle wants its random-number
generating functor to return results in the range [0,N), where N is the
parameter it passes to the functor; i.e., the upper-bound is exclusive
(and the lower-bound inclusive).
The <random> implementation in libstdc++ also notes this, e.g., in the
comment on the associated operator() method in the
std::uniform_int_distribution template class:
/**
* Gets a uniform random number in the range @f$[0, n)@f$.
*
* This function is aimed at use with std::random_shuffle.
*/
template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
const param_type& __p);
However, in practice, it actually will return the upper-bound as well;
it seems to treat it as a maximum, rather than an exclusive bound.
For instance, compiling the attached test program (at end of message),
"rand-bug.cc", results in the following output:
$ g++-4.5 -o rand-bug -std=c++0x rand-bug.cc
$ ./rand-bug
trying 1000000 random numbers in range [0,25)...
returned upper-bound (25) 38394 times (should be 0)
[Note that the same issue exists with other ways of invoking using the
generator (e.g., a std::uniform_real_distribution<float> with bounds of
0 and 1 will indeed return 1); but it's less clear its a bug in those
cases (although, for instance, boost's random implementation never
seems to return the upper bound).]
Thanks,
-Miles
Here's the test program:
#include <iostream>
#include <random>
int main ()
{
std::mt19937 rng;
typedef std::uniform_int_distribution<unsigned> dist_type;
dist_type dist;
unsigned num_loops = 1000000;
unsigned upper_bound = 25;
std::cout << "trying " << num_loops << " random numbers in range [0,"
<< upper_bound << ")..." << std::endl;
//
// According to the function documentation for this, it should never
// return the upper bound:
//
// * Gets a uniform random number in the range @f$[0, n)@f$.
// *
// * This function is aimed at use with std::random_shuffle.
//
unsigned returned_upper_bound_count = 0;
for (unsigned i = 0; i < num_loops; i++)
{
unsigned num = dist (rng, dist_type::param_type (0, upper_bound));
if (num == upper_bound)
returned_upper_bound_count++;
}
std::cout << "returned upper-bound (" << upper_bound << ") "
<< returned_upper_bound_count << " times (should be 0)"
<< std::endl;
return 0;
}
--
Summary: range of random-number generator seems wrong/confusing
Product: gcc
Version: 4.5.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: debian-gcc at lists dot debian dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/43660] range of random-number generator seems wrong/confusing
2010-04-06 1:56 [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing debian-gcc at lists dot debian dot org
@ 2010-04-06 10:38 ` redi at gcc dot gnu dot org
2010-04-06 10:41 ` redi at gcc dot gnu dot org
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu dot org @ 2010-04-06 10:38 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from redi at gcc dot gnu dot org 2010-04-06 10:38 -------
n1933 is ancient history, the RNG pieces have changed significantly
In the current draft it says:
"A uniform_int_distribution random number distribution produces random integers
i, a <= i <= b"
So it is a closed interval [a,b] rather than [a,b)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/43660] range of random-number generator seems wrong/confusing
2010-04-06 1:56 [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing debian-gcc at lists dot debian dot org
2010-04-06 10:38 ` [Bug libstdc++/43660] " redi at gcc dot gnu dot org
@ 2010-04-06 10:41 ` redi at gcc dot gnu dot org
2010-04-06 10:54 ` redi at gcc dot gnu dot org
2010-04-06 11:00 ` paolo dot carlini at oracle dot com
3 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu dot org @ 2010-04-06 10:41 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from redi at gcc dot gnu dot org 2010-04-06 10:40 -------
(In reply to comment #0)
> [Note that the same issue exists with other ways of invoking using the
> generator (e.g., a std::uniform_real_distribution<float> with bounds of
> 0 and 1 will indeed return 1); but it's less clear its a bug in those
> cases (although, for instance, boost's random implementation never
> seems to return the upper bound).]
Again, referring to the latest draft:
"A uniform_real_distribution random number distribution produces random numbers
x, a <= x < b"
So that does appear to be a bug
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/43660] range of random-number generator seems wrong/confusing
2010-04-06 1:56 [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing debian-gcc at lists dot debian dot org
2010-04-06 10:38 ` [Bug libstdc++/43660] " redi at gcc dot gnu dot org
2010-04-06 10:41 ` redi at gcc dot gnu dot org
@ 2010-04-06 10:54 ` redi at gcc dot gnu dot org
2010-04-06 11:00 ` paolo dot carlini at oracle dot com
3 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu dot org @ 2010-04-06 10:54 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from redi at gcc dot gnu dot org 2010-04-06 10:53 -------
(In reply to comment #0)
>
> As best as I can tell, std::random_shuffle wants its random-number
> generating functor to return results in the range [0,N), where N is the
> parameter it passes to the functor; i.e., the upper-bound is exclusive
> (and the lower-bound inclusive).
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3056.pdf changes the
third random_shuffle overload to shuffle and changes the requirements
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/43660] range of random-number generator seems wrong/confusing
2010-04-06 1:56 [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing debian-gcc at lists dot debian dot org
` (2 preceding siblings ...)
2010-04-06 10:54 ` redi at gcc dot gnu dot org
@ 2010-04-06 11:00 ` paolo dot carlini at oracle dot com
3 siblings, 0 replies; 6+ messages in thread
From: paolo dot carlini at oracle dot com @ 2010-04-06 11:00 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from paolo dot carlini at oracle dot com 2010-04-06 11:00 -------
Jon is right and recently I removed that old comment from random.h because
indeed was incorrect.
--
paolo dot carlini at oracle dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |RESOLVED
Resolution| |INVALID
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/43660] range of random-number generator seems wrong/confusing
[not found] <bug-43660-4@http.gcc.gnu.org/bugzilla/>
@ 2015-03-09 12:41 ` redi at gcc dot gnu.org
0 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2015-03-09 12:41 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43660
--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #2)
> (In reply to comment #0)
> > [Note that the same issue exists with other ways of invoking using the
> > generator (e.g., a std::uniform_real_distribution<float> with bounds of
> > 0 and 1 will indeed return 1); but it's less clear its a bug in those
> > cases (although, for instance, boost's random implementation never
> > seems to return the upper bound).]
>
> Again, referring to the latest draft:
> "A uniform_real_distribution random number distribution produces random
> numbers x, a <= x < b"
>
> So that does appear to be a bug
PR 64351 deals with that case.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2015-03-09 12:41 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-04-06 1:56 [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing debian-gcc at lists dot debian dot org
2010-04-06 10:38 ` [Bug libstdc++/43660] " redi at gcc dot gnu dot org
2010-04-06 10:41 ` redi at gcc dot gnu dot org
2010-04-06 10:54 ` redi at gcc dot gnu dot org
2010-04-06 11:00 ` paolo dot carlini at oracle dot com
[not found] <bug-43660-4@http.gcc.gnu.org/bugzilla/>
2015-03-09 12:41 ` redi at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).