From ebb82e27513e78bac987eda8a6cca289be3ff43d Mon Sep 17 00:00:00 2001 From: Paolo Carlini Date: Tue, 30 Oct 2007 13:05:26 +0000 Subject: [PATCH] re PR libstdc++/33815 (tr1::uniform_int isn't uniform) 2007-10-19 Paolo Carlini PR libstdc++/33815 * include/tr1_impl/random (uniform_int<>::_M_call(_UniformRandomNumberGenerator&, result_type, result_type, true_type)): Avoid the modulo (which uses the low-order bits). From-SVN: r129769 --- libstdc++-v3/ChangeLog | 30 ++++++++++++++------- libstdc++-v3/include/tr1_impl/random | 12 +-------- libstdc++-v3/include/tr1_impl/random.tcc | 34 ++++++++++++++++++++++++ 3 files changed, 55 insertions(+), 21 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 847b69e71d8..2b783daf8bb 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,21 +1,31 @@ +2007-10-30 Paolo Carlini + + * include/tr1_impl/random (uniform_int<>:: + _M_call(_UniformRandomNumberGenerator&, result_type, result_type, + true_type)): Only declare. + * include/tr1_impl/random.tcc (uniform_int<>:: + _M_call(_UniformRandomNumberGenerator&, result_type, result_type, + true_type)): Re-do, unbiased for the currently supported ranges; + add comment. + 2007-10-30 Benjamin Kosnik - *docs/html/ext/pb_ds/multimap_text_insert_timing_test_small.html: + * docs/html/ext/pb_ds/multimap_text_insert_timing_test_small.html: Correct filename. - *docs/html/ext/pb_ds/multimap_text_find_timing_test_large.html: Same. - *docs/html/ext/pb_ds/ + * docs/html/ext/pb_ds/multimap_text_find_timing_test_large.html: Same. + * docs/html/ext/pb_ds/ multimap_text_insert_mem_usage_test_small.html: Same. - *docs/html/ext/pb_ds/multimap_text_insert_timing_test_large.html: Same. - *docs/html/ext/pb_ds/ + * docs/html/ext/pb_ds/multimap_text_insert_timing_test_large.html: Same. + * docs/html/ext/pb_ds/ multimap_text_insert_mem_usage_test_large.html: Same. - *docs/html/ext/pb_ds/multimap_text_find_timing_test_small.html: Same. + * docs/html/ext/pb_ds/multimap_text_find_timing_test_small.html: Same. 2007-10-30 Benjamin Kosnik - *include/Makefile.am (PCHFLAGS): Remove -Wno-deprecated. - *include/Makefile.in: Regenerate. - - *include/std/memory: Remove extraneous include. + * include/Makefile.am (PCHFLAGS): Remove -Wno-deprecated. + * include/Makefile.in: Regenerate. + + * include/std/memory: Remove extraneous include. 2007-10-29 Benjamin Kosnik diff --git a/libstdc++-v3/include/tr1_impl/random b/libstdc++-v3/include/tr1_impl/random index 7b9b951f74a..4ce7d8b4c47 100644 --- a/libstdc++-v3/include/tr1_impl/random +++ b/libstdc++-v3/include/tr1_impl/random @@ -1603,17 +1603,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 template result_type _M_call(_UniformRandomNumberGenerator& __urng, - result_type __min, result_type __max, true_type) - { - // XXX Must be fixed to also work when __urng.max() - __urng.min() - // is smaller than __max - __min. - typedef typename __gnu_cxx::__add_unsigned::__type __utype; - return result_type((__max - __min + 1.0L) - * (__utype(__urng()) - __utype(__urng.min())) - / (__utype(__urng.max()) - - __utype(__urng.min()) + 1.0L)) + __min; - } + result_type __min, result_type __max, true_type); template result_type diff --git a/libstdc++-v3/include/tr1_impl/random.tcc b/libstdc++-v3/include/tr1_impl/random.tcc index e57d609ef5e..2b0f6957b14 100644 --- a/libstdc++-v3/include/tr1_impl/random.tcc +++ b/libstdc++-v3/include/tr1_impl/random.tcc @@ -750,6 +750,40 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1 } + template + template + typename uniform_int<_IntType>::result_type + uniform_int<_IntType>:: + _M_call(_UniformRandomNumberGenerator& __urng, + result_type __min, result_type __max, true_type) + { + // XXX Must be fixed to work well for *arbitrary* __urng.max(), + // __urng.min(), __max, __min. Currently works fine only in the + // most common case __urng.max() - __urng.min() >= __max - __min, + // with __urng.max() > __urng.min() >= 0. + typedef typename __gnu_cxx::__add_unsigned::__type __urntype; + typedef typename __gnu_cxx::__add_unsigned::__type + __utype; + typedef typename __gnu_cxx::__conditional_type<(sizeof(__urntype) + > sizeof(__utype)), + __urntype, __utype>::__type __uctype; + + result_type __ret; + + const __urntype __urnmin = __urng.min(); + const __urntype __urnmax = __urng.max(); + const __urntype __urnrange = __urnmax - __urnmin; + const __uctype __urange = __max - __min; + const __uctype __udenom = (__urnrange <= __urange + ? 1 : __urnrange / (__urange + 1)); + do + __ret = (__urntype(__urng()) - __urnmin) / __udenom; + while (__ret > __max - __min); + + return __ret + __min; + } + template std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& __os, -- 2.30.2