24 Numerics library [numerics]

24.7 Random number generation [rand]

24.7.3 Random number engine class templates [rand.eng]

24.7.3.3 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

_{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.

The state x

_{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:

a)
Let $Y = X_{i - s} - X_{i - r} - c$ .
b)
Set $X_{i}$ to $y = Y mod m$ .

Set c to 1 if $Y < 0$ , otherwise set c to 0.

[ Note

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

— 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.

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 result_type default_seed = 19780503u;

    // constructors and seeding functions
    subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
    explicit subtract_with_carry_engine(result_type value);
    template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
    void seed(result_type value = default_seed);
    template<class Sseq> void seed(Sseq& q);

    // generating functions
    result_type operator()();
    void discard(unsigned long long z);
  };

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.

🔗

explicit subtract_with_carry_engine(result_type value);

Effects: Constructs a subtract_with_carry_engine object.

Sets the values of

X_{- r}, \dots, X_{- 1}

, in that order, as specified below.

X_{- 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<result_type,
                          40014u,0u,2147483563u> e(value == 0u ? default_seed : value);

Then, to set each

X_{k}

, obtain new values

z_{0}, \dots, z_{n - 1}

from

n = ⌈ w / 32 ⌉

successive invocations of e taken modulo

2^{32}

Set

X_{k}

(\sum_{j = 0}^{n - 1} z_{j} \cdot 2^{32 j}) mod m

Complexity: Exactly

n \cdot r

invocations of e.

🔗

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

Effects: Constructs a subtract_with_carry_engine object.

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}

(\sum_{j = 0}^{k - 1} a_{k (i + r) + j} \cdot 2^{32 j}) mod m

X_{- 1}

is then 0, sets c to 1; otherwise sets c to 0.

24 Numerics library [numerics]

24.7 Random number generation [rand]

24.7.3 Random number engine class templates [rand.eng]

24.7.3.3 Class template subtract_­with_­carry_­engine [rand.eng.sub]

24.7.3.3 Class template subtract_with_carry_engine [rand.eng.sub]