Updated boost to v1.55.0

[rsem.git] / boost / random / subtract_with_carry.hpp

diff --git a/boost/random/subtract_with_carry.hpp b/boost/random/subtract_with_carry.hpp
index ca5c78ba6d07f5989bbe960952cd47d79b7467ac..fa82260244a74e579177d50ff71cac4c0db81fcd 100644 (file)
--- a/boost/random/subtract_with_carry.hpp
+++ b/boost/random/subtract_with_carry.hpp
@@ -7,7 +7,7 @@
  *
  * See http://www.boost.org for most recent version including documentation.
  *
  *
  * See http://www.boost.org for most recent version including documentation.
  *

- * $Id: subtract_with_carry.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
+ * $Id: subtract_with_carry.hpp 85813 2013-09-21 20:17:00Z jewillco $

  *
  * Revision history
  *  2002-03-02  created
  *
  * Revision history
  *  2002-03-02  created


@@ -16,56 +16,88 @@
 #ifndef BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP
 #define BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP
 
 #ifndef BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP
 #define BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP
 

-#include <boost/config/no_tr1/cmath.hpp>
+#include <boost/config/no_tr1/cmath.hpp>         // std::pow

 #include <iostream>
 #include <algorithm>     // std::equal
 #include <stdexcept>
 #include <iostream>
 #include <algorithm>     // std::equal
 #include <stdexcept>

-#include <boost/config/no_tr1/cmath.hpp>         // std::pow

 #include <boost/config.hpp>
 #include <boost/limits.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/config.hpp>
 #include <boost/limits.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/static_assert.hpp>

+#include <boost/integer/static_log2.hpp>
+#include <boost/integer/integer_mask.hpp>

 #include <boost/detail/workaround.hpp>
 #include <boost/random/detail/config.hpp>
 #include <boost/random/detail/seed.hpp>
 #include <boost/detail/workaround.hpp>
 #include <boost/random/detail/config.hpp>
 #include <boost/random/detail/seed.hpp>

