random (xor_combine<>::_M_initialize_max_aux): New.

2006-10-01  Paolo Carlini  <pcarlini@suse.de>

	* include/tr1/random (xor_combine<>::_M_initialize_max_aux): New.
	(xor_combine<>::operator()()): Tweak per N2079.
	* include/tr1/random.tcc (xor_combine<>::_M_initialize_max_aux):
	Define.
	(xor_combine<>::_M_initialize_max): Use it.
	* testsuite/tr1/5_numerical_facilities/random/xor_combine/
	cons/default.cc: Adjust.
	* docs/html/ext/tr1.html: Adjust.

From-SVN: r117353

5 files changed, 73 insertions, 25 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 99eff89..8115f0d 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,16 @@
 2006-10-01  Paolo Carlini  <pcarlini@suse.de>
 
+	* include/tr1/random (xor_combine<>::_M_initialize_max_aux): New.
+	(xor_combine<>::operator()()): Tweak per N2079.
+	* include/tr1/random.tcc (xor_combine<>::_M_initialize_max_aux):
+	Define.
+	(xor_combine<>::_M_initialize_max): Use it.
+	* testsuite/tr1/5_numerical_facilities/random/xor_combine/
+	cons/default.cc: Adjust.
+	* docs/html/ext/tr1.html: Adjust.
+
+2006-10-01  Paolo Carlini  <pcarlini@suse.de>
+
 	* include/ext/type_traits.h: Avoid _T, badname for some targets;
 	also avoid plain T.
 
diff --git a/libstdc++-v3/docs/html/ext/tr1.html b/libstdc++-v3/docs/html/ext/tr1.html
index 78f130d..d8ae397 100644
--- a/libstdc++-v3/docs/html/ext/tr1.html
+++ b/libstdc++-v3/docs/html/ext/tr1.html
@@ -706,7 +706,7 @@ release.
       <td>done</td>
       <td></td>
       <td></td>
-      <td>Buggy min() and max()</td>
+      <td>operator()() per N2079</td>
     </tr>
     <tr>
       <td>5.1.5</td>
@@ -2307,7 +2307,7 @@ permitted in any medium, provided this notice is preserved.
 <table width="100%" border="0">
 <tr>
   <td>
-    <!-- IGNORE DIFF -->Last modified 2006-08-25
+    <!-- IGNORE DIFF -->Last modified 2006-10-01
   </td>
   <td align="right" valign="bottom">
     <a href="http://validator.w3.org/check/referer">
diff --git a/libstdc++-v3/include/tr1/random b/libstdc++-v3/include/tr1/random
index 05286ee..543378e 100644
--- a/libstdc++-v3/include/tr1/random
+++ b/libstdc++-v3/include/tr1/random
@@ -1262,7 +1262,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
 
     public:
       /** The type of the generated random value. */
-      typedef typename __gnu_cxx::__conditional_type<(sizeof(_Result_type1) > sizeof(_Result_type2)),
+      typedef typename __gnu_cxx::__conditional_type<(sizeof(_Result_type1)
+						      > sizeof(_Result_type2)),
 	_Result_type1, _Result_type2>::__type result_type;
 
       // parameter values
@@ -1310,7 +1311,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
       base2() const
       { return _M_b2; }
 
-      // XXX Per N2032, but aren't always right...
       result_type
       min() const
       { return 0; }
@@ -1322,9 +1322,13 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
       /**
        * Gets the next random number in the sequence.
        */
+      // NB: Not exactly the TR1 formula, per N2079 instead.
       result_type
       operator()()
