From Jason Turner

[rand.eng]

C++20 → C++23 9.2 KB 104 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpenphrf5f/{from.md → to.md} +67 -26
tmp/tmpenphrf5f/{from.md → to.md} RENAMED
@@ -1,37 +1,36 @@
1
  ### Random number engine class templates <a id="rand.eng">[[rand.eng]]</a>
2
 
3
- Each type instantiated from a class template specified in this
4
- subclause  [[rand.eng]] meets the requirements of a random number engine
5
- [[rand.req.eng]] type.
 
6
 
7
  Except where specified otherwise, the complexity of each function
8
- specified in this subclause  [[rand.eng]] is constant.
9
 
10
- Except where specified otherwise, no function described in this
11
- subclause  [[rand.eng]] throws an exception.
12
 
13
- Every function described in this subclause  [[rand.eng]] that has a
14
- function parameter `q` of type `Sseq&` for a template type parameter
15
- named `Sseq` that is different from type `seed_seq` throws what and when
16
- the invocation of `q.generate` throws.
17
 
18
- Descriptions are provided in this subclause  [[rand.eng]] only for
19
- engine operations that are not described in [[rand.req.eng]] or for
20
- operations where there is additional semantic information. In
21
- particular, declarations for copy constructors, for copy assignment
22
- operators, for streaming operators, and for equality and inequality
23
- operators are not shown in the synopses.
24
 
25
- Each template specified in this subclause  [[rand.eng]] requires one or
26
- more relationships, involving the value(s) of its non-type template
27
  parameter(s), to hold. A program instantiating any of these templates is
28
  ill-formed if any such required relationship fails to hold.
29
 
30
  For every random number engine and for every random number engine
31
- adaptor `X` defined in this subclause [[rand.eng]] and in subclause 
32
- [[rand.adapt]]:
33
 
34
  - if the constructor
35
  ``` cpp
36
  template<class Sseq> explicit X(Sseq& q);
37
  ```
@@ -59,10 +58,11 @@ object `x` is of size 1 and consists of a single integer. The transition
59
  algorithm is a modular linear function of the form
60
  TA(xᵢ) = (a ⋅ xᵢ + c) mod m; the generation algorithm is
61
  GA(xᵢ) = xᵢ₊₁.
62
 
63
  ``` cpp
 
64
  template<class UIntType, UIntType a, UIntType c, UIntType m>
65
  class linear_congruential_engine {
66
  public:
67
  // types
68
  using result_type = UIntType;
@@ -80,14 +80,27 @@ template<class UIntType, UIntType a, UIntType c, UIntType m>
80
  explicit linear_congruential_engine(result_type s);
81
  template<class Sseq> explicit linear_congruential_engine(Sseq& q);
82
  void seed(result_type s = default_seed);
83
  template<class Sseq> void seed(Sseq& q);
84
 
 
 
 
 
85
  // generating functions
86
  result_type operator()();
87
  void discard(unsigned long long z);
 
 
 
 
 
 
 
 
88
  };
 
89
  ```
90
 
91
  If the template parameter `m` is 0, the modulus m used throughout this
92
  subclause  [[rand.eng.lcong]] is `numeric_limits<result_type>::max()`
93
  plus 1.
@@ -118,15 +131,16 @@ $S = \left(\sum_{j = 0}^{k - 1} a_{j + 3} \cdot 2^{32j} \right) \bmod m$.
118
  If c mod m is 0 and S is 0, sets the engine’s state to 1, else sets
119
  the engine’s state to S.
120
 
121
  #### Class template `mersenne_twister_engine` <a id="rand.eng.mers">[[rand.eng.mers]]</a>
122
 
123
- A `mersenne_twister_engine` random number engine[^2] produces unsigned
124
- integer random numbers in the closed interval [0,2ʷ-1]. The state xᵢ of
125
- a `mersenne_twister_engine` object `x` is of size n and consists of a
126
- sequence X of n values of the type delivered by `x`; all subscripts
127
- applied to X are to be taken modulo n.
 