+#include <boost/random/detail/operators.hpp>
+#include <boost/random/detail/seed_impl.hpp>
+#include <boost/random/detail/generator_seed_seq.hpp>

 #include <boost/random/linear_congruential.hpp>
 
 
 namespace boost {
 namespace random {
 
 #include <boost/random/linear_congruential.hpp>
 
 
 namespace boost {
 namespace random {
 

-#if BOOST_WORKAROUND(_MSC_FULL_VER, BOOST_TESTED_AT(13102292)) && BOOST_MSVC > 1300
-#  define BOOST_RANDOM_EXTRACT_SWC_01
-#endif
-
-#if defined(__APPLE_CC__) && defined(__GNUC__) && (__GNUC__ == 3) && (__GNUC_MINOR__ <= 3)
-#  define BOOST_RANDOM_EXTRACT_SWC_01
-#endif
-
-# ifdef BOOST_RANDOM_EXTRACT_SWC_01
-namespace detail
+namespace detail {
+   
+struct subtract_with_carry_discard

 {
 {

-  template <class IStream, class SubtractWithCarry, class RealType>
-  void extract_subtract_with_carry_01(
-      IStream& is
-      , SubtractWithCarry& f
-      , RealType& carry
-      , RealType* x
-      , RealType modulus)
-  {
-    RealType value;
-    for(unsigned int j = 0; j < f.long_lag; ++j) {
-      is >> value >> std::ws;
-      x[j] = value / modulus;
+    template<class Engine>
+    static void apply(Engine& eng, boost::uintmax_t z)
+    {
+        typedef typename Engine::result_type IntType;
+        const std::size_t short_lag = Engine::short_lag;
+        const std::size_t long_lag = Engine::long_lag;
+        std::size_t k = eng.k;
+        IntType carry = eng.carry;
+        if(k != 0) {
+            // increment k until it becomes 0.
+            if(k < short_lag) {
+                std::size_t limit = (short_lag - k) < z?
+                    short_lag : (k + static_cast<std::size_t>(z));
+                for(std::size_t j = k; j < limit; ++j) {
+                    carry = eng.do_update(j, j + long_lag - short_lag, carry);
+                }
+            }
+            std::size_t limit = (long_lag - k) < z?
+                long_lag : (k + static_cast<std::size_t>(z));
+            std::size_t start = (k < short_lag ? short_lag : k);
+            for(std::size_t j = start; j < limit; ++j) {
+                carry = eng.do_update(j, j - short_lag, carry);
+            }
+        }
+
+        k = ((z % long_lag) + k) % long_lag;
+
+        if(k < z) {
+            // main loop: update full blocks from k = 0 to long_lag
+            for(std::size_t i = 0; i < (z - k) / long_lag; ++i) {
+                for(std::size_t j = 0; j < short_lag; ++j) {
+                    carry = eng.do_update(j, j + long_lag - short_lag, carry);
+                }
+                for(std::size_t j = short_lag; j < long_lag; ++j) {
+                    carry = eng.do_update(j, j - short_lag, carry);
+                }
+            }
+
+            // Update the last partial block
+            std::size_t limit = short_lag < k? short_lag : k; 
+            for(std::size_t j = 0; j < limit; ++j) {
+                carry = eng.do_update(j, j + long_lag - short_lag, carry);
+            }
+            for(std::size_t j = short_lag; j < k; ++j) {
+                carry = eng.do_update(j, j - short_lag, carry);
+            }
+        }
+        eng.carry = carry;
+        eng.k = k;

     }
     }

-    is >> value >> std::ws;
-    carry = value / modulus;
-  }
+};
+

 }
 }

-# endif

 
 /**
 
 /**

- * Instantiations of @c subtract_with_carry model a
+ * Instantiations of @c subtract_with_carry_engine model a

  * \pseudo_random_number_generator.  The algorithm is
  * described in
  *
  * \pseudo_random_number_generator.  The algorithm is
  * described in
  *


@@ -75,390 +107,506 @@ namespace detail
  *  Volume 1, Number 3 (1991), 462-480.
  *  @endblockquote
  */
  *  Volume 1, Number 3 (1991), 462-480.
  *  @endblockquote
  */

-template<class IntType, IntType m, unsigned int s, unsigned int r,
-  IntType val>
-class subtract_with_carry
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+class subtract_with_carry_engine

 {
 public:
 {
 public:

-  typedef IntType result_type;
-  BOOST_STATIC_CONSTANT(bool, has_fixed_range = true);
-  BOOST_STATIC_CONSTANT(result_type, min_value = 0);
-  BOOST_STATIC_CONSTANT(result_type, max_value = m-1);
-  BOOST_STATIC_CONSTANT(result_type, modulus = m);
-  BOOST_STATIC_CONSTANT(unsigned int, long_lag = r);
-  BOOST_STATIC_CONSTANT(unsigned int, short_lag = s);
-
-  subtract_with_carry() {
-    // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope
-#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
-    BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_signed);
+    typedef IntType result_type;
+    BOOST_STATIC_CONSTANT(std::size_t, word_size = w);
+    BOOST_STATIC_CONSTANT(std::size_t, long_lag = r);
+    BOOST_STATIC_CONSTANT(std::size_t, short_lag = s);
+    BOOST_STATIC_CONSTANT(uint32_t, default_seed = 19780503u);
+
+    // Required by the old Boost.Random concepts
+    BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+    // Backwards compatibility
+    BOOST_STATIC_CONSTANT(result_type, modulus = (result_type(1) << w));
+    

     BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_integer);
     BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_integer);

-#endif
-    seed();
-  }
-  BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry, uint32_t, value)
-  { seed(value); }
-  BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(subtract_with_carry, Generator, gen)
-  { seed(gen); }
-  template<class It> subtract_with_carry(It& first, It last) { seed(first,last); }
-
-  // compiler-generated copy ctor and assignment operator are fine
-
-  void seed() { seed(19780503u); }
-  BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry, uint32_t, value)
-  {
-    random::linear_congruential<int32_t, 40014, 0, 2147483563, 0> intgen(value);
-    seed(intgen);
-  }
-
-  // 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 template member functions.
-  BOOST_RANDOM_DETAIL_GENERATOR_SEED(subtract_with_carry, Generator, gen)
-  {
-    // I could have used std::generate_n, but it takes "gen" by value
-    for(unsigned int j = 0; j < long_lag; ++j)
-      x[j] = gen() % modulus;
-    carry = (x[long_lag-1] == 0);
-    k = 0;
-  }
-
-  template<class It>
-  void seed(It& first, It last)
-  {
-    unsigned int j;
-    for(j = 0; j < long_lag && first != last; ++j, ++first)
-      x[j] = *first % modulus;
-    if(first == last && j < long_lag)
-      throw std::invalid_argument("subtract_with_carry::seed");
-    carry = (x[long_lag-1] == 0);
-    k = 0;
-   }
-
-  result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_value; }
-  result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_value; }
-
-  result_type operator()()
-  {
-    int short_index = k - short_lag;
-    if(short_index < 0)
-      short_index += long_lag;
-    IntType delta;
-    if (x[short_index] >= x[k] + carry) {
-      // x(n) >= 0
-      delta =  x[short_index] - (x[k] + carry);
-      carry = 0;
-    } else {
-      // x(n) < 0
-      delta = modulus - x[k] - carry + x[short_index];
-      carry = 1;
+
+    /**
+     * Constructs a new @c subtract_with_carry_engine and seeds
+     * it with the default seed.
+     */
+    subtract_with_carry_engine() { seed(); }
+    /**
+     * Constructs a new @c subtract_with_carry_engine and seeds
+     * it with @c value.
+     */
+    BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry_engine,
+                                               IntType, value)
+    { seed(value); }
+    /**
+     * Constructs a new @c subtract_with_carry_engine and seeds
+     * it with values produced by @c seq.generate().
+     */
+    BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(subtract_with_carry_engine,
+                                             SeedSeq, seq)
+    { seed(seq); }
+    /**
+     * Constructs a new @c subtract_with_carry_engine and seeds
+     * it with values from a range.  first is updated to point
+     * one past the last value consumed.  If there are not
+     * enough elements in the range to fill the entire state of
+     * the generator, throws @c std::invalid_argument.
+     */
+    template<class It> subtract_with_carry_engine(It& first, It last)
+    { seed(first,last); }
+
+    // compiler-generated copy ctor and assignment operator are fine
+
+    /** Seeds the generator with the default seed. */
+    void seed() { seed(default_seed); }
+    BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry_engine,
+                                        IntType, value)
+    {
+        typedef linear_congruential_engine<uint32_t,40014,0,2147483563> gen_t;
+        gen_t intgen(static_cast<boost::uint32_t>(value == 0 ? default_seed : value));
+        detail::generator_seed_seq<gen_t> gen(intgen);
+        seed(gen);

     }
     }

-    x[k] = delta;
-    ++k;
-    if(k >= long_lag)
-      k = 0;
-    return delta;
-  }

 
 

-public:
-  static bool validation(result_type x) { return x == val; }
-  
-#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
-
-#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
-  template<class CharT, class Traits>
-  friend std::basic_ostream<CharT,Traits>&
-  operator<<(std::basic_ostream<CharT,Traits>& os,
-             const subtract_with_carry& f)
-  {
-    for(unsigned int j = 0; j < f.long_lag; ++j)
-      os << f.compute(j) << " ";
-    os << f.carry << " ";
-    return os;
-  }
-
-  template<class CharT, class Traits>
-  friend std::basic_istream<CharT,Traits>&
-  operator>>(std::basic_istream<CharT,Traits>& is, subtract_with_carry& f)
-  {
-    for(unsigned int j = 0; j < f.long_lag; ++j)
-      is >> f.x[j] >> std::ws;
-    is >> f.carry >> std::ws;
-    f.k = 0;
-    return is;
-  }
-#endif
+    /** Seeds the generator with values produced by @c seq.generate(). */
+    BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(subtract_with_carry, SeedSeq, seq)
+    {
+        detail::seed_array_int<w>(seq, x);
+        carry = (x[long_lag-1] == 0);
+        k = 0;
+    }

 
 

