Bug#568616: libstdc++6-4.5-dev: range of random-number generator seems wrong/confusing
Package: libstdc++6-4.5-dev
Version: 4.5-20100202-1
Severity: normal
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;
}
-- System Information:
Debian Release: squeeze/sid
APT prefers unstable
APT policy: (500, 'unstable'), (500, 'testing'), (101, 'experimental')
Architecture: amd64 (x86_64)
Kernel: Linux 2.6.32-trunk-amd64 (SMP w/4 CPU cores)
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash
Versions of packages libstdc++6-4.5-dev depends on:
ii g++-4.5 4.5-20100202-1 The GNU C++ compiler
ii gcc-4.5-base 4.5-20100202-1 The GNU Compiler Collection (base
ii libc6-dev 2.10.2-5 Embedded GNU C Library: Developmen
ii libstdc++6 4.5-20100202-1 The GNU Standard C++ Library v3
libstdc++6-4.5-dev recommends no packages.
Versions of packages libstdc++6-4.5-dev suggests:
pn libstdc++6-4.5-doc <none> (no description available)
-- no debconf information
Reply to: