From Jason Turner

[rand.eng]

C++23 → Trunk 12.2 KB 213 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpfweab1r3/{from.md → to.md} +189 -15
tmp/tmpfweab1r3/{from.md → to.md} RENAMED
@@ -21,11 +21,11 @@ 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]]:
@@ -91,21 +91,22 @@ namespace std {
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.
107
 
108
  [*Note 1*: m need not be representable as a value of type
109
  `result_type`. — *end note*]
110
 
111
  If the template parameter `m` is not 0, the following relations shall
@@ -209,14 +210,16 @@ namespace std {
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`,
@@ -289,17 +292,17 @@ namespace std {
289
  static constexpr size_t word_size = w;
290
  static constexpr size_t short_lag = s;
291
  static constexpr size_t long_lag = r;
292
  static constexpr result_type min() { return 0; }
293
  static constexpr result_type max() { return m - 1; }
294
- static constexpr result_type default_seed = 19780503u;
295
 
296
  // constructors and seeding functions
297
- subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
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);
@@ -309,14 +312,16 @@ namespace std {
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
@@ -334,12 +339,12 @@ below. If X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
334
 
335
  To set the values Xₖ, first construct `e`, a
336
  `linear_congruential_engine` object, as if by the following definition:
337
 
338
  ``` cpp
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$.
@@ -354,5 +359,174 @@ template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
354
  r ⋅ k, invokes `q.generate(`a + 0`, `a + r ⋅ k`)` and then, iteratively
355
  for i = -r, …, -1, sets Xᵢ to
356
  $\left(\sum_{j=0}^{k-1}a_{k(i+r)+j} \cdot 2^{32j} \right) \bmod m$. If
357
  X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
358
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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 constant 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]]:
 
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, // hosted
97
+ const linear_congruential_engine& x);
98
  template<class charT, class traits>
99
  friend basic_istream<charT, traits>&
100
+ operator>>(basic_istream<charT, traits>& is, // hosted
101
+ linear_congruential_engine& x);
102
  };
103
  }
104
  ```
105
 
106
+ If the template parameter `m` is 0, the modulus m used throughout
107
+ [[rand.eng.lcong]] is `numeric_limits<result_type>::max()` plus 1.
 
108
 
109
  [*Note 1*: m need not be representable as a value of type
110
  `result_type`. — *end note*]
111
 
112
  If the template parameter `m` is not 0, the following relations shall
 
210
  void discard(unsigned long long z);
211
 
212
  // inserters and extractors
213
  template<class charT, class traits>
214
  friend basic_ostream<charT, traits>&
215
+ operator<<(basic_ostream<charT, traits>& os, // hosted
216
+ const mersenne_twister_engine& x);
217
  template<class charT, class traits>
218
  friend basic_istream<charT, traits>&
219
+ operator>>(basic_istream<charT, traits>& is, // hosted
220
+ mersenne_twister_engine& x);
221
  };
222
  }
223
  ```
224
 
225
  The following relations shall hold: `0 < m`, `m <= n`, `2u < w`,
 
292
  static constexpr size_t word_size = w;
293
  static constexpr size_t short_lag = s;
294
  static constexpr size_t long_lag = r;
295
  static constexpr result_type min() { return 0; }
296
  static constexpr result_type max() { return m - 1; }
297
+ static constexpr uint_least32_t default_seed = 19780503u;
298
 
299
  // constructors and seeding functions
300
+ subtract_with_carry_engine() : subtract_with_carry_engine(0u) {}
301
  explicit subtract_with_carry_engine(result_type value);
302
  template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
303
+ void seed(result_type value = 0u);
304
  template<class Sseq> void seed(Sseq& q);
305
 
306
  // equality operators
307
  friend bool operator==(const subtract_with_carry_engine& x,
308
  const subtract_with_carry_engine& y);
 
312
  void discard(unsigned long long z);
313
 
314
  // inserters and extractors
315
  template<class charT, class traits>
316
  friend basic_ostream<charT, traits>&
317
+ operator<<(basic_ostream<charT, traits>& os, // hosted
318
+ const subtract_with_carry_engine& x);
319
  template<class charT, class traits>
320
  friend basic_istream<charT, traits>&
321
+ operator>>(basic_istream<charT, traits>& is, // hosted
322
+ subtract_with_carry_engine& x);
323
  };
324
  }
325
  ```
326
 
327
  The following relations shall hold: `0u < s`, `s < r`, `0 < w`, and
 
339
 
340
  To set the values Xₖ, first construct `e`, a
341
  `linear_congruential_engine` object, as if by the following definition:
342
 
343
  ``` cpp
