This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[v3] Patch to twister_rand_gen_* to use tr1::random


Hi,

the below should most of the runtime fails which we are seeing on 64-bit machines for ext/pb_ds/regression/*rand, for sure does so on ia64-linux. For the latter one remains but first blush seems a different issue:

terminate called after throwing an instance of 'pb_ds::test::forced_exception'
FAIL: ext/pb_ds/regression/priority_queue_rand.cc execution test


Paolo.

/////////////////
2006-06-17  Ami Tavory  <atavory@gmail.com>
	    Paolo Carlini  <pcarlini@suse.de>

	* testsuite/util/rng/twister_rand_gen.cc: Adapt to simply use
	tr1::mt19937.
	* testsuite/util/rng/twister_rand_gen.hpp: Likewise.
Index: testsuite/util/rng/twister_rand_gen.cc
===================================================================
--- testsuite/util/rng/twister_rand_gen.cc	(revision 114727)
+++ testsuite/util/rng/twister_rand_gen.cc	(working copy)
@@ -13,10 +13,10 @@
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 // General Public License for more details.
 
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING.  If not, write to
-// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
-// MA 02111-1307, USA.
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
 
 // As a special exception, you may use this file as part of a free
 // software library without restriction.  Specifically, if other files
@@ -40,82 +40,51 @@
 // warranty.
 
 /**
- * @file twister_rand_gen.cpp
- * Contains a random number generator invented and implemented by
- *    Makoto Matsumoto
- *    (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)
+ * @file twister_rand_gen.cc
  */
 
 #include <util/rng/twister_rand_gen.hpp>
 #include <ctime>
