[Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing

[Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing

[debian-gcc at lists dot debian dot org]

[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

[Bug libstdc++/43660] range of random-number generator seems wrong/confusing

[redi at gcc dot gnu dot org]

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

[Bug libstdc++/43660] range of random-number generator seems wrong/confusing

[redi at gcc dot gnu dot org]

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

[Bug libstdc++/43660] range of random-number generator seems wrong/confusing

[redi at gcc dot gnu dot org]

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

[Bug libstdc++/43660] range of random-number generator seems wrong/confusing

[paolo dot carlini at oracle dot com]

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

[Bug libstdc++/43660] range of random-number generator seems wrong/confusing

[redi at gcc dot gnu.org]

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.