128
 
129
  The transition algorithm employs a twisted generalized feedback shift
130
  register defined by shift values n and m, a twist value r, and a
131
  conditional xor-mask a. To improve the uniformity of the result, the
132
  bits of the raw shift register are additionally *tempered* (i.e.,
@@ -150,10 +164,11 @@ z₁, z₂, z₃, z₄ as follows, then delivers z₄ as its result:
150
  - Let $z_2 = z_1 \xor \bigl( (z_1 \leftshift{w} s) \bitand b \bigr)$.
151
  - Let $z_3 = z_2 \xor \bigl( (z_2 \leftshift{w} t) \bitand c \bigr)$.
152
  - Let $z_4 = z_3 \xor ( z_3 \rightshift \ell )$.
153
 
154
  ``` cpp
 
155
  template<class UIntType, size_t w, size_t n, size_t m, size_t r,
156
  UIntType a, size_t u, UIntType d, size_t s,
157
  UIntType b, size_t t,
158
  UIntType c, size_t l, UIntType f>
159
  class mersenne_twister_engine {
@@ -184,14 +199,26 @@ template<class UIntType, size_t w, size_t n, size_t m, size_t r,
184
  explicit mersenne_twister_engine(result_type value);
185
  template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
186
  void seed(result_type value = default_seed);
187
  template<class Sseq> void seed(Sseq& q);
188
 
 
 
 
189
  // generating functions
190
  result_type operator()();
191
  void discard(unsigned long long z);
 
 
 
 
 
 
 
 
192
  };
 
193
  ```
194
 
195
  The following relations shall hold: `0 < m`, `m <= n`, `2u < w`,
196
  `r <= w`, `u <= w`, `s <= w`, `t <= w`, `l <= w`,
197
  `w <= numeric_limits<UIntType>::digits`, `a <= (1u<<w) - 1u`,
@@ -249,10 +276,11 @@ and a = b - (b - 1) / m. — *end note*]
249
 
250
  The generation algorithm is given by GA(xᵢ) = y, where y is the value
251
  produced as a result of advancing the engine’s state as described above.
252
 
253
  ``` cpp
 
254
  template<class UIntType, size_t w, size_t s, size_t r>
255
  class subtract_with_carry_engine {
256
  public:
257
  // types
258
  using result_type = UIntType;
@@ -270,14 +298,27 @@ template<class UIntType, size_t w, size_t s, size_t r>
270
  explicit subtract_with_carry_engine(result_type value);
271
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
272
  void seed(result_type value = default_seed);
273
  template<class Sseq> void seed(Sseq& q);
274
 
 
 
 
 
275
  // generating functions
276
  result_type operator()();
277
  void discard(unsigned long long z);
 
 
 
 
 
 
 
 
278
  };
 
279
  ```
280
 
281
  The following relations shall hold: `0u < s`, `s < r`, `0 < w`, and
282
  `w <= numeric_limits<UIntType>::digits`.
283
 
@@ -298,11 +339,11 @@ To set the values Xₖ, first construct `e`, a
298
  linear_congruential_engine<result_type,
299
  40014u,0u,2147483563u> e(value == 0u ? default_seed : value);
300
  ```
301
 
302
  Then, to set each Xₖ, obtain new values z₀, …, zₙ₋₁ from n = ⌈ w/32 ⌉
303
- successive invocations of `e` taken modulo 2³². Set Xₖ to
304
  $\left( \sum_{j=0}^{n-1} z_j \cdot 2^{32j}\right) \bmod m$.
305
 
306
  *Complexity:* Exactly n ⋅ `r` invocations of `e`.
307
 
308
  ``` cpp
 
1
  ### Random number engine class templates <a id="rand.eng">[[rand.eng]]</a>
2
 
3
+ #### General <a id="rand.eng.general">[[rand.eng.general]]</a>
4
+
5
+ Each type instantiated from a class template specified in [[rand.eng]]
6
+ meets the requirements of a random number engine [[rand.req.eng]] type.
7
 