-  friend bool operator==(const subtract_with_carry& x, const subtract_with_carry& y)
-  {
-    for(unsigned int j = 0; j < r; ++j)
-      if(x.compute(j) != y.compute(j))
-        return false;
-    return true;
-  }
-
-  friend bool operator!=(const subtract_with_carry& x, const subtract_with_carry& y)
-  { return !(x == y); }
-#else
-  // Use a member function; Streamable concept not supported.
-  bool operator==(const subtract_with_carry& rhs) const
-  {
-    for(unsigned int j = 0; j < r; ++j)
-      if(compute(j) != rhs.compute(j))
-        return false;
-    return true;
-  }
-
-  bool operator!=(const subtract_with_carry& rhs) const
-  { return !(*this == rhs); }
-#endif
+    /**
+     * Seeds the generator with values from a range.  Updates @c first to
+     * point one past the last consumed value.  If the range does not
+     * contain enough elements to fill the entire state of the generator,
+     * throws @c std::invalid_argument.
+     */
+    template<class It>
+    void seed(It& first, It last)
+    {
+        detail::fill_array_int<w>(first, last, x);
+        carry = (x[long_lag-1] == 0);
+        k = 0;
+    }
+
+    /** Returns the smallest value that the generator can produce. */
+    static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return 0; }
+    /** Returns the largest value that the generator can produce. */
+    static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return boost::low_bits_mask_t<w>::sig_bits; }
+
+    /** Returns the next value of the generator. */
+    result_type operator()()
+    {
+        std::size_t short_index =
+            (k < short_lag)?
+                (k + long_lag - short_lag) :
+                (k - short_lag);
+        carry = do_update(k, short_index, carry);
+        IntType result = x[k];
+        ++k;
+        if(k >= long_lag)
+            k = 0;
+        return result;
+    }
+
+    /** Advances the state of the generator by @c z. */
+    void discard(boost::uintmax_t z)
+    {
+        detail::subtract_with_carry_discard::apply(*this, z);
+    }
+
+    /** Fills a range with random values. */
+    template<class It>
+    void generate(It first, It last)
+    { detail::generate_from_int(*this, first, last); }
+ 
+    /** Writes a @c subtract_with_carry_engine to a @c std::ostream. */
+    BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, subtract_with_carry_engine, f)
+    {
+        for(unsigned int j = 0; j < f.long_lag; ++j)
+            os << f.compute(j) << ' ';
+        os << f.carry;
+        return os;
+    }
+
+    /** Reads a @c subtract_with_carry_engine from a @c std::istream. */
+    BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, subtract_with_carry_engine, f)
+    {
+        for(unsigned int j = 0; j < f.long_lag; ++j)
+            is >> f.x[j] >> std::ws;
+        is >> f.carry;
+        f.k = 0;
+        return is;
+    }
+
+    /**
+     * Returns true if the two generators will produce identical
+     * sequences of values.
+     */
+    BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(subtract_with_carry_engine, x, y)
+    {
+        for(unsigned int j = 0; j < r; ++j)
+            if(x.compute(j) != y.compute(j))
+                return false;
+        return true;
+    }
+
+    /**
+     * Returns true if the two generators will produce different
+     * sequences of values.
+     */
+    BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(subtract_with_carry_engine)

 
 private:
 
 private:

-  /// \cond hide_private_members
-  // returns x(i-r+index), where index is in 0..r-1
-  IntType compute(unsigned int index) const
-  {
-    return x[(k+index) % long_lag];
-  }
-  /// \endcond
-
-  // state representation; next output (state) is x(i)
-  //   x[0]  ... x[k] x[k+1] ... x[long_lag-1]     represents
-  //  x(i-k) ... x(i) x(i+1) ... x(i-k+long_lag-1)
-  // speed: base: 20-25 nsec
-  // ranlux_4: 230 nsec, ranlux_7: 430 nsec, ranlux_14: 810 nsec
-  // This state representation makes operator== and save/restore more
-  // difficult, because we've already computed "too much" and thus
-  // have to undo some steps to get at x(i-r) etc.
-
-  // state representation: next output (state) is x(i)
-  //   x[0]  ... x[k] x[k+1]          ... x[long_lag-1]     represents
-  //  x(i-k) ... x(i) x(i-long_lag+1) ... x(i-k-1)
-  // speed: base 28 nsec
-  // ranlux_4: 370 nsec, ranlux_7: 688 nsec, ranlux_14: 1343 nsec
-  IntType x[long_lag];
-  unsigned int k;
-  int carry;
+    /// \cond show_private
+    // returns x(i-r+index), where index is in 0..r-1
+    IntType compute(unsigned int index) const
+    {
+        return x[(k+index) % long_lag];
+    }
+
+    friend struct detail::subtract_with_carry_discard;
+
+    IntType do_update(std::size_t current, std::size_t short_index, IntType carry)
+    {
+        IntType delta;
+        IntType temp = x[current] + carry;
+        if (x[short_index] >= temp) {
+            // x(n) >= 0
+            delta =  x[short_index] - temp;
+            carry = 0;
+        } else {
+            // x(n) < 0
+            delta = modulus - temp + x[short_index];
+            carry = 1;
+        }
+        x[current] = delta;
+        return carry;
+    }
+    /// \endcond
+
+    // state representation; next output (state) is x(i)
+    //   x[0]  ... x[k] x[k+1] ... x[long_lag-1]     represents
+    //  x(i-k) ... x(i) x(i+1) ... x(i-k+long_lag-1)
+    // speed: base: 20-25 nsec
+    // ranlux_4: 230 nsec, ranlux_7: 430 nsec, ranlux_14: 810 nsec
+    // This state representation makes operator== and save/restore more
+    // difficult, because we've already computed "too much" and thus
+    // have to undo some steps to get at x(i-r) etc.
+
+    // state representation: next output (state) is x(i)
+    //   x[0]  ... x[k] x[k+1]          ... x[long_lag-1]     represents
+    //  x(i-k) ... x(i) x(i-long_lag+1) ... x(i-k-1)
+    // speed: base 28 nsec
+    // ranlux_4: 370 nsec, ranlux_7: 688 nsec, ranlux_14: 1343 nsec
+    IntType x[long_lag];
+    std::size_t k;
+    IntType carry;

 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 //  A definition is required even for integral static constants
 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 //  A definition is required even for integral static constants