344
+ linear_congruential_engine<uint_least32_t, 40014u, 0u, 2147483563u> e(
345
+ value == 0u ? default_seed : static_cast<uint_least32_t>(value % 2147483563u));
346
  ```
347
 
348
  Then, to set each Xₖ, obtain new values z₀, …, zₙ₋₁ from n = ⌈ w/32 ⌉
349
  successive invocations of `e`. Set Xₖ to
350
  $\left( \sum_{j=0}^{n-1} z_j \cdot 2^{32j}\right) \bmod m$.
 
359
  r ⋅ k, invokes `q.generate(`a + 0`, `a + r ⋅ k`)` and then, iteratively
360
  for i = -r, …, -1, sets Xᵢ to
361
  $\left(\sum_{j=0}^{k-1}a_{k(i+r)+j} \cdot 2^{32j} \right) \bmod m$. If
362
  X₋₁ is then 0, sets c to 1; otherwise sets c to 0.
363
 
364
+ #### Class template `philox_engine` <a id="rand.eng.philox">[[rand.eng.philox]]</a>
365
+
366
+ A `philox_engine` random number engine produces unsigned integer random
367
+ numbers in the interval \[`0`, m), where m = 2ʷ and the template
368
+ parameter w defines the range of the produced numbers. The state of a
369
+ `philox_engine` object consists of a sequence X of n unsigned integer
370
+ values of width w, a sequence K of n/2 values of `result_type`, a
371
+ sequence Y of n values of `result_type`, and a scalar i, where
372
+
373
+ - X is the interpretation of the unsigned integer *counter* value
374
+ $Z \cedef \sum_{j = 0}^{n - 1} X_j \cdot 2^{wj}$ of n ⋅ w bits,
375
+ - K are keys, which are generated once from the seed (see constructors
376
+ below) and remain constant unless the `seed` function [[rand.req.eng]]
377
+ is invoked,
378
+ - Y stores a batch of output values, and
379
+ - i is an index for an element of the sequence Y.
380
+
381
+ The generation algorithm returns Yᵢ, the value stored in the iᵗʰ element
382
+ of Y after applying the transition algorithm.
383
+
384
+ The state transition is performed as if by the following algorithm:
385
+
386
+ ``` cpp
387
+ i = i + 1
388
+ if (i == n) {
389
+ Y = Philox(K, X) // see below
390
+ Z = Z + 1
391
+ i = 0
392
+ }
393
+ ```
394
+
395
+ The `Philox` function maps the length-n/2 sequence K and the length-n
396
+ sequence X into a length-n output sequence Y. Philox applies an r-round
397
+ substitution-permutation network to the values in X. A single round of
398
+ the generation algorithm performs the following steps:
399
+
400
+ - The output sequence X' of the previous round (X in case of the first
401
+ round) is permuted to obtain the intermediate state V:
402
+ ``` cpp
403
+ Vⱼ = X'_{fₙ(j)}
404
+ ```
405
+
406
+ where j = 0, …, n - 1 and fₙ(j) is defined in [[rand.eng.philox.f]].
407
+ **Table: Values for the word permutation $\bm{f}_{\bm{n}}\bm{(j)}$** <a id="rand.eng.philox.f">[rand.eng.philox.f]</a>
408
+
409
+ | | |
410
+ | --------------------------------------------- | ---------------------------- |
411
+ | *[spans 2 columns]* $\bm{f}_{\bm{n}}\bm{(j)}$ | *[spans 4 columns]* $\bm{j}$ |
412
+ | \multicolumn{2}{|c|} | 0 | 1 | 2 | 3 |
413
+ | $\bm{n} $ | 2 | 0 | 1 | \multicolumn{2}{c|} |
414
+ | | 4 | 2 | 1 | 0 | 3 |
415
+
416
+
417
+ \[*Note 1*: For n = 2 the sequence is not permuted. — *end note*]
418
+ - The following computations are applied to the elements of the V
419
+ sequence:
420
+ ``` cpp
421
+ X_2k + 0} = \mulhi(V_2k, Mₖ, w) \xor key^qₖ \xor V_2k + 1}
422
+ X_2k + 1} = \mullo(V_2k, Mₖ, w)
423
+ ```
424
+
425
+ where:
426
+ - μllo(`a`, `b`, `w`) is the low half of the modular multiplication of
427
+ `a` and `b`: $(\tcode{a} \cdot \tcode{b}) \mod 2^w$,
428
+ - μlhi(`a`, `b`, `w`) is the high half of the modular multiplication
429
+ of `a` and `b`: (⌊ (`a` ⋅ `b`) / 2ʷ ⌋),
430
+ - k = 0, …, n/2 - 1 is the index in the sequences,
431
+ - q = 0, …, r - 1 is the index of the round,
432
+ - $\mathit{key}^q_k$ is the kᵗʰ round key for round q,
433
+ $\mathit{key}^q_k \cedef (K_k + q \cdot C_k) \mod 2^w$,
434
+ - Kₖ are the elements of the key sequence K,
435
+ - Mₖ is `multipliers[k]`, and
436
+ - Cₖ is `round_consts[k]`.
437
+
438
+ After r applications of the single-round function, `Philox` returns the
439
+ sequence Y = X'.
440
+
441
+ ``` cpp
442
+ namespace std {
443
+ template<class UIntType, size_t w, size_t n, size_t r, UIntType... consts>
444
+ class philox_engine {
445
+ static constexpr size_t array-size = n / 2; // exposition only
446
+ public:
447
+ // types
448
+ using result_type = UIntType;
449
+
450
+ // engine characteristics
451
+ static constexpr size_t word_size = w;
452
+ static constexpr size_t word_count = n;
453
+ static constexpr size_t round_count = r;
454
+ static constexpr array<result_type, array-size> multipliers;
455
+ static constexpr array<result_type, array-size> round_consts;
456
+ static constexpr result_type min() { return 0; }
457
+ static constexpr result_type max() { return m - 1; }
458
+ static constexpr result_type default_seed = 20111115u;
459
+
460
+ // constructors and seeding functions
461
+ philox_engine() : philox_engine(default_seed) {}
462
+ explicit philox_engine(result_type value);
463
+ template<class Sseq> explicit philox_engine(Sseq& q);
464
+ void seed(result_type value = default_seed);
465
+ template<class Sseq> void seed(Sseq& q);
466
+
467
+ void set_counter(const array<result_type, n>& counter);
468
+
469
+ // equality operators
470
+ friend bool operator==(const philox_engine& x, const philox_engine& y);
471
+
472
+ // generating functions
473
+ result_type operator()();
474
+ void discard(unsigned long long z);
475
+
476
+ // inserters and extractors
477
+ template<class charT, class traits>
478
+ friend basic_ostream<charT, traits>&
479
+ operator<<(basic_ostream<charT, traits>& os, const philox_engine& x); // hosted
480
+ template<class charT, class traits>
481
+ friend basic_istream<charT, traits>&
482
+ operator>>(basic_istream<charT, traits>& is, philox_engine& x); // hosted
483
+ };
484
+ }
485
+ ```
486
+
487
+ *Mandates:*
488
+
489
+ - `sizeof...(consts) == n` is `true`, and
490
+ - `n == 2 || n == 4` is `true`, and
491
+ - `0 < r` is `true`, and
492
+ - `0 < w && w <= numeric_limits<UIntType>::digits` is `true`.
493
+
494
+ The template parameter pack `consts` represents the Mₖ and Cₖ constants
495
+ which are grouped as follows:
496
+ $[ M_0, C_0, M_1, C_1, M_2, C_2, \dotsc, M_{n/2 - 1}, C_{n/2 - 1} ]$.
497
+
498
+ The textual representation consists of the values of
499
+ $K_0, \dotsc, K_{n/2 - 1}, X_{0}, \dotsc, X_{n - 1}, i$, in that order.
500
+
501
+ [*Note 2*: The stream extraction operator can reconstruct Y from K and
502
+ X, as needed. — *end note*]
503
+
504
+ ``` cpp
505
+ explicit philox_engine(result_type value);
506
+ ```
507
+
508
+ *Effects:* Sets the K₀ element of sequence K to
509
+ $\texttt{value} \mod 2^w$. All elements of sequences X and K (except K₀)
510
+ are set to `0`. The value of i is set to n - 1.
511
+
512
+ ``` cpp
513
+ template<class Sseq> explicit philox_engine(Sseq& q);
514
+ ```
515
+
516
+ *Effects:* With p = ⌈ w / 32 ⌉ and an array (or equivalent) `a` of
517
+ length (n/2) ⋅ p, invokes `q.generate(a + 0, a + n / 2 * `p`)` and then
518
+ iteratively for k = 0, …, n/2 - 1, sets Kₖ to
519
+ $\left(\sum_{j = 0}^{p - 1} a_{k p + j} \cdot 2^{32j} \right) \mod 2^w$.
520
+ All elements of sequence X are set to `0`. The value of i is set to
521
+ n - 1.
522
+
523
+ ``` cpp
524
+ void set_counter(const array<result_type, n>& c);
525
+ ```
526
+
527
+ *Effects:* For j = 0, …, n - 1 sets Xⱼ to $C_{n - 1 - j} \mod 2^w$. The
528
+ value of i is set to n - 1.
529
+
530
+ [*Note 1*: The counter is the value Z introduced at the beginning of
531
+ this subclause. — *end note*]
532
+