-#include <iostream>
 
 namespace pb_ds
 {
   namespace test
   {
-#ifdef TWISTER_RAND_GEN_DEBUG
+#ifdef PB_DS_TWISTER_RAND_GEN_DEBUG
 #define PB_DS_DBG_ASSERT(X) assert(X)
 #define PB_DS_DBG_VERIFY(X) assert(X)
 #define PB_DS_DBG_ONLY(X) X
-#else // #ifdef TWISTER_RAND_GEN_DEBUG
-#define PB_DS_DBG_ASSERT(X)
+#else // #ifdef PB_DS_TWISTER_RAND_GEN_DEBUG
+#define PB_DS_DBG_ASSERT(X) 
 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
 #define PB_DS_DBG_ONLY(X) ;
-#endif // #ifdef TWISTER_RAND_GEN_DEBUG
+#endif // #ifdef PB_DS_TWISTER_RAND_GEN_DEBUG
 
-    enum
-      {
-	mers_n = 624,
-	mers_m = 397,
-	mers_r = 31,
-	mers_u = 11,
-	mers_s = 7,
-	mers_t = 15,
-	mers_l = 18,
-	mers_a = 0x9908B0DF,
-	mers_b = 0x9D2C5680,
-	mers_c = 0xEFC60000
-      };
-
     twister_rand_gen::
-    twister_rand_gen(unsigned long seed)
-    { init(seed); }
+    twister_rand_gen(unsigned int seed)
+    : m_base_generator(seed)
+    {
+      // Do nothing.
+    }
 
     void
     twister_rand_gen::
-    init(unsigned long seed)
-    {
-      m_a_mt[0]= seed;
+    init(unsigned int seed)
+    { m_base_generator.seed(seed); }
 
-      for (m_mti=1; m_mti < mers_n; ++m_mti)
-	m_a_mt[m_mti] = (1812433253UL* (m_a_mt[m_mti-1] ^ (m_a_mt[m_mti-1] >> 30)) + m_mti);
-
-      union
-      {
-	double m_f;
-	unsigned long m_a[2];
-      } u;
-
-      u.m_f = 1.0;
-
-      if (u.m_a[1] == 0x3FF00000)
-	m_endianess = little;
-      else if (u.m_a[0] == 0x3FF00000)
-	m_endianess = big;
-      else
-	m_endianess = none;
-    }
-
     unsigned long
     twister_rand_gen::
     get_unsigned_long(unsigned long min, unsigned long max)
     {
       PB_DS_DBG_ASSERT(max >= min);
+
       const double prob = get_prob();
-      const unsigned long rand_word =(unsigned long)((max - min+ 1)*  prob) + min;
 
+      const unsigned long rand_word = 
+	(unsigned long)((max - min + 1) * prob) + min;
+
       PB_DS_DBG_ASSERT(rand_word <= max);
+
       return rand_word;
     }
 
@@ -123,79 +92,20 @@
     twister_rand_gen::
     get_prob()
     {
-      union
-      {
-	double m_f;
-	unsigned long m_a[2];
-      } u;
+      const double eng_min = m_base_generator.min();
+      const double eng_range =
+	static_cast<const double>(m_base_generator.max() - eng_min);
 
-      unsigned long rand_word = get_unsigned_long_imp();
+      const double eng_res =
+	static_cast<const double>(m_base_generator() - eng_min);
 
-      double ret;
+      const double ret = eng_res / eng_range;
 
-      switch(m_endianess)
-	{
-	case little:
-	  u.m_a[0] =    rand_word << 20;
-	  u.m_a[1] = (rand_word >> 12) | 0x3FF00000;
-	  ret = u.m_f - 1.0;
-	  break;
-	case big:
-	  u.m_a[1] =    rand_word << 20;
-	  u.m_a[0] = (rand_word >> 12) | 0x3FF00000;
-	  ret = u.m_f - 1.0;
-	  break;
-	case none:
-	default:
-	  break;
-	}
+      PB_DS_DBG_ASSERT(ret >=0 && ret <= 1);
 
-      ret = (double)rand_word * (1./((double)(unsigned long)(-1L)+1.));
-
-      PB_DS_DBG_ASSERT(ret >= 0);
-      PB_DS_DBG_ASSERT(ret <= 1);
-
       return ret;
     }
 
-    unsigned long
-    twister_rand_gen::
-    get_unsigned_long_imp()
-    {
-      unsigned long y;
-      if (m_mti >= mers_n)
-	{
-	  const unsigned long LOWER_MASK = (1LU << mers_r) - 1;
-	  const unsigned long UPPER_MASK = static_cast<unsigned long>(-1L << mers_r);
-	  static const unsigned long m_a_mag01[2] = {0, mers_a};
-
-	  unsigned long kk;
-	  for (kk=0; kk < mers_n-mers_m; ++kk)
-	    {
-	      y = (m_a_mt[kk]&  UPPER_MASK) | (m_a_mt[kk+1]&  LOWER_MASK);
-	      m_a_mt[kk] = m_a_mt[kk+mers_m] ^ (y >> 1) ^ m_a_mag01[y&  1];
-	    }
-
-	  for (; kk < mers_n-1; ++kk)
-	    {
-	      y = (m_a_mt[kk]&  UPPER_MASK) | (m_a_mt[kk+1]&  LOWER_MASK);
-	      m_a_mt[kk] = m_a_mt[kk+(mers_m-mers_n)] ^ (y >> 1) ^ m_a_mag01[y&  1];
-	    }
-
-	  y = (m_a_mt[mers_n-1]&  UPPER_MASK) | (m_a_mt[0]&  LOWER_MASK);
-	  m_a_mt[mers_n-1] = m_a_mt[mers_m-1] ^ (y >> 1) ^ m_a_mag01[y&  1];
-	  m_mti = 0;
-	}
-
-      y = m_a_mt[m_mti++];
-
-      y ^=    y >> mers_u;
-      y ^= (y << mers_s)&  mers_b;
-      y ^= (y << mers_t)&  mers_c;
-      y ^=    y >> mers_l;
-      return y;
-    }
-
 #undef PB_DS_DBG_ASSERT
 #undef PB_DS_DBG_VERIFY
 #undef PB_DS_DBG_ONLY
Index: testsuite/util/rng/twister_rand_gen.hpp
===================================================================
--- testsuite/util/rng/twister_rand_gen.hpp	(revision 114727)
+++ testsuite/util/rng/twister_rand_gen.hpp	(working copy)
@@ -13,10 +13,10 @@
 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 // General Public License for more details.
 
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING.  If not, write to
-// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
-// MA 02111-1307, USA.
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
 
 // As a special exception, you may use this file as part of a free
 // software library without restriction.  Specifically, if other files
@@ -41,9 +41,6 @@
 
 /**
  * @file twister_rand_gen.hpp
- * Contains a random number generator invented and implemented by
- *    Makoto Matsumoto
- *    (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)
  */
 
 #ifndef PB_DS_TWISTER_RAND_GEN_HPP
@@ -51,6 +48,7 @@
 
 #include <ctime>
 #include <limits.h>
+#include <tr1/random>
 
 namespace pb_ds
 {
@@ -58,51 +56,29 @@
   {
     class twister_rand_gen
     {
-    private:
-      enum
-	{
-	  mers_n = 624,
-	  mers_m = 397,
-	  mers_r = 31,
-	  mers_u = 11,
-	  mers_s = 7,
-	  mers_t = 15,
-	  mers_l = 18,
-	  mers_a = 0x9908B0DF,
-	  mers_b = 0x9D2C5680,
-	  mers_c = 0xEFC60000
-	};
-
-      unsigned long m_a_mt[mers_n];
-      unsigned long m_mti;
-
-      enum endianess_type
-	{
-	  little,
-	  big,
-	  none
-	};
-
-      endianess_type m_endianess;
-
-      unsigned long
-      get_unsigned_long_imp();
-
     public:
-      twister_rand_gen(unsigned long seed = static_cast<unsigned long>(std::time(0)));
+      twister_rand_gen(unsigned int seed = 
+		       static_cast<unsigned int>(std::time(0)));
 
       void
-      init(unsigned long seed);
+      init(unsigned int seed);
 
-      static unsigned long
+      static unsigned int
       get_time_determined_seed()
-      { return (static_cast<unsigned long>(std::time(0))); }
+      { return(static_cast<unsigned int>(std::time(0))); }
 
       unsigned long
-      get_unsigned_long(unsigned long min = 0, unsigned long max = UINT_MAX - 1);
+      get_unsigned_long(unsigned long min = 0, 
+			unsigned long max = UINT_MAX - 1);
 
       double
       get_prob();
+
+    private:
+      typedef std::tr1::mt19937 base_generator_t;
+
+    private:
+      base_generator_t m_base_generator;
     };
   } // namespace test
 } // namespace pb_ds

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]