-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const bool subtract_with_carry<IntType, m, s, r, val>::has_fixed_range;
-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const IntType subtract_with_carry<IntType, m, s, r, val>::min_value;
-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const IntType subtract_with_carry<IntType, m, s, r, val>::max_value;
-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const IntType subtract_with_carry<IntType, m, s, r, val>::modulus;
-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const unsigned int subtract_with_carry<IntType, m, s, r, val>::long_lag;
-template<class IntType, IntType m, unsigned int s, unsigned int r, IntType val>
-const unsigned int subtract_with_carry<IntType, m, s, r, val>::short_lag;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const bool subtract_with_carry_engine<IntType, w, s, r>::has_fixed_range;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const IntType subtract_with_carry_engine<IntType, w, s, r>::modulus;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_engine<IntType, w, s, r>::word_size;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_engine<IntType, w, s, r>::long_lag;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_engine<IntType, w, s, r>::short_lag;
+template<class IntType, std::size_t w, std::size_t s, std::size_t r>
+const uint32_t subtract_with_carry_engine<IntType, w, s, r>::default_seed;

 #endif
 
 
 // use a floating-point representation to produce values in [0..1)
 #endif
 
 
 // use a floating-point representation to produce values in [0..1)

-/** @copydoc boost::random::subtract_with_carry */
-template<class RealType, int w, unsigned int s, unsigned int r, int val=0>
-class subtract_with_carry_01
+/**
+ * Instantiations of \subtract_with_carry_01_engine model a
+ * \pseudo_random_number_generator.  The algorithm is
+ * described in
+ *
+ *  @blockquote
+ *  "A New Class of Random Number Generators", George
+ *  Marsaglia and Arif Zaman, Annals of Applied Probability,
+ *  Volume 1, Number 3 (1991), 462-480.
+ *  @endblockquote
+ */
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+class subtract_with_carry_01_engine

 {
 public:
 {
 public:

-  typedef RealType result_type;
-  BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
-  BOOST_STATIC_CONSTANT(int, word_size = w);
-  BOOST_STATIC_CONSTANT(unsigned int, long_lag = r);
-  BOOST_STATIC_CONSTANT(unsigned int, short_lag = s);
-
-#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
-  BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_integer);
-#endif
-
-  subtract_with_carry_01() { init_modulus(); seed(); }
-  explicit subtract_with_carry_01(uint32_t value)
-  { init_modulus(); seed(value);   }
-  template<class It> subtract_with_carry_01(It& first, It last)
-  { init_modulus(); seed(first,last); }
+    typedef RealType result_type;
+    BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
+    BOOST_STATIC_CONSTANT(std::size_t, word_size = w);
+    BOOST_STATIC_CONSTANT(std::size_t, long_lag = r);
+    BOOST_STATIC_CONSTANT(std::size_t, short_lag = s);
+    BOOST_STATIC_CONSTANT(boost::uint32_t, default_seed = 19780503u);
+
+    BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_integer);
+
+    /** Creates a new \subtract_with_carry_01_engine using the default seed. */
+    subtract_with_carry_01_engine() { init_modulus(); seed(); }
+    /** Creates a new subtract_with_carry_01_engine and seeds it with value. */
+    BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry_01_engine,
+                                               boost::uint32_t, value)
+    { init_modulus(); seed(value); }
+    /**
+     * Creates a new \subtract_with_carry_01_engine and seeds with values
+     * produced by seq.generate().
+     */
+    BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(subtract_with_carry_01_engine,
+                                             SeedSeq, seq)
+    { init_modulus(); seed(seq); }
+    /**
+     * Creates a new \subtract_with_carry_01_engine and seeds it with values
+     * from a range.  Advances first to point one past the last consumed
+     * value.  If the range does not contain enough elements to fill the
+     * entire state, throws @c std::invalid_argument.
+     */
+    template<class It> subtract_with_carry_01_engine(It& first, It last)
+    { init_modulus(); seed(first,last); }

 
 private:
 
 private:

-  /// \cond hide_private_members
-  void init_modulus()
-  {
+    /// \cond show_private
+    void init_modulus()
+    {

 #ifndef BOOST_NO_STDC_NAMESPACE
 #ifndef BOOST_NO_STDC_NAMESPACE

-    // allow for Koenig lookup
-    using std::pow;
+        // allow for Koenig lookup
+        using std::pow;

 #endif
 #endif

-    _modulus = pow(RealType(2), word_size);
-  }
-  /// \endcond hide_private_members
+        _modulus = pow(RealType(2), RealType(word_size));
+    }
+    /// \endcond

 
 public:
 
 public:

