2006-06-05 Paolo Carlini <pcarlini@suse.de>

	* include/tr1/random.tcc (Max::value()): Cast 1 to Tp(1) and
	adjust shift count to w; rename as Max_w.
	(struct Mod_w): New.
	(mersenne_twister<>::seed(Gen&, false_type): Use the latter.
	(mersenne_twister<>::operator()()): Fix ~0ul to ~_UInt().
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/default.cc: Fix ~0ul to 2^32-1.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/gen1.cc: Likewise.

2006-06-05  Stephen M. Webb  <stephen.webb@bregmasoft.com>

	* include/tr1/random: New.
	* include/tr1/random.tcc: Likewise.
	* include/Makefile.am: Add.
	* testsuite/tr1/5_numerical_facilies/random/ranlux3.cc: New.
	* testsuite/tr1/5_numerical_facilies/random/ranlux4.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mt19937.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/variate_generator/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	cons/seed1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	cons/seed2.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	cons/default.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	cons/gen1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	operators/equal.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	operators/not_equal.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/subtract_with_carry/
	operators/serialize.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/uniform_real/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/discard_block/
	requirements/requirements.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	cons/seed1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	cons/seed2.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	cons/default.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	cons/gen1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	requirements/non_uint_neg.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	operators/equal.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	operators/not_equal.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/linear_congruential/
	operators/serialize.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/xor_combine/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/minstd_rand.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/minstd_rand0.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/uniform_int/
	cons/range.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/uniform_int/
	cons/default.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/uniform_int/
	cons/range_neg.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/uniform_int/
	requirements/typedefs.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/seed1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/seed2.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/default.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	cons/gen1.cc: Likewise.
	* testsuite/tr1/5_numerical_facilies/random/mersenne_twister/
	requirements/typedefs.cc: Likewise.
	* include/Makefile.in: Regenerate.
	* testsuite/tr1/headers.cc: Update.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@114384 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 422 insertions, 0 deletions

diff --git a/libstdc++-v3/include/tr1/random.tcc b/libstdc++-v3/include/tr1/random.tcc
new file mode 100644
index 00000000000..b78bb4ec1af
--- /dev/null
+++ b/libstdc++-v3/include/tr1/random.tcc
@@ -0,0 +1,422 @@
+// random number generation (out of line) -*- C++ -*-
+
+// Copyright (C) 2006 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// 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, 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 instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <limits>
+
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE(tr1)
+
+  /*
+   * Implementation-space details.
+   */
+  namespace _Private
+  {
+    // General case for x = (ax + c) mod m -- use Schrage's algorithm to avoid
+    // integer overflow.
+    //
+    // Because a and c are compile-time integral constants the compiler kindly
+    // elides any unreachable paths.
+    //
+    // Preconditions:  a > 0, m > 0.
+    //
+    template<typename _Tp, _Tp a, _Tp c, _Tp m, bool _m_is_zero>
+      struct Mod
+      {
+	static _Tp
+	calc(_Tp x)
+	{
+	  if (a == 1)
+	    x %= m;
+	  else
+	    {
+	      static const _Tp q = m / a;
+	      static const _Tp r = m % a;
+	      
+	      _Tp t1 = a * (x % q);
+	      _Tp t2 = r * (x / q);
+	      if (t1 >= t2)
+		x = t1 - t2;
+	      else
+		x = m - t2 + t1;
+	    }
+
+	  if (c != 0)
+	    {
+	      const _Tp d = m - x;
+	      if (d > c)
+		x += c;
+	      else
+		x = c - d;
+	    }
+	  return x;
+	}
+      };
+
+    // Special case for m==0 -- use unsigned integer overflow as modulo
+    // operator.
+    template<typename _Tp, _Tp a, _Tp c, _Tp m>
+      struct Mod<_Tp, a, c, m, true>
+      {
+	static _Tp
+	calc(_Tp x)
+	{ return a * x + c; }
+      };
+
+    // Dispatch based on modulus value to prevent divide-by-zero compile-time
+    // errors when m == 0.
+    template<typename _Tp, _Tp a, _Tp c, _Tp m>
+      inline _Tp
+      mod(_Tp x)
+      { return Mod<_Tp, a, c, m, m == 0>::calc(x); }
+
+    // Like the above, for a==1, c==0, in terms of w.
+    template<typename _Tp, _Tp w, bool>
+      struct Mod_w
+      {
+	static _Tp
+	calc(_Tp x)
+	{ return x % (_Tp(1) << w); }
+      };
+
+    template<typename _Tp, _Tp w>
+      struct Mod_w<_Tp, w, true>
+      {
+	static _Tp
+	calc(_Tp x)
+	{ return x; }
+      };
+
+    // Selector to return the maximum value possible that will fit in 
+    // @p w bits of @p _Tp.
+    template<typename _Tp, _Tp w, bool>
+      struct Max_w
+      {
+	static _Tp
+	value()
+	{ return (_Tp(1) << w) - 1; }
+      };
+
+    template<typename _Tp, _Tp w>
+      struct Max_w<_Tp, w, true>
+      {
+	static _Tp
+	value()
+	{ return std::numeric_limits<_Tp>::max(); }
+      };
+
+  } // namespace _Private
+
+
+  /**
+   * Constructs the LCR engine with integral seed @p x0.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    linear_congruential<UIntType, a, c, m>::
+    linear_congruential(unsigned long x0)
+    { this->seed(x0); }
+
+  /**
+   * Constructs the LCR engine with seed generated from @p g.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    template<class Gen>
+      linear_congruential<UIntType, a, c, m>::
+      linear_congruential(Gen& g)
+      { this->seed(g); }
+
+  /**
+   * Seeds the LCR with integral value @p x0, adjusted so that the 
+   * ring identity is never a member of the convergence set.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    void
+    linear_congruential<UIntType, a, c, m>::
+    seed(unsigned long x0)
+    {
+      if ((_Private::mod<UIntType, 1, 0, m>(c) == 0)
+	  && (_Private::mod<UIntType, 1, 0, m>(x0) == 0))
+	m_x = _Private::mod<UIntType, 1, 0, m>(1);
+      else
+	m_x = _Private::mod<UIntType, 1, 0, m>(x0);
+    }
+
+  /**
+   * Seeds the LCR engine with a value generated by @p g.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    template<class Gen>
+      void
+      linear_congruential<UIntType, a, c, m>::
+      seed(Gen& g, false_type)
+      {
+	UIntType x0 = g();
+	if ((_Private::mod<UIntType, 1, 0, m>(c) == 0)
+	    && (_Private::mod<UIntType, 1, 0, m>(x0) == 0))
+	  m_x = _Private::mod<UIntType, 1, 0, m>(1);
+	else
+	  m_x = _Private::mod<UIntType, 1, 0, m>(x0);
+      }
+
+  /**
+   * Returns a value that is less than or equal to all values potentially
+   * returned by operator(). The return value of this function does not
+   * change during the lifetime of the object..
+   *
+   * The minumum depends on the @p c parameter: if it is zero, the
+   * minimum generated must be > 0, otherwise 0 is allowed.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    typename linear_congruential<UIntType, a, c, m>::result_type
+    linear_congruential<UIntType, a, c, m>::
+    min() const
+    { return (_Private::mod<UIntType, 1, 0, m>(c) == 0) ? 1 : 0; }
+
+  /**
+   * Gets the maximum possible value of the generated range.
+   *
+   * For a linear congruential generator, the maximum is always @p m - 1.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    typename linear_congruential<UIntType, a, c, m>::result_type
+    linear_congruential<UIntType, a, c, m>::
+    max() const
+    { return (m == 0) ? std::numeric_limits<UIntType>::max() : (m - 1); }
+
+  /**
+   * Gets the next generated value in sequence.
+   */
+  template<class UIntType, UIntType a, UIntType c, UIntType m>
+    typename linear_congruential<UIntType, a, c, m>::result_type
+    linear_congruential<UIntType, a, c, m>::
+    operator()()
+    {
+      m_x = _Private::mod<UIntType, a, c, m>(m_x);
+      return m_x;
+    }
+
+
+  template<class _UInt, int w, int n, int m, int r,
+	   _UInt a, int u, int s,
+	   _UInt b, int t, _UInt c, int l>
+    void
+    mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::
+    seed(unsigned long value)
+    {
+      if (value == 0)
+	value = 4357;
+      
+#if 0
+      // @todo handle case numeric_limits<_UInt>::digits > 32
+      if (std::numeric_limits<_UInt>::digits > 32)
+	{
+	  std::tr1::linear_congruential<unsigned long, 69069, 0, 2**32> lcg(value);
+	  seed(lcg);
+	}
+      else
+	{
+	  std::tr1::linear_congruential<unsigned long, 69069, 0, 0> lcg(value);
+	  seed(lcg);
+	}
+#else
+      std::tr1::linear_congruential<unsigned long, 69069, 0, 0> lcg(value);
+      seed(lcg);
+#endif
+    }
+
+
+  template<class _UInt, int w, int n, int m, int r,
+	   _UInt a, int u, int s,
+	   _UInt b, int t, _UInt c, int l>
+    template<class Gen>
+      void
+      mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::
+      seed(Gen& gen, false_type)
+      {
+	using _Private::Mod_w;
+	using std::numeric_limits;
+
+	for (int i = 0; i < state_size; ++i)
+	  _M_x[i] = Mod_w<_UInt, w,
+	                  w == numeric_limits<_UInt>::digits>::calc(gen());
+	_M_p = state_size + 1;
+      }
+
+  template<class _UInt, int w, int n, int m, int r,
+	   _UInt a, int u, int s,
+	   _UInt b, int t, _UInt c, int l>
+    typename
+    mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::result_type
+    mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::
+    max() const
+    {
+      using _Private::Max_w;
+      using std::numeric_limits;
+      return Max_w<_UInt, w, w == numeric_limits<_UInt>::digits>::value();
+    }
+
+
+  template<class _UInt, int w, int n, int m, int r,
+	   _UInt a, int u, int s,
+	   _UInt b, int t, _UInt c, int l>
+    typename
+    mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::result_type
+    mersenne_twister<_UInt, w, n, m, r, a, u, s, b, t, c, l>::
+    operator()()
+    {
+      // reload the vector - cost is O(n) amortized over n calls.
+      if (_M_p >= state_size)
+	{
+	  const _UInt upper_mask = (~_UInt()) << r;
+	  const _UInt lower_mask = ~upper_mask;
+
+	  for (int k = 0; k < (n - m); ++k)
+	    {
+	      _UInt y = (_M_x[k] & upper_mask) | (_M_x[k + 1] & lower_mask);
+	      _M_x[k] = _M_x[k + m] ^ (y >> 1) ^ ((y & 0x01) ? a : 0);
+	    }
+
+	  for (int k = (n - m); k < (n - 1); ++k)
+	    {
+	      _UInt y = (_M_x[k] & upper_mask) | (_M_x[k + 1] & lower_mask);
+	      _M_x[k] = _M_x[k + (m - n)] ^ (y >> 1) ^ ((y & 0x01) ? a : 0);
+	    }
+
+	  _M_p = 0;
+	}
+
+      // Calculate x(i)
+      result_type y = _M_x[_M_p++];
+      y ^= (y >> u);
+      y ^= (y << s) & b;
+      y ^= (y << t) & c;
+      y ^= (y >> l);
+      
+      return y;
+    }
+
+
+  template<typename _IntType, _IntType m, int s, int r>
+    void
+    subtract_with_carry<_IntType, m, s, r>::
+    seed(_IntType __value)
+    {
+      std::tr1::linear_congruential<unsigned long, 40014, 0, 2147483563>
+	lcg(__value);
+      
+      for (int i = 0; i < long_lag; ++i)
+	_M_x[i] = _Private::mod<_IntType, 1, 0, modulus>(lcg());
+	
+      _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
+      _M_p = 0;
+    }
+
+  
+  //
+  // This implementation differs from the tr1 spec because the tr1 spec refused
+  // to make any sense to me:  the exponent of the factor in the spec goes from
+  // 1 to (n-1), but it would only make sense to me if it went from 0 to (n-1).
+  //
+  // This algorithm is still problematic because it can overflow left right and
+  // center.
+  //
+  template<typename _IntType, _IntType __m, int __s, int __r>
+    template<class Gen>
+    void
+    subtract_with_carry<_IntType, __m, __s, __r>::
+    seed(Gen& gen, false_type)
+    {
+      const int n = (std::numeric_limits<_IntType>::digits + 31) / 32;
+      for (int i = 0; i < long_lag; ++i)
+	{
+	  _M_x[i] = 0;
+	  unsigned long factor = 1;
+	  for (int j = 0; j < n; ++j)
+	    {
+	      _M_x[i] += gen() * factor;
+	      factor *= 0x80000000;
+	    }
+	  _M_x[i] = _Private::mod<_IntType, 1, 0, modulus>(_M_x[i]);
+	}
+      _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
+      _M_p = 0;
+    }
+  
+
+  template<typename _IntType, _IntType __m, int __s, int __r>
+    typename subtract_with_carry<_IntType, __m, __s, __r>::result_type
+    subtract_with_carry<_IntType, __m, __s, __r>::
+    operator()()
+    {
+      // derive short lag index from current index
+      int ps = _M_p - short_lag;
+      if (ps < 0) ps += long_lag;
+      
+      // calculate new x(i) without overflow or division
+      _IntType xi;
+      if (_M_x[ps] >= _M_x[_M_p] + _M_carry)
+	{
+	  xi = _M_x[ps] - _M_x[_M_p] - _M_carry;
+	  _M_carry = 0;
+	}
+      else
+	{
+	  xi = modulus - _M_x[_M_p] - _M_carry + _M_x[ps];
+	  _M_carry = 1;
+	}
+      _M_x[_M_p++] = xi;
+      
+      // adjust current index to loop around in ring buffer
+      if (_M_p >= long_lag)
+	_M_p = 0;
+      
+      return xi;
+    }
+
+  
+  template<class _E, int __p, int __r>
+    typename discard_block<_E, __p, __r>::result_type
+    discard_block<_E, __p, __r>::
+    operator()()
+    {
+      if (_M_n >= used_block)
+	{
+	  while (_M_n < block_size)
+	    {
+	      _M_b();
+	      ++_M_n;
+	    }
+	  _M_n = 0;
+	}
+      ++_M_n;
+      return _M_b();
+    }
+
+_GLIBCXX_END_NAMESPACE
+}