[rand.eng.sub]

The state x

{i of a subtract_with_carry_engine object x is of size O (r), and consists of a sequence X of r integer values 0 \leq {X i < m = {2 w; all subscripts applied to X are to be taken modulo r .}^{w; all subscripts applied to X are to be taken modulo r .}}_{i < m = {2 w; all subscripts applied to X are to be taken modulo r .}^{w; all subscripts applied to X are to be taken modulo r .}}}_{i of a subtract_with_carry_engine object x is of size O (r), and consists of a sequence X of r integer values 0 \leq {X i < m = {2 w; all subscripts applied to X are to be taken modulo r .}^{w; all subscripts applied to X are to be taken modulo r .}}_{i < m = {2 w; all subscripts applied to X are to be taken modulo r .}^{w; all subscripts applied to X are to be taken modulo r .}}}

The state x

{i additionally consists of an integer c (known as the carry) whose value is either 0 or 1 .}_{i additionally consists of an integer c (known as the carry) whose value is either 0 or 1 .}

The state transition is performed as follows:

(3.1)
Let $Y = {X i - s - {X i - r - c .}_{i - r - c .}}_{i - s - {X i - r - c .}_{i - r - c .}}$
(3.2)
Set ${X i to y = Y mod m .}_{i to y = Y mod m .}$

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

T A (x {i) = (a \cdot x {i) mod b, where b is of the form {m r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}^{r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}}_{i) mod b, where b is of the form {m r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}^{r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}}}_{i) = (a \cdot x {i) mod b, where b is of the form {m r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}^{r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}}_{i) mod b, where b is of the form {m r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}^{r - {m s + 1 and a = b - (b - 1) / m .}^{s + 1 and a = b - (b - 1) / m .}}}}

— end note]

The generation algorithm is given by

G A (x {i) = y, where y is the value produced as a result of advancing the engine's state as described above .}_{i) = 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: / 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

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<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 z); / inserters and extractors template<class charT, class traits> friend basic_ostream<charT, traits>& operator<(basic_ostream<charT, traits>& os, / hosted const 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); }; }

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

{X i - r, \dots, {X i - 1, in that order, followed by c .}_{i - 1, in that order, followed by c .}}_{i - r, \dots, {X i - 1, in that order, followed by c .}_{i - 1, in that order, followed by c .}}

🔗

explicit subtract_with_carry_engine(result_type value);

Effects: Sets the values of

{X - r, \dots, {X - 1, in that order, as specified below .}_{- 1, in that order, as specified below .}}_{- r, \dots, {X - 1, in that order, as specified below .}_{- 1, in that order, as specified below .}}

{X - 1 is then 0, sets c to 1; otherwise sets c to 0 .}_{- 1 is then 0, sets c to 1; otherwise sets c to 0 .}

To set the values

{X k, 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);}_{k, 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

{X k, obtain new values {z 0, \dots, {z n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}_{n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}}_{0, \dots, {z n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}_{n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}}}_{k, obtain new values {z 0, \dots, {z n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}_{n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}}_{0, \dots, {z n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}_{n - 1 from n = ⌈ w / 32 ⌉ successive invocations of e .}}}

Set

{X k to ({\sum n - 1 j = 0 {z j \cdot {2 32 j) mod m .}^{32 j) mod m .}}_{j \cdot {2 32 j) mod m .}^{32 j) mod m .}}}^{n - 1 j = 0 {z j \cdot {2 32 j) mod m .}^{32 j) mod m .}}_{j \cdot {2 32 j) mod m .}^{32 j) mod m .}}}}_{k to ({\sum n - 1 j = 0 {z j \cdot {2 32 j) mod m .}^{32 j) mod m .}}_{j \cdot {2 32 j) mod m .}^{32 j) mod m .}}}^{n - 1 j = 0 {z j \cdot {2 32 j) mod m .}^{32 j) mod m .}}_{j \cdot {2 32 j) mod m .}^{32 j) mod m .}}}}

Complexity: Exactly

n \cdot r invocations of e .

🔗

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

Effects: With

k = ⌈ w / 32 ⌉ and a an array (or equivalent) of length r \cdot k, invokes q . generate (a + 0, a + r \cdot k) and then, iteratively for i = - r, \dots, - 1, sets {X i to ({\sum k - 1 j = 0 {a k (i + r) + j \cdot}_{k (i + r) + j \cdot 2}}^{k - 1 j = 0 {a k (i + r) + j \cdot 2^{.}}_{k (i + r) + j \cdot {2 .}^{32 j) mod m .}}}}_{i to ({\sum k - 1 j = 0 {a k (i + r) + j \cdot 2}_{k (i + r) + j \cdot 2^{.}}}^{k - 1 j = 0 {a k (i + r) + j \cdot {2 .}^{32 j) mod m .}}_{k (i + r) + j \cdot {2 32 j) mod m .}^{32 j) mod m .}}}}

{X - 1 is then 0, sets c to 1; otherwise sets c to 0 .}_{- 1 is then 0, sets c to 1; otherwise sets c to 0 .}