8
  Except where specified otherwise, the complexity of each function
9
+ specified in [[rand.eng]] is constant.
10
 
11
+ Except where specified otherwise, no function described in [[rand.eng]]
12
+ throws an exception.
13
 
14
+ Every function described in [[rand.eng]] that has a function parameter
15
+ `q` of type `Sseq&` for a template type parameter named `Sseq` that is
16
+ different from type `seed_seq` throws what and when the invocation of
17
+ `q.generate` throws.
18
 
19
+ Descriptions are provided in [[rand.eng]] only for engine operations
20
+ that are not described in [[rand.req.eng]] or for operations where there
21
+ is additional semantic information. In particular, declarations for copy
22
+ constructors, for copy assignment operators, for streaming operators,
23
+ and for equality and inequality operators are not shown in the synopses.
 
24
 
25
+ Each template specified in [[rand.eng]] requires one or more
26
+ relationships, involving the value(s) of its non-type template
27
  parameter(s), to hold. A program instantiating any of these templates is
28
  ill-formed if any such required relationship fails to hold.
29
 
30
  For every random number engine and for every random number engine
31
+ adaptor `X` defined in [[rand.eng]] and in [[rand.adapt]]:
 
32
 
33
  - if the constructor
34
  ``` cpp
35
  template<class Sseq> explicit X(Sseq& q);
36
  ```
 
58
  algorithm is a modular linear function of the form
59
  TA(xᵢ) = (a ⋅ xᵢ + c) mod m; the generation algorithm is
60
  GA(xᵢ) = xᵢ₊₁.
61
 
62
  ``` cpp
63
+ namespace std {
64
  template<class UIntType, UIntType a, UIntType c, UIntType m>
65
  class linear_congruential_engine {
66
  public:
67
  // types
68
  using result_type = UIntType;
 
80
  explicit linear_congruential_engine(result_type s);
81
  template<class Sseq> explicit linear_congruential_engine(Sseq& q);
82
  void seed(result_type s = default_seed);
83
  template<class Sseq> void seed(Sseq& q);
84
 
85
+ // equality operators
86
+ friend bool operator==(const linear_congruential_engine& x,
87
+ const linear_congruential_engine& y);
88
+
89
  // generating functions
90
  result_type operator()();
91
  void discard(unsigned long long z);
92
+
93
+ // inserters and extractors
94
+ template<class charT, class traits>
95
+ friend basic_ostream<charT, traits>&
96
+ operator<<(basic_ostream<charT, traits>& os, const linear_congruential_engine& x);
97
+ template<class charT, class traits>
98
+ friend basic_istream<charT, traits>&
99
+ operator>>(basic_istream<charT, traits>& is, linear_congruential_engine& x);
100
  };
101
+ }
102
  ```
103
 
104
  If the template parameter `m` is 0, the modulus m used throughout this
105
  subclause  [[rand.eng.lcong]] is `numeric_limits<result_type>::max()`
106
  plus 1.
 
131
  If c mod m is 0 and S is 0, sets the engine’s state to 1, else sets
132
  the engine’s state to S.
133
 
134
  #### Class template `mersenne_twister_engine` <a id="rand.eng.mers">[[rand.eng.mers]]</a>
135
 
136
+ A `mersenne_twister_engine` random number engine[^3]
137
+
138
+ produces unsigned integer random numbers in the closed interval
139
+ [0,2ʷ-1]. The state xᵢ of a `mersenne_twister_engine` object `x` is of
140
+ size n and consists of a sequence X of n values of the type delivered by
141
+ `x`; all subscripts applied to X are to be taken modulo n.
142
 
143
  The transition algorithm employs a twisted generalized feedback shift
144
  register defined by shift values n and m, a twist value r, and a
145
  conditional xor-mask a. To improve the uniformity of the result, the
