28 Numerics library [numerics]

28.5 Random number generation [rand]

28.5.4 Random number engine class templates [rand.eng] Class template subtract_with_carry_engine [rand.eng.sub]

A subtract_with_carry_engine random number engine produces unsigned integer random numbers.
The state x of a subtract_with_carry_engine object x is of size , and consists of a sequence X of r integer values ; all subscripts applied to X are to be taken modulo r.
The state x additionally consists of an integer c (known as the carry) whose value is either 0 or 1.
The state transition is performed as follows:
  • Let .
  • Set to .
    Set c to 1 if , otherwise set c to 0.
[Note 1: 
This algorithm corresponds to a modular linear function of the form , where b is of the form and .
— end note]
The generation algorithm is given by , where y is the value produced as a result of advancing the engine's state as described above.
namespace std { template<class UIntType, size_t w, size_t s, size_t r> class subtract_with_carry_engine { public: // types using result_type = UIntType; // engine characteristics static constexpr size_t word_size = w; static constexpr size_t short_lag = s; static constexpr size_t long_lag = r; static constexpr result_type min() { return 0; } static constexpr result_type max() { return ; } static constexpr uint_least32_t default_seed = 19780503u; // constructors and seeding functions subtract_with_carry_engine() : subtract_with_carry_engine(0u) {} explicit subtract_with_carry_engine(result_type value); template<class Sseq> explicit subtract_with_carry_engine(Sseq& q); void seed(result_type value = 0u); template<class Sseq> void seed(Sseq& q); // equality operators friend bool operator==(const subtract_with_carry_engine& x, const subtract_with_carry_engine& y); // generating functions result_type operator()(); void discard(unsigned long long z); // inserters and extractors template<class charT, class traits> friend basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& os, const subtract_with_carry_engine& x); template<class charT, class traits> friend basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, subtract_with_carry_engine& x); }; }
The following relations shall hold: 0u < s, s < r, 0 < w, and w <= numeric_limits<UIntType>​::​digits.
The textual representation consists of the values of , in that order, followed by c.
explicit subtract_with_carry_engine(result_type value);
Effects: Sets the values of , in that order, as specified below.
If is then 0, sets c to 1; otherwise sets c to 0.
To set the values , first construct e, a linear_congruential_engine object, as if by the following definition: linear_congruential_engine<uint_least32_t, 40014u,0u,2147483563u> e(value == 0u ? default_seed : value);
Then, to set each , obtain new values from successive invocations of e.
Set to .
Complexity: Exactly invocations of e.
template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
Effects: With and a an array (or equivalent) of length , invokes q.generate(, ) and then, iteratively for , sets to .
If is then 0, sets c to 1; otherwise sets c to 0.