public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "debian-gcc at lists dot debian dot org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/43660] New: range of random-number generator seems wrong/confusing Date: Tue, 06 Apr 2010 01:56:00 -0000 [thread overview] Message-ID: <bug-43660-5724@http.gcc.gnu.org/bugzilla/> (raw) [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
next reply other threads:[~2010-04-06 1:56 UTC|newest] Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top 2010-04-06 1:56 debian-gcc at lists dot debian dot org [this message] 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
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-43660-5724@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).