cppdraft_translate/cppdraft/rand/eng/sub.md

[rand.eng.sub]

29 Numerics library [numerics]

29.5 Random number generation [rand]

29.5.4 Random number engine class templates [rand.eng]

29.5.4.4 Class template subtract_with_carry_engine [rand.eng.sub]

1

#

A subtract_with_carry_engine random number engine produces unsigned integer random numbers.

2

#

The state xi of a subtract_with_carry_engine object x is of sizeO(r), and consists of a sequence X of r integer values 0≤Xi<m=2w; all subscripts applied to X are to be taken modulo r.

The state xi additionally consists of an integer c (known as the carry) whose value is either 0 or 1.

3

#

The state transition is performed as follows:

• (3.1)

  Let Y=Xi−s−Xi−r−c.

• (3.2)

  Set Xi to y=Ymodm. Set c to 1 if Y<0, otherwise set c to 0.

[Note 1:

This algorithm corresponds to a modular linear function of the form TA(xi)=(aâ‹xi)modb, where b is of the form mr−ms+1 and a=b−(b−1)/m.

— end note]

4

#

The generation algorithm is given by GA(xi)=y, 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:// typesusing result_type = UIntType; // engine characteristicsstatic 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 m−1; }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 explicit subtract_with_carry_engine(Sseq& q); void seed(result_type value = 0u); template void seed(Sseq& q); // equality operatorsfriend 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 extractorstemplate<class charT, class traits>friend basic_ostream<charT, traits>&operator<<(basic_ostream<charT, traits>& os, // hostedconst subtract_with_carry_engine& x); template<class charT, class traits>friend basic_istream<charT, traits>&operator>>(basic_istream<charT, traits>& is, // hosted subtract_with_carry_engine& x); };}

5

#

The following relations shall hold: 0u < s, s < r, 0 < w, and w <= numeric_limits​::​digits.

6

#

The textual representation consists of the values of Xi−r,…,Xi−1, in that order, followed by c.

🔗

explicit subtract_with_carry_engine(result_type value);

7

#

Effects: Sets the values of X−r,…,X−1, in that order, as specified below.

If X−1 is then 0, sets c to 1; otherwise sets c to 0.

To set the values Xk, 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 : static_cast<uint_least32_t>(value % 2147483563u));

Then, to set each Xk, obtain new values z0,…,zn−1 from n=⌈w/32⌉ successive invocations of e.

Set Xk to (∑n−1j=0zjâ‹232j)modm.

8

#

Complexity: Exactly nâ‹r invocations of e.

🔗

template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);

9

#

Effects: With k=⌈w/32⌉ and a an array (or equivalent) of length râ‹k, invokes q.generate(a+0, a+râ‹k) and then, iteratively for i=−r,…,−1, sets Xi to (∑k−1j=0ak(i+r)+jâ‹232j)modm.

If X−1 is then 0, sets c to 1; otherwise sets c to 0.