29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 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 xi of a subtract_­with_­carry_­engine object x is of size O(r), and consists of a sequence X of r integer values 0Xi<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.

The state transition is performed as follows:

  1. a)Let Y=XisXirc.

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

[Note: This algorithm corresponds to a modular linear function of the form TA(xi)=(axi)modb, where b is of the form mrms+1 and a=b(b1)/m. end note]

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.

template<class UIntType, size_t w, size_t s, size_t r>
  class subtract_with_carry_engine {
    // 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 m1; }
    static constexpr result_type default_seed = 19780503u;

    // constructors and seeding functions
    explicit subtract_with_carry_engine(result_type value = default_seed);
    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 Xir,,Xi1, in that order, followed by c.

explicit subtract_with_carry_engine(result_type value = default_seed);

Effects: Constructs a subtract_­with_­carry_­engine object. Sets the values of Xr,,X1, in that order, as specified below. If X1 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:

                          40014u,0u,2147483563u> e(value == 0u ? default_seed : value);

Then, to set each Xk, obtain new values z0,,zn1 from n=w/32 successive invocations of e taken modulo 232. Set Xk to (n1j=0zj232j)modm.

Complexity: Exactly nr 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 rk, invokes q.generate(a+0, a+rk) and then, iteratively for i=r,,1, sets Xi to (k1j=0ak(i+r)+j232j)modm. If X1 is then 0, sets c to 1; otherwise sets c to 0.