text: /* boost random/mersenne_twister.hpp header file
   *
   * Copyright Jens Maurer 2000-2001
   * Distributed under the Boost Software License, Version 1.0. (See
   * accompanying file LICENSE_1_0.txt or copy at
   * http://www.boost.org/LICENSE_1_0.txt)
   *
   * See http://www.boost.org for most recent version including documentation.
   *
   * $Id: mersenne_twister.hpp,v 1.2 2007/08/20 21:02:01 aselle Exp $
   *
   * Revision history
   *  2001-02-18  moved to individual header files
   */
  
  #ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP
  #define BOOST_RANDOM_MERSENNE_TWISTER_HPP
  
  #include <iostream>
  #include <algorithm>     // std::copy
  #include <stdexcept>
  #include <boost/config.hpp>
  #include <boost/limits.hpp>
  #include <boost/static_assert.hpp>
  #include <boost/integer_traits.hpp>
  #include <boost/cstdint.hpp>
  #include <boost/random/linear_congruential.hpp>
  #include <boost/detail/workaround.hpp>
  #include <boost/random/detail/ptr_helper.hpp>
  
  namespace boost {
  namespace random {
  
  // http://www.math.keio.ac.jp/matumoto/emt.html
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  class mersenne_twister
  {
  public:
    typedef UIntType result_type;
    BOOST_STATIC_CONSTANT(int, word_size = w);
    BOOST_STATIC_CONSTANT(int, state_size = n);
    BOOST_STATIC_CONSTANT(int, shift_size = m);
    BOOST_STATIC_CONSTANT(int, mask_bits = r);
    BOOST_STATIC_CONSTANT(UIntType, parameter_a = a);
    BOOST_STATIC_CONSTANT(int, output_u = u);
    BOOST_STATIC_CONSTANT(int, output_s = s);
    BOOST_STATIC_CONSTANT(UIntType, output_b = b);
    BOOST_STATIC_CONSTANT(int, output_t = t);
    BOOST_STATIC_CONSTANT(UIntType, output_c = c);
    BOOST_STATIC_CONSTANT(int, output_l = l);
  
    BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
    
    mersenne_twister() { seed(); }
  
  #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x520)
    // Work around overload resolution problem (Gennadiy E. Rozental)
    explicit mersenne_twister(const UIntType& value)
  #else
    explicit mersenne_twister(UIntType value)
  #endif
    { seed(value); }
    template<class It> mersenne_twister(It& first, It last) { seed(first,last); }
  
    template<class Generator>
    explicit mersenne_twister(Generator & gen) { seed(gen); }
  
    // compiler-generated copy ctor and assignment operator are fine
  
    void seed() { seed(UIntType(5489)); }
  
  #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x520)
    // Work around overload resolution problem (Gennadiy E. Rozental)
    void seed(const UIntType& value)
  #else
    void seed(UIntType value)
  #endif
    {
      // New seeding algorithm from 
      // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
      // In the previous versions, MSBs of the seed affected only MSBs of the
      // state x[].
      const UIntType mask = ~0u;
      x[0] = value & mask;
      for (i = 1; i < n; i++) {
        // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106
        x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask;
      }
    }
  
    // For GCC, moving this function out-of-line prevents inlining, which may
    // reduce overall object code size.  However, MSVC does not grok
    // out-of-line definitions of member function templates.
    template<class Generator>
    void seed(Generator & gen)
    {
  #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
      BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed);
  #endif
      // I could have used std::generate_n, but it takes "gen" by value
      for(int j = 0; j < n; j++)
        x[j] = gen();
      i = n;
    }
  
    template<class It>
    void seed(It& first, It last)
    {
      int j;
      for(j = 0; j < n && first != last; ++j, ++first)
        x[j] = *first;
      i = n;
      if(first == last && j < n)
        throw std::invalid_argument("mersenne_twister::seed");
    }
    
    result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }
    result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const
    {
      // avoid "left shift count >= with of type" warning
      result_type res = 0;
      for(int i = 0; i < w; ++i)
        res |= (1u << i);
      return res;
    }
  
    result_type operator()();
    static bool validation(result_type v) { return val == v; }
  
  #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
  
  //#ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS
    template<class CharT, class Traits>
    friend std::basic_ostream<CharT,Traits>&
    operator<<(std::basic_ostream<CharT,Traits>& os, const mersenne_twister& mt)
    {
      for(int j = 0; j < mt.state_size; ++j)
        os << mt.compute(j) << " ";
      return os;
    }
  
    template<class CharT, class Traits>
    friend std::basic_istream<CharT,Traits>&
    operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt)
    {
      for(int j = 0; j < mt.state_size; ++j)
        is >> mt.x[j] >> std::ws;
      // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template
      // value parameter "n" available from the class template scope, so use
      // the static constant with the same value
      mt.i = mt.state_size;
      return is;
    }
  //#endif
  
    friend bool operator==(const mersenne_twister& x, const mersenne_twister& y)
    {
      for(int j = 0; j < state_size; ++j)
        if(x.compute(j) != y.compute(j))
          return false;
      return true;
    }
  
    friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y)
    { return !(x == y); }
  #else
    // Use a member function; Streamable concept not supported.
    bool operator==(const mersenne_twister& rhs) const
    {
      for(int j = 0; j < state_size; ++j)
        if(compute(j) != rhs.compute(j))
          return false;
      return true;
    }
  
    bool operator!=(const mersenne_twister& rhs) const
    { return !(*this == rhs); }
  #endif
  
  private:
    // returns x(i-n+index), where index is in 0..n-1
    UIntType compute(unsigned int index) const
    {
      // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers
      return x[ (i + n + index) % (2*n) ];
    }
    void twist(int block);
  
    // state representation: next output is o(x(i))
    //   x[0]  ... x[k] x[k+1] ... x[n-1]     x[n]     ... x[2*n-1]   represents
    //  x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)]
    // The goal is to always have x(i-n) ... x(i-1) available for
    // operator== and save/restore.
  
    UIntType x[2*n]; 
    int i;
  };
  
  #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
  //  A definition is required even for integral static constants
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c;
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l;
  #endif
  
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block)
  {
    const UIntType upper_mask = (~0u) << r;
    const UIntType lower_mask = ~upper_mask;
  
    if(block == 0) {
      for(int j = n; j < 2*n; j++) {
        UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask);
        x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
      }
    } else if (block == 1) {
      // split loop to avoid costly modulo operations
      {  // extra scope for MSVC brokenness w.r.t. for scope
        for(int j = 0; j < n-m; j++) {
          UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
          x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0);
        }
      }
      
      for(int j = n-m; j < n-1; j++) {
        UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask);
        x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0);
      }
      // last iteration
      UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask);
      x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0);
      i = 0;
    }
  }
  
  template<class UIntType, int w, int n, int m, int r, UIntType a, int u,
    int s, UIntType b, int t, UIntType c, int l, UIntType val>
  inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type
  mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()()
  {
    if(i == n)
      twist(0);
    else if(i >= 2*n)
      twist(1);
    // Step 4
    UIntType z = x[i];
    ++i;
    z ^= (z >> u);
    z ^= ((z << s) & b);
    z ^= ((z << t) & c);
    z ^= (z >> l);
    return z;
  }
  
  } // namespace random
  
  
  typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11,
    7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b;
  
  // validation by experiment from mt19937.c
  typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11,
    7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937;
  
  } // namespace boost
  
  BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937)
  
  #endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP
  