[rand.eng.sub]

# 29 Numerics library [[numerics]](./#numerics)

## 29.5 Random number generation [[rand]](rand#eng.sub)

### 29.5.4 Random number engine class templates [[rand.eng]](rand.eng#sub)

#### 29.5.4.4 Class template subtract_with_carry_engine [rand.eng.sub]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2989)

A subtract_with_carry_engine random number engine
produces unsigned integer random numbers[.](#1.sentence-1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L2993)

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[.](#2.sentence-1)

The state xi additionally consists of an integer c (known as the [*carry*](#def:carry))
whose value is either 0 or 1[.](#2.sentence-2)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3006)

The state transition
is performed as follows:

- [(3.1)](#3.1)

  Let Y=XiâsâXiârâc[.](#3.1.sentence-1)

- [(3.2)](#3.2)

  Set Xi to y=Ymodm[.](#3.2.sentence-1)
  Set c to 1 if Y<0,
 otherwise set c to 0[.](#3.2.sentence-2)

[*Note [1](#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[.](#3.sentence-2)

â *end note*]

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3027)

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[.](#4.sentence-1)

[ð](#lib:subtract_with_carry_engine_)

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<class Sseq> explicit subtract_with_carry_engine(Sseq& q); void seed(result_type value = 0u); template<class Sseq> 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](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3079)

The following relations shall hold: 0u < s, s < r, 0 < w,
and w <= numeric_limits<UIntType>​::​digits[.](#5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3087)

The textual representation
consists of the values of Xiâr,â¦,Xiâ1,
in that order, followed by c[.](#6.sentence-1)

[ð](#lib:subtract_with_carry_engine,constructor)

`explicit subtract_with_carry_engine(result_type value);
`

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3099)

*Effects*: Sets the values of Xâr,â¦,Xâ1,
 in that order, as specified below[.](#7.sentence-1)

If Xâ1 is then 0,
 sets c to 1;
 otherwise sets c to 0[.](#7.sentence-2)

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[.](#7.sentence-4)

Set Xk to (ânâ1j=0zjâ232j)modm[.](#7.sentence-5)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3121)

*Complexity*: Exactly nâr invocations
 of e[.](#8.sentence-1)

[ð](#lib:subtract_with_carry_engine,constructor_)

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

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L3133)

*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[.](#9.sentence-1)

If Xâ1 is then 0,
 sets c to 1;
 otherwise sets c to 0[.](#9.sentence-2)