-  // compiler-generated copy ctor and assignment operator are fine
+    // compiler-generated copy ctor and assignment operator are fine
+
+    /** Seeds the generator with the default seed. */
+    void seed() { seed(default_seed); }
+
+    /** Seeds the generator with @c value. */
+    BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry_01_engine,
+                                        boost::uint32_t, value)
+    {
+        typedef linear_congruential_engine<uint32_t, 40014, 0, 2147483563> gen_t;
+        gen_t intgen(value == 0 ? default_seed : value);
+        detail::generator_seed_seq<gen_t> gen(intgen);
+        seed(gen);
+    }

 
 

-  void seed(uint32_t value = 19780503u)
-  {
-#ifndef BOOST_NO_STDC_NAMESPACE
-    // allow for Koenig lookup
-    using std::fmod;
-#endif
-    random::linear_congruential<int32_t, 40014, 0, 2147483563, 0> gen(value);
-    unsigned long array[(w+31)/32 * long_lag];
-    for(unsigned int j = 0; j < sizeof(array)/sizeof(unsigned long); ++j)
-      array[j] = gen();
-    unsigned long * start = array;
-    seed(start, array + sizeof(array)/sizeof(unsigned long));
-  }
-
-  template<class It>
-  void seed(It& first, It last)
-  {
-#ifndef BOOST_NO_STDC_NAMESPACE
-    // allow for Koenig lookup
-    using std::fmod;
-    using std::pow;
-#endif
-    unsigned long mask = ~((~0u) << (w%32));   // now lowest (w%32) bits set
-    RealType two32 = pow(RealType(2), 32);
-    unsigned int j;
-    for(j = 0; j < long_lag && first != last; ++j) {
-      x[j] = RealType(0);
-      for(int i = 0; i < w/32 && first != last; ++i, ++first)
-        x[j] += *first / pow(two32,i+1);
-      if(first != last && mask != 0) {
-        x[j] += fmod((*first & mask) / _modulus, RealType(1));
-        ++first;
-      }
+    /** Seeds the generator with values produced by @c seq.generate(). */
+    BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(subtract_with_carry_01_engine,
+                                      SeedSeq, seq)
+    {
+        detail::seed_array_real<w>(seq, x);
+        carry = (x[long_lag-1] ? 0 : 1 / _modulus);
+        k = 0;

     }
     }

-    if(first == last && j < long_lag)
-      throw std::invalid_argument("subtract_with_carry_01::seed");
-    carry = (x[long_lag-1] ? 0 : 1 / _modulus);
-    k = 0;
-  }
-
-  result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(0); }
-  result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(1); }
-
-  result_type operator()()
-  {
-    int short_index = k - short_lag;
-    if(short_index < 0)
-      short_index += long_lag;
-    RealType delta = x[short_index] - x[k] - carry;
-    if(delta < 0) {
-      delta += RealType(1);
-      carry = RealType(1)/_modulus;
-    } else {
-      carry = 0;
+
+    /**
+     * Seeds the generator with values from a range.  Updates first to
+     * point one past the last consumed element.  If there are not
+     * enough elements in the range to fill the entire state, throws
+     * @c std::invalid_argument.
+     */
+    template<class It>
+    void seed(It& first, It last)
+    {
+        detail::fill_array_real<w>(first, last, x);
+        carry = (x[long_lag-1] ? 0 : 1 / _modulus);
+        k = 0;

     }
     }

-    x[k] = delta;
-    ++k;
-    if(k >= long_lag)
-      k = 0;
-    return delta;
-  }
-
-  static bool validation(result_type x)
-  { return x == val/pow(RealType(2), word_size); }
-  
-#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
-
-#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
-  template<class CharT, class Traits>
-  friend std::basic_ostream<CharT,Traits>&
-  operator<<(std::basic_ostream<CharT,Traits>& os,
-             const subtract_with_carry_01& f)
-  {
-#ifndef BOOST_NO_STDC_NAMESPACE
-    // allow for Koenig lookup
-    using std::pow;
-#endif
-    std::ios_base::fmtflags oldflags = os.flags(os.dec | os.fixed | os.left); 
-    for(unsigned int j = 0; j < f.long_lag; ++j)
-      os << (f.compute(j) * f._modulus) << " ";
-    os << (f.carry * f._modulus);
-    os.flags(oldflags);
-    return os;
-  }
-
-  template<class CharT, class Traits>
-  friend std::basic_istream<CharT,Traits>&
-  operator>>(std::basic_istream<CharT,Traits>& is, subtract_with_carry_01& f)
-  {
-# ifdef BOOST_RANDOM_EXTRACT_SWC_01
-      detail::extract_subtract_with_carry_01(is, f, f.carry, f.x, f._modulus);
-# else
-    // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template type
-    // parameter "RealType" available from the class template scope, so use
-    // the member typedef
-    typename subtract_with_carry_01::result_type value;
-    for(unsigned int j = 0; j < long_lag; ++j) {
-      is >> value >> std::ws;
-      f.x[j] = value / f._modulus;
+
+    /** Returns the smallest value that the generator can produce. */
+    static result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return result_type(0); }
+    /** Returns the largest value that the generator can produce. */
+    static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
+    { return result_type(1); }
+
+    /** Returns the next value of the generator. */
+    result_type operator()()
+    {
+        std::size_t short_index =
+            (k < short_lag) ?
+                (k + long_lag - short_lag) :
+                (k - short_lag);
+        carry = do_update(k, short_index, carry);
+        RealType result = x[k];
+        ++k;
+        if(k >= long_lag)
+            k = 0;
+        return result;

     }
     }