-      { return ((_M_b1() << shift1) ^ (_M_b2() << shift2)); }
+      {
+	return ((result_type(_M_b1() - _M_b1.min()) << shift1)
+		^ (result_type(_M_b2() - _M_b2.min()) << shift2));
+      }
 
       /**
        * Compares two %xor_combine random number generator objects of
@@ -1397,6 +1401,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
       void
       _M_initialize_max();
 
+      result_type
+      _M_initialize_max_aux(result_type, result_type, int);
+
       base1_type  _M_b1;
       base2_type  _M_b2;
       result_type _M_max;
diff --git a/libstdc++-v3/include/tr1/random.tcc b/libstdc++-v3/include/tr1/random.tcc
index fd052fe..46d73da 100644
--- a/libstdc++-v3/include/tr1/random.tcc
+++ b/libstdc++-v3/include/tr1/random.tcc
@@ -619,30 +619,59 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
 		_UniformRandomNumberGenerator2, __s2>::
     _M_initialize_max()
     {
-      const int __lshift = std::abs(__s1 - __s2);
+      const int __w = std::numeric_limits<result_type>::digits;
 
-      result_type __m1 = _M_b1.max() - _M_b1.min();
-      result_type __m2 = _M_b2.max() - _M_b2.min();
+      const result_type __m1 =
+	std::min(result_type(_M_b1.max() - _M_b1.min()),
+		 _Shift<result_type, __w - __s1>::__value - 1);
 
-      // NB: in TR1 s1 is not required to be >= s2.
-      if (__s1 >= __s2)
-	__m1 <<= __lshift;
+      const result_type __m2 =
+	std::min(result_type(_M_b2.max() - _M_b2.min()),
+		 _Shift<result_type, __w - __s2>::__value - 1);
+
+      // NB: In TR1 s1 is not required to be >= s2.
+      if (__s1 < __s2)
+	_M_max = _M_initialize_max_aux(__m2, __m1, __s2 - __s1) << __s1;
       else
-	__m2 <<= __lshift;
+	_M_max = _M_initialize_max_aux(__m1, __m2, __s1 - __s2) << __s2;
+    }
+
+  template<class _UniformRandomNumberGenerator1, int __s1,
+	   class _UniformRandomNumberGenerator2, int __s2>
+    typename xor_combine<_UniformRandomNumberGenerator1, __s1,
+			 _UniformRandomNumberGenerator2, __s2>::result_type
+    xor_combine<_UniformRandomNumberGenerator1, __s1,
+		_UniformRandomNumberGenerator2, __s2>::
+    _M_initialize_max_aux(result_type __a, result_type __b, int __d)
+    {
+      const result_type __two2d = result_type(1) << __d;
+      const result_type __c = __a * __two2d;
 
-      result_type __a = __m1 & __m2;
-      const result_type __b = __m1 | __m2;      
+      if (__a == 0 || __b < __two2d)
+	return __c + __b;
 
-      result_type __c = 0;
-      if (__a)
-	{
-	  result_type __k;
-	  for (__k = 0; __a != 1; __a >>= 1)
-	    ++__k;
-	  __c = (result_type(1) << __k) - 1;
-	}
+      const result_type __t = std::max(__c, __b);
+      const result_type __u = std::min(__c, __b);
+
+      result_type __ub = __u;
+      result_type __p;
+      for (__p = 0; __ub != 1; __ub >>= 1)
+	++__p;
 
-      _M_max = (__c | __b) << __lshift; 
+      const result_type __two2p = result_type(1) << __p;
+      const result_type __k = __t / __two2p;
+
+      if (__k & 1)
+	return (__k + 1) * __two2p - 1;
+
+      if (__c >= __b)
+	return (__k + 1) * __two2p + _M_initialize_max_aux((__t % __two2p)
+							   / __two2d,
+							   __u % __two2p, __d);
+      else
+	return (__k + 1) * __two2p + _M_initialize_max_aux((__u % __two2p)
+							   / __two2d,
+							   __t % __two2p, __d);
     }
 
   template<class _UniformRandomNumberGenerator1, int __s1,
@@ -852,7 +881,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1)
 		      continue;
 		  }
 		else if (__u <= __c3)
-		  // XXX This case not in the book, nor in the Errata...
+		  // NB: This case not in the book, nor in the Errata,
+		  // but should be ok...
 		  __x = -1;
 		else if (__u <= __c4)
 		  __x = 0;
diff --git a/libstdc++-v3/testsuite/tr1/5_numerical_facilities/random/xor_combine/cons/default.cc b/libstdc++-v3/testsuite/tr1/5_numerical_facilities/random/xor_combine/cons/default.cc
index 5ac01b8..83ff51b 100644
--- a/libstdc++-v3/testsuite/tr1/5_numerical_facilities/random/xor_combine/cons/default.cc
+++ b/libstdc++-v3/testsuite/tr1/5_numerical_facilities/random/xor_combine/cons/default.cc
@@ -36,7 +36,7 @@ test01()
     minstd_rand0, 2
     > x;
 
-  VERIFY( x() == 32642 );
+  VERIFY( x() == 32644 );
 }
 
 int main()