X-Git-Url: https://git.donarmstrong.com/?p=rsem.git;a=blobdiff_plain;f=boost%2Frandom%2Fsubtract_with_carry.hpp;h=fa82260244a74e579177d50ff71cac4c0db81fcd;hp=ca5c78ba6d07f5989bbe960952cd47d79b7467ac;hb=2d71eb92104693ca9baa5a2e1c23eeca776d8fd3;hpb=da57529b92adbb7ae74a89861cb39fb35ac7c62d diff --git a/boost/random/subtract_with_carry.hpp b/boost/random/subtract_with_carry.hpp index ca5c78b..fa82260 100644 --- 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. * - * $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 @@ -16,56 +16,88 @@ #ifndef BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP #define BOOST_RANDOM_SUBTRACT_WITH_CARRY_HPP -#include +#include // std::pow #include #include // std::equal #include -#include // std::pow #include #include #include #include +#include +#include #include #include #include +#include +#include +#include #include 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 - 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 + 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(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(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 * @@ -75,390 +107,506 @@ namespace detail * Volume 1, Number 3 (1991), 462-480. * @endblockquote */ -template -class subtract_with_carry +template +class subtract_with_carry_engine { 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::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::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 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 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 - 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 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 gen_t; + gen_t intgen(static_cast(value == 0 ? default_seed : value)); + detail::generator_seed_seq 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 - friend std::basic_ostream& - operator<<(std::basic_ostream& 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 - friend std::basic_istream& - operator>>(std::basic_istream& 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(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 + void seed(It& first, It last) + { + detail::fill_array_int(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::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 + 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: - /// \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 -template -const bool subtract_with_carry::has_fixed_range; -template -const IntType subtract_with_carry::min_value; -template -const IntType subtract_with_carry::max_value; -template -const IntType subtract_with_carry::modulus; -template -const unsigned int subtract_with_carry::long_lag; -template -const unsigned int subtract_with_carry::short_lag; +template +const bool subtract_with_carry_engine::has_fixed_range; +template +const IntType subtract_with_carry_engine::modulus; +template +const std::size_t subtract_with_carry_engine::word_size; +template +const std::size_t subtract_with_carry_engine::long_lag; +template +const std::size_t subtract_with_carry_engine::short_lag; +template +const uint32_t subtract_with_carry_engine::default_seed; #endif // use a floating-point representation to produce values in [0..1) -/** @copydoc boost::random::subtract_with_carry */ -template -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 subtract_with_carry_01_engine { 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::is_integer); -#endif - - subtract_with_carry_01() { init_modulus(); seed(); } - explicit subtract_with_carry_01(uint32_t value) - { init_modulus(); seed(value); } - template 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::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 subtract_with_carry_01_engine(It& first, It last) + { init_modulus(); seed(first,last); } private: - /// \cond hide_private_members - void init_modulus() - { + /// \cond show_private + void init_modulus() + { #ifndef BOOST_NO_STDC_NAMESPACE - // allow for Koenig lookup - using std::pow; + // allow for Koenig lookup + using std::pow; #endif - _modulus = pow(RealType(2), word_size); - } - /// \endcond hide_private_members + _modulus = pow(RealType(2), RealType(word_size)); + } + /// \endcond 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 gen_t; + gen_t intgen(value == 0 ? default_seed : value); + detail::generator_seed_seq 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 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 - 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(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 + void seed(It& first, It last) + { + detail::fill_array_real(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 - friend std::basic_ostream& - operator<<(std::basic_ostream& 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 - friend std::basic_istream& - operator>>(std::basic_istream& 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 + 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: - /// \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 -template -const bool subtract_with_carry_01::has_fixed_range; -template -const int subtract_with_carry_01::word_size; -template -const unsigned int subtract_with_carry_01::long_lag; -template -const unsigned int subtract_with_carry_01::short_lag; +template +const bool subtract_with_carry_01_engine::has_fixed_range; +template +const std::size_t subtract_with_carry_01_engine::word_size; +template +const std::size_t subtract_with_carry_01_engine::long_lag; +template +const std::size_t subtract_with_carry_01_engine::short_lag; +template +const uint32_t subtract_with_carry_01_engine::default_seed; #endif -/// \cond hide_private_members -template -RealType subtract_with_carry_01::compute(unsigned int index) const + +/// \cond show_deprecated + +template +class subtract_with_carry : + public subtract_with_carry_engine::value, s, r> { - return x[(k+index) % long_lag]; -} + typedef subtract_with_carry_engine::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 + 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 seq(gen); + base_type::seed(seq); + } + BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry, IntType, val) + { base_type::seed(val); } + template + void seed(It& first, It last) { base_type::seed(first, last); } +}; + +template +class subtract_with_carry_01 : + public subtract_with_carry_01_engine +{ + typedef subtract_with_carry_01_engine 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 + 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 seq(gen); + base_type::seed(seq); + } + BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(subtract_with_carry_01, uint32_t, val) + { base_type::seed(val); } + template + void seed(It& first, It last) { base_type::seed(first, last); } +}; + /// \endcond +namespace detail { + +template +struct generator_bits; + +template +struct generator_bits > { + static std::size_t value() { return w; } +}; + +template +struct generator_bits > { + static std::size_t value() { return w; } +}; + +} + } // namespace random } // namespace boost