re PR libstdc++/33815 (tr1::uniform_int isn't uniform)

2007-10-19  Paolo Carlini  <pcarlini@suse.de>

	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

3 files changed, 55 insertions, 21 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 847b69e..2b783da 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,21 +1,31 @@
+2007-10-30  Paolo Carlini  <pcarlini@suse.de>
+
+	* 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  <bkoz@redhat.com>
 
-	*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  <bkoz@redhat.com>
 	
-	*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  <bkoz@redhat.com>
  
diff --git a/libstdc++-v3/include/tr1_impl/random b/libstdc++-v3/include/tr1_impl/random
index 7b9b951..4ce7d8b 100644
--- a/libstdc++-v3/include/tr1_impl/random
+++ b/libstdc++-v3/include/tr1_impl/random
@@ -1603,17 +1603,7 @@ _GLIBCXX_BEGIN_NAMESPACE_TR1
       template<typename _UniformRandomNumberGenerator>
         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<typename
-	    _UniformRandomNumberGenerator::result_type>::__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<typename _UniformRandomNumberGenerator>
         result_type
diff --git a/libstdc++-v3/include/tr1_impl/random.tcc b/libstdc++-v3/include/tr1_impl/random.tcc
index e57d609..2b0f695 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<typename _IntType>
+    template<typename _UniformRandomNumberGenerator>
+      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<typename
+	  _UniformRandomNumberGenerator::result_type>::__type __urntype;
+	typedef typename __gnu_cxx::__add_unsigned<result_type>::__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<typename _IntType, typename _CharT, typename _Traits>
     std::basic_ostream<_CharT, _Traits>&
     operator<<(std::basic_ostream<_CharT, _Traits>& __os,