-    is >> value >> std::ws;
-    f.carry = value / f._modulus;
-# endif 
-    f.k = 0;
-    return is;
-  }
-#endif

 
 

-  friend bool operator==(const subtract_with_carry_01& x,
-                         const subtract_with_carry_01& y)
-  {
-    for(unsigned int j = 0; j < r; ++j)
-      if(x.compute(j) != y.compute(j))
-        return false;
-    return true;
-  }
-
-  friend bool operator!=(const subtract_with_carry_01& x,
-                         const subtract_with_carry_01& y)
-  { return !(x == y); }
-#else
-  // Use a member function; Streamable concept not supported.
-  bool operator==(const subtract_with_carry_01& rhs) const
-  { 
-    for(unsigned int j = 0; j < r; ++j)
-      if(compute(j) != rhs.compute(j))
-        return false;
-    return true;
-  }
-
-  bool operator!=(const subtract_with_carry_01& rhs) const
-  { return !(*this == rhs); }
-#endif
+    /** Advances the state of the generator by @c z. */
+    void discard(boost::uintmax_t z)
+    { detail::subtract_with_carry_discard::apply(*this, z); }
+
+    /** Fills a range with random values. */
+    template<class Iter>
+    void generate(Iter first, Iter last)
+    { detail::generate_from_real(*this, first, last); }
+
+    /** Writes a \subtract_with_carry_01_engine to a @c std::ostream. */
+    BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, subtract_with_carry_01_engine, f)
+    {
+        std::ios_base::fmtflags oldflags =
+            os.flags(os.dec | os.fixed | os.left); 
+        for(unsigned int j = 0; j < f.long_lag; ++j)
+            os << (f.compute(j) * f._modulus) << ' ';
+        os << (f.carry * f._modulus);
+        os.flags(oldflags);
+        return os;
+    }
+    
+    /** Reads a \subtract_with_carry_01_engine from a @c std::istream. */
+    BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, subtract_with_carry_01_engine, f)
+    {
+        RealType value;
+        for(unsigned int j = 0; j < long_lag; ++j) {
+            is >> value >> std::ws;
+            f.x[j] = value / f._modulus;
+        }
+        is >> value;
+        f.carry = value / f._modulus;
+        f.k = 0;
+        return is;
+    }
+
+    /** Returns true if the two generators will produce identical sequences. */
+    BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(subtract_with_carry_01_engine, x, y)
+    {
+        for(unsigned int j = 0; j < r; ++j)
+            if(x.compute(j) != y.compute(j))
+                return false;
+        return true;
+    }
+
+    /** Returns true if the two generators will produce different sequences. */
+    BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(subtract_with_carry_01_engine)

 
 private:
 
 private:

-  /// \cond hide_private_members
-  RealType compute(unsigned int index) const;
-  /// \endcond
-  unsigned int k;
-  RealType carry;
-  RealType x[long_lag];
-  RealType _modulus;
+    /// \cond show_private
+    RealType compute(unsigned int index) const
+    {
+        return x[(k+index) % long_lag];
+    }
+
+    friend struct detail::subtract_with_carry_discard;
+
+    RealType do_update(std::size_t current, std::size_t short_index, RealType carry)
+    {
+        RealType delta = x[short_index] - x[current] - carry;
+        if(delta < 0) {
+            delta += RealType(1);
+            carry = RealType(1)/_modulus;
+        } else {
+            carry = 0;
+        }
+        x[current] = delta;
+        return carry;
+    }
+    /// \endcond
+    std::size_t k;
+    RealType carry;
+    RealType x[long_lag];
+    RealType _modulus;

 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 //  A definition is required even for integral static constants
 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 //  A definition is required even for integral static constants

