From Jason Turner

[rand.eng]

C++17 → C++20 12.3 KB 123 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp3isogify/{from.md → to.md} +60 -50
tmp/tmp3isogify/{from.md → to.md} RENAMED
@@ -1,36 +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 section 
4
- [[rand.eng]] satisfies 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 section  [[rand.eng]] is constant.
9
 
10
- Except where specified otherwise, no function described in this section 
11
- [[rand.eng]] throws an exception.
12
 
13
- Every function described in this section  [[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 section  [[rand.eng]] only for engine
19
- operations that are not described in [[rand.req.eng]] or for operations
20
- where there is additional semantic information. In particular,
21
- declarations for copy constructors, for copy assignment operators, for
22
- streaming operators, and for equality and inequality operators are not
23
- shown in the synopses.
24
 
25
- Each template specified in this section  [[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);
@@ -74,11 +74,12 @@ template<class UIntType, UIntType a, UIntType c, UIntType m>
74
  static constexpr result_type min() { return c == 0u ? 1u: 0u; }
75
  static constexpr result_type max() { return m - 1u; }
76
  static constexpr result_type default_seed = 1u;
77
 
78
  // constructors and seeding functions
79
- explicit linear_congruential_engine(result_type s = default_seed);
 
80
  template<class Sseq> explicit linear_congruential_engine(Sseq& q);
81
  void seed(result_type s = default_seed);
82
  template<class Sseq> void seed(Sseq& q);
83
 
84
  // generating functions
@@ -86,41 +87,38 @@ template<class UIntType, UIntType a, UIntType c, UIntType m>
86
  void discard(unsigned long long z);
87
  };
88
  ```
89
 
90
  If the template parameter `m` is 0, the modulus m used throughout this
91
- section  [[rand.eng.lcong]] is `numeric_limits<result_type>::max()` plus
92
- 1.
93
 
94
  [*Note 1*: m need not be representable as a value of type
95
  `result_type`. — *end note*]
96
 
97
  If the template parameter `m` is not 0, the following relations shall
98
  hold: `a < m` and `c < m`.
99
 
100
  The textual representation consists of the value of xᵢ.
101
 
102
  ``` cpp
103
- explicit linear_congruential_engine(result_type s = default_seed);
104
  ```
105
 
106
- *Effects:* Constructs a `linear_congruential_engine` object. If
107
- c mod m is 0 and `s` mod m is 0, sets the engine’s state to 1,
108
- otherwise sets the engine’s state to `s` mod m.
109
 
110
  ``` cpp
111
  template<class Sseq> explicit linear_congruential_engine(Sseq& q);
112
  ```
113
 
114
- *Effects:* Constructs a `linear_congruential_engine` object. With
115
- $k = \left\lceil \frac{\log_2 m}
116
- {32}
117
- \right\rceil$ and a an array (or equivalent) of length
118
- k + 3, invokes `q.generate(`a+0`, `a+k+3`)` and then computes
119
- $S = \left(\sum_{j=0}^{k-1}a_{j+3} \cdot 2^{32j} \right) \bmod m$. If
120
- c mod m is 0 and S is 0, sets the engine’s state to 1, else sets the
121
- engine’s state to S.
122
 
123
  #### Class template `mersenne_twister_engine` <a id="rand.eng.mers">[[rand.eng.mers]]</a>
124
 
125
  A `mersenne_twister_engine` random number engine[^2] produces unsigned
126
  integer random numbers in the closed interval [0,2ʷ-1]. The state xᵢ of
@@ -130,21 +128,31 @@ applied to X are to be taken modulo n.
130
 
131
  The transition algorithm employs a twisted generalized feedback shift
132
  register defined by shift values n and m, a twist value r, and a
133
  conditional xor-mask a. To improve the uniformity of the result, the
134
  bits of the raw shift register are additionally *tempered* (i.e.,
135
- scrambled) according to a bit-scrambling matrix defined by values
136
- u, d, s, b, t, c, and ℓ.
137
 
138
  The state transition is performed as follows:
139
 
 
 
 
 
 
140
  The sequence X is initialized with the help of an initialization
141
  multiplier f.
142
 
143
  The generation algorithm determines the unsigned integer values
144
  z₁, z₂, z₃, z₄ as follows, then delivers z₄ as its result:
145
 
 
 
 
 
 
146
  ``` cpp
147
  template<class UIntType, size_t w, size_t n, size_t m, size_t r,
148
  UIntType a, size_t u, UIntType d, size_t s,
149
  UIntType b, size_t t,
150
  UIntType c, size_t l, UIntType f>
@@ -170,11 +178,12 @@ template<class UIntType, size_t w, size_t n, size_t m, size_t r,
170
  static constexpr result_type min() { return 0; }
171
  static constexpr result_type max() { return 2^w - 1; }
172
  static constexpr result_type default_seed = 5489u;
173
 
174
  // constructors and seeding functions
175
- explicit mersenne_twister_engine(result_type value = default_seed);
 
176
  template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
177
  void seed(result_type value = default_seed);
178
  template<class Sseq> void seed(Sseq& q);
179
 
180
  // generating functions
@@ -188,18 +197,18 @@ The following relations shall hold: `0 < m`, `m <= n`, `2u < w`,
188
  `w <= numeric_limits<UIntType>::digits`, `a <= (1u<<w) - 1u`,
189
  `b <= (1u<<w) - 1u`, `c <= (1u<<w) - 1u`, `d <= (1u<<w) - 1u`, and
190
  `f <= (1u<<w) - 1u`.
191
 
192
  The textual representation of xᵢ consists of the values of
193
- Xᵢ₋ₙ, …, Xᵢ₋₁, in that order.
194
 
195
  ``` cpp
196
- explicit mersenne_twister_engine(result_type value = default_seed);
197
  ```
198
 
199
- *Effects:* Constructs a `mersenne_twister_engine` object. Sets X₋ₙ to
200
- `value` mod 2ʷ. Then, iteratively for i = 1-n,…,-1, sets Xᵢ to $$%
201
  \bigl[f \cdot
202
  \bigl(X_{i-1} \xor \bigl(X_{i-1} \rightshift (w-2)\bigr)
203
  \bigr)
204
  + i \bmod n
205
  \bigr] \bmod 2^w
@@ -209,14 +218,13 @@ explicit mersenne_twister_engine(result_type value = default_seed);
209
 
210
  ``` cpp
211
  template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
212
  ```
213
 
214
- *Effects:* Constructs a `mersenne_twister_engine` object. With
215
- k = ⌈ w / 32 ⌉ and a an array (or equivalent) of length n ⋅ k, invokes
216
- `q.generate(`a+0`, `a+n ⋅ k`)` and then, iteratively for i = -n,…,-1,
217
- sets Xᵢ to
218
  $\left(\sum_{j=0}^{k-1}a_{k(i+n)+j} \cdot 2^{32j} \right) \bmod 2^w$.
219
  Finally, if the most significant w-r bits of X₋ₙ are zero, and if each
220
  of the other resulting Xᵢ is 0, changes X₋ₙ to 2ʷ⁻¹.
221
 
222
  #### Class template `subtract_with_carry_engine` <a id="rand.eng.sub">[[rand.eng.sub]]</a>
@@ -230,10 +238,13 @@ all subscripts applied to X are to be taken modulo r. The state xᵢ
230
  additionally consists of an integer c (known as the *carry*) whose value
231
  is either 0 or 1.
232
 
233
  The state transition is performed as follows:
234
 
 
 
 
235
  [*Note 1*: This algorithm corresponds to a modular linear function of
236
  the form TA(xᵢ) = (a ⋅ xᵢ) mod b, where b is of the form mʳ - mˢ + 1
237
  and a = b - (b - 1) / m. — *end note*]
238
 
239
  The generation algorithm is given by GA(xᵢ) = y, where y is the value
@@ -253,11 +264,12 @@ template<class UIntType, size_t w, size_t s, size_t r>
253
  static constexpr result_type min() { return 0; }
254
  static constexpr result_type max() { return m - 1; }
255
  static constexpr result_type default_seed = 19780503u;
256
 
257
  // constructors and seeding functions
258
- explicit subtract_with_carry_engine(result_type value = default_seed);
 
259
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
260
  void seed(result_type value = default_seed);
261
  template<class Sseq> void seed(Sseq& q);
262
 
263
  // generating functions
@@ -271,16 +283,15 @@ The following relations shall hold: `0u < s`, `s < r`, `0 < w`, and
271
 
272
  The textual representation consists of the values of Xᵢ₋ᵣ, …, Xᵢ₋₁, in
273
  that order, followed by c.
274
 
275
  ``` cpp
276
- explicit subtract_with_carry_engine(result_type value = default_seed);
277
  ```
278
 
279
- *Effects:* Constructs a `subtract_with_carry_engine` object. Sets the
280
- values of X₋ᵣ, …, X₋₁, in that order, as specified below. If X₋₁ is then
281
- 0, sets c to 1; otherwise sets c to 0.
282
 
283
  To set the values Xₖ, first construct `e`, a
284
  `linear_congruential_engine` object, as if by the following definition:
285
 
286
  ``` cpp
@@ -296,12 +307,11 @@ $\left( \sum_{j=0}^{n-1} z_j \cdot 2^{32j}\right) \bmod m$.
296
 
297
  ``` cpp
298
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
299
  ```
300
 
301
- *Effects:* Constructs a `subtract_with_carry_engine` object. With
302
- k = ⌈ w / 32 ⌉ and a an array (or equivalent) of length r ⋅ k, invokes
303
- `q.generate(`a+0`, `a+r ⋅ k`)` and then, iteratively for i = -r, …, -1,
304
- sets Xᵢ to
305
  $\left(\sum_{j=0}^{k-1}a_{k(i+r)+j} \cdot 2^{32j} \right) \bmod m$. If
306
  X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
307
 
 
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);
 
74
  static constexpr result_type min() { return c == 0u ? 1u: 0u; }
75
  static constexpr result_type max() { return m - 1u; }
76
  static constexpr result_type default_seed = 1u;
77
 
78
  // constructors and seeding functions
79
+ linear_congruential_engine() : linear_congruential_engine(default_seed) {}
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
 
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.
94
 
95
  [*Note 1*: m need not be representable as a value of type
96
  `result_type`. — *end note*]
97
 
98
  If the template parameter `m` is not 0, the following relations shall
99
  hold: `a < m` and `c < m`.
100
 
101
  The textual representation consists of the value of xᵢ.
102
 
103
  ``` cpp
104
+ explicit linear_congruential_engine(result_type s);
105
  ```
106
 
107
+ *Effects:* If c mod m is 0 and `s` mod m is 0, sets the engine’s
108
+ state to 1, otherwise sets the engine’s state to `s` mod m.
 
109
 
110
  ``` cpp
111
  template<class Sseq> explicit linear_congruential_engine(Sseq& q);
112
  ```
113
 
114
+ *Effects:* With $k = \left\lceil \frac{\log_2 m}{32} \right\rceil$ and a
115
+ an array (or equivalent) of length k + 3, invokes
116
+ `q.generate(`a + 0`, `a + k + 3`)` and then computes
117
+ $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
 
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.,
133
+ scrambled) according to a bit-scrambling matrix defined by values u, d,
134
+ s, b, t, c, and ℓ.
135
 
136
  The state transition is performed as follows:
137
 
138
+ - Concatenate the upper w-r bits of Xᵢ₋ₙ with the lower r bits of
139
+ $X_{i+1-n}$ to obtain an unsigned integer value Y.
140
+ - With $\alpha = a \cdot (Y \bitand 1)$, set Xᵢ to
141
+ $X_{i+m-n} \xor (Y \rightshift 1) \xor \alpha$.
142
+
143
  The sequence X is initialized with the help of an initialization
144
  multiplier f.
145
 
146
  The generation algorithm determines the unsigned integer values
147
  z₁, z₂, z₃, z₄ as follows, then delivers z₄ as its result:
148
 
149
+ - Let $z_1 = X_i \xor \bigl(( X_i \rightshift u ) \bitand d\bigr)$.
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>
 
178
  static constexpr result_type min() { return 0; }
179
  static constexpr result_type max() { return 2^w - 1; }
180
  static constexpr result_type default_seed = 5489u;
181
 
182
  // constructors and seeding functions
183
+ mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}
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
 
197
  `w <= numeric_limits<UIntType>::digits`, `a <= (1u<<w) - 1u`,
198
  `b <= (1u<<w) - 1u`, `c <= (1u<<w) - 1u`, `d <= (1u<<w) - 1u`, and
199
  `f <= (1u<<w) - 1u`.
200
 
201
  The textual representation of xᵢ consists of the values of
202
+ $X_{i - n}, \dotsc, X_{i - 1}$, in that order.
203
 
204
  ``` cpp
205
+ explicit mersenne_twister_engine(result_type value);
206
  ```
207
 
208
+ *Effects:* Sets X₋ₙ to `value` mod 2ʷ. Then, iteratively for
209
+ i = 1 - n, …, -1, sets Xᵢ to $$%
210
  \bigl[f \cdot
211
  \bigl(X_{i-1} \xor \bigl(X_{i-1} \rightshift (w-2)\bigr)
212
  \bigr)
213
  + i \bmod n
214
  \bigr] \bmod 2^w
 
218
 
219
  ``` cpp
220
  template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
221
  ```
222
 
223
+ *Effects:* With k = ⌈ w / 32 ⌉ and a an array (or equivalent) of length
224
+ n ⋅ k, invokes `q.generate(`a+0`, `a+n ⋅ k`)` and then, iteratively for
225
+ i = -n,…,-1, sets Xᵢ to
 
226
  $\left(\sum_{j=0}^{k-1}a_{k(i+n)+j} \cdot 2^{32j} \right) \bmod 2^w$.
227
  Finally, if the most significant w-r bits of X₋ₙ are zero, and if each
228
  of the other resulting Xᵢ is 0, changes X₋ₙ to 2ʷ⁻¹.
229
 
230
  #### Class template `subtract_with_carry_engine` <a id="rand.eng.sub">[[rand.eng.sub]]</a>
 
238
  additionally consists of an integer c (known as the *carry*) whose value
239
  is either 0 or 1.
240
 
241
  The state transition is performed as follows:
242
 
243
+ - Let Y = Xᵢ₋ₛ - Xᵢ₋ᵣ - c.
244
+ - Set Xᵢ to y = Y mod m. Set c to 1 if Y < 0, otherwise set c to 0.
245
+
246
  [*Note 1*: This algorithm corresponds to a modular linear function of
247
  the form TA(xᵢ) = (a ⋅ xᵢ) mod b, where b is of the form mʳ - mˢ + 1
248
  and a = b - (b - 1) / m. — *end note*]
249
 
250
  The generation algorithm is given by GA(xᵢ) = y, where y is the value
 
264
  static constexpr result_type min() { return 0; }
265
  static constexpr result_type max() { return m - 1; }
266
  static constexpr result_type default_seed = 19780503u;
267
 
268
  // constructors and seeding functions
269
+ subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
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
 
283
 
284
  The textual representation consists of the values of Xᵢ₋ᵣ, …, Xᵢ₋₁, in
285
  that order, followed by c.
286
 
287
  ``` cpp
288
+ explicit subtract_with_carry_engine(result_type value);
289
  ```
290
 
291
+ *Effects:* Sets the values of X₋ᵣ, …, X₋₁, in that order, as specified
292
+ below. If X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
 
293
 
294
  To set the values Xₖ, first construct `e`, a
295
  `linear_congruential_engine` object, as if by the following definition:
296
 
297
  ``` cpp
 
307
 
308
  ``` cpp
309
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
310
  ```
311
 
312
+ *Effects:* With k = ⌈ w / 32 ⌉ and a an array (or equivalent) of length
313
+ r ⋅ k, invokes `q.generate(`a + 0`, `a + r ⋅ k`)` and then, iteratively
314
+ for i = -r, …, -1, sets Xᵢ to
 
315
  $\left(\sum_{j=0}^{k-1}a_{k(i+r)+j} \cdot 2^{32j} \right) \bmod m$. If
316
  X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
317