146
  bits of the raw shift register are additionally *tempered* (i.e.,
 
164
  - Let $z_2 = z_1 \xor \bigl( (z_1 \leftshift{w} s) \bitand b \bigr)$.
165
  - Let $z_3 = z_2 \xor \bigl( (z_2 \leftshift{w} t) \bitand c \bigr)$.
166
  - Let $z_4 = z_3 \xor ( z_3 \rightshift \ell )$.
167
 
168
  ``` cpp
169
+ namespace std {
170
  template<class UIntType, size_t w, size_t n, size_t m, size_t r,
171
  UIntType a, size_t u, UIntType d, size_t s,
172
  UIntType b, size_t t,
173
  UIntType c, size_t l, UIntType f>
174
  class mersenne_twister_engine {
 
199
  explicit mersenne_twister_engine(result_type value);
200
  template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
201
  void seed(result_type value = default_seed);
202
  template<class Sseq> void seed(Sseq& q);
203
 
204
+ // equality operators
205
+ friend bool operator==(const mersenne_twister_engine& x, const mersenne_twister_engine& y);
206
+
207
  // generating functions
208
  result_type operator()();
209
  void discard(unsigned long long z);
210
+
211
+ // inserters and extractors
212
+ template<class charT, class traits>
213
+ friend basic_ostream<charT, traits>&
214
+ operator<<(basic_ostream<charT, traits>& os, const mersenne_twister_engine& x);
215
+ template<class charT, class traits>
216
+ friend basic_istream<charT, traits>&
217
+ operator>>(basic_istream<charT, traits>& is, mersenne_twister_engine& x);
218
  };
219
+ }
220
  ```
221
 
222
  The following relations shall hold: `0 < m`, `m <= n`, `2u < w`,
223
  `r <= w`, `u <= w`, `s <= w`, `t <= w`, `l <= w`,
224
  `w <= numeric_limits<UIntType>::digits`, `a <= (1u<<w) - 1u`,
 
276
 
277
  The generation algorithm is given by GA(xᵢ) = y, where y is the value
278
  produced as a result of advancing the engine’s state as described above.
279
 
280
  ``` cpp
281
+ namespace std {
282
  template<class UIntType, size_t w, size_t s, size_t r>
283
  class subtract_with_carry_engine {
284
  public:
285
  // types
286
  using result_type = UIntType;
 
298
  explicit subtract_with_carry_engine(result_type value);
299
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
300
  void seed(result_type value = default_seed);
301
  template<class Sseq> void seed(Sseq& q);
302
 
303
+ // equality operators
304
+ friend bool operator==(const subtract_with_carry_engine& x,
305
+ const subtract_with_carry_engine& y);
306
+
307
  // generating functions
308
  result_type operator()();
309
  void discard(unsigned long long z);
310
+
311
+ // inserters and extractors
312
+ template<class charT, class traits>
313
+ friend basic_ostream<charT, traits>&
314
+ operator<<(basic_ostream<charT, traits>& os, const subtract_with_carry_engine& x);
315
+ template<class charT, class traits>
316
+ friend basic_istream<charT, traits>&
317
+ operator>>(basic_istream<charT, traits>& is, subtract_with_carry_engine& x);
318
  };
319
+ }
320
  ```
321
 
322
  The following relations shall hold: `0u < s`, `s < r`, `0 < w`, and
323
  `w <= numeric_limits<UIntType>::digits`.
324
 
 
339
  linear_congruential_engine<result_type,
340
  40014u,0u,2147483563u> e(value == 0u ? default_seed : value);
341
  ```
342
 
343
  Then, to set each Xₖ, obtain new values z₀, …, zₙ₋₁ from n = ⌈ w/32 ⌉
344
+ successive invocations of `e`. Set Xₖ to
345
  $\left( \sum_{j=0}^{n-1} z_j \cdot 2^{32j}\right) \bmod m$.
346
 
347
  *Complexity:* Exactly n ⋅ `r` invocations of `e`.
348
 
349
  ``` cpp