-template<class RealType, int w, unsigned int s, unsigned int r, int val>
-const bool subtract_with_carry_01<RealType, w, s, r, val>::has_fixed_range;
-template<class RealType, int w, unsigned int s, unsigned int r, int val>
-const int subtract_with_carry_01<RealType, w, s, r, val>::word_size;
-template<class RealType, int w, unsigned int s, unsigned int r, int val>
-const unsigned int subtract_with_carry_01<RealType, w, s, r, val>::long_lag;
-template<class RealType, int w, unsigned int s, unsigned int r, int val>
-const unsigned int subtract_with_carry_01<RealType, w, s, r, val>::short_lag;
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+const bool subtract_with_carry_01_engine<RealType, w, s, r>::has_fixed_range;
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_01_engine<RealType, w, s, r>::word_size;
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_01_engine<RealType, w, s, r>::long_lag;
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+const std::size_t subtract_with_carry_01_engine<RealType, w, s, r>::short_lag;
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+const uint32_t subtract_with_carry_01_engine<RealType, w, s, r>::default_seed;

 #endif
 
 #endif
 

-/// \cond hide_private_members
-template<class RealType, int w, unsigned int s, unsigned int r, int val>
-RealType subtract_with_carry_01<RealType, w, s, r, val>::compute(unsigned int index) const
+
+/// \cond show_deprecated
+
+template<class IntType, IntType m, unsigned s, unsigned r, IntType v>
+class subtract_with_carry :
+    public subtract_with_carry_engine<IntType,
+        boost::static_log2<m>::value, s, r>

 {
 {

-  return x[(k+index) % long_lag];
-}
+    typedef subtract_with_carry_engine<IntType,
+        boost::static_log2<m>::value, s, r> base_type;
+public:
+    subtract_with_carry() {}
+    BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(subtract_with_carry, Gen, gen)
+    { seed(gen); }
+    BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry,
+                                               IntType, val)
+    { seed(val); }
+    template<class It>
+    subtract_with_carry(It& first, It last) : base_type(first, last) {}
+    void seed() { base_type::seed(); }
+    BOOST_RANDOM_DETAIL_GENERATOR_SEED(subtract_with_carry, Gen, gen)
+    {
+        detail::generator_seed_seq<Gen> seq(gen);
+        base_type::seed(seq);
+    }
+    BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry, IntType, val)
+    { base_type::seed(val); }
+    template<class It>
+    void seed(It& first, It last) { base_type::seed(first, last); }
+};
+
+template<class RealType, int w, unsigned s, unsigned r, int v = 0>
+class subtract_with_carry_01 :
+    public subtract_with_carry_01_engine<RealType, w, s, r>
+{
+    typedef subtract_with_carry_01_engine<RealType, w, s, r> base_type;
+public:
+    subtract_with_carry_01() {}
+    BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(subtract_with_carry_01, Gen, gen)
+    { seed(gen); }
+    BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(subtract_with_carry_01,
+                                               uint32_t, val)
+    { seed(val); }
+    template<class It>
+    subtract_with_carry_01(It& first, It last) : base_type(first, last) {}
+    void seed() { base_type::seed(); }
+    BOOST_RANDOM_DETAIL_GENERATOR_SEED(subtract_with_carry_01, Gen, gen)
+    {
+        detail::generator_seed_seq<Gen> seq(gen);
+        base_type::seed(seq);
+    }
+    BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry_01, uint32_t, val)
+    { base_type::seed(val); }
+    template<class It>
+    void seed(It& first, It last) { base_type::seed(first, last); }
+};
+

 /// \endcond
 
 /// \endcond
 

+namespace detail {
+
+template<class Engine>
+struct generator_bits;
+
+template<class RealType, std::size_t w, std::size_t s, std::size_t r>
+struct generator_bits<subtract_with_carry_01_engine<RealType, w, s, r> > {
+    static std::size_t value() { return w; }
+};
+
+template<class RealType, int w, unsigned s, unsigned r, int v>
+struct generator_bits<subtract_with_carry_01<RealType, w, s, r, v> > {
+    static std::size_t value() { return w; }
+};
+
+}
+

 } // namespace random
 } // namespace boost
 
 } // namespace random
 } // namespace boost