From Jason Turner

[rand.eng.philox]

C++23 → Trunk 6.7 KB 172 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/tmp7miprf_g/{from.md → to.md} +169 -0
tmp/tmp7miprf_g/{from.md → to.md} RENAMED
@@ -0,0 +1,169 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ #### Class template `philox_engine` <a id="rand.eng.philox">[[rand.eng.philox]]</a>
2
+
3
+ A `philox_engine` random number engine produces unsigned integer random
4
+ numbers in the interval \[`0`, m), where m = 2ʷ and the template
5
+ parameter w defines the range of the produced numbers. The state of a
6
+ `philox_engine` object consists of a sequence X of n unsigned integer
7
+ values of width w, a sequence K of n/2 values of `result_type`, a
8
+ sequence Y of n values of `result_type`, and a scalar i, where
9
+
10
+ - X is the interpretation of the unsigned integer *counter* value
11
+ $Z \cedef \sum_{j = 0}^{n - 1} X_j \cdot 2^{wj}$ of n ⋅ w bits,
12
+ - K are keys, which are generated once from the seed (see constructors
13
+ below) and remain constant unless the `seed` function [[rand.req.eng]]
14
+ is invoked,
15
+ - Y stores a batch of output values, and
16
+ - i is an index for an element of the sequence Y.
17
+
18
+ The generation algorithm returns Yᵢ, the value stored in the iᵗʰ element
19
+ of Y after applying the transition algorithm.
20
+
21
+ The state transition is performed as if by the following algorithm:
22
+
23
+ ``` cpp
24
+ i = i + 1
25
+ if (i == n) {
26
+ Y = Philox(K, X) // see below
27
+ Z = Z + 1
28
+ i = 0
29
+ }
30
+ ```
31
+
32
+ The `Philox` function maps the length-n/2 sequence K and the length-n
33
+ sequence X into a length-n output sequence Y. Philox applies an r-round
34
+ substitution-permutation network to the values in X. A single round of
35
+ the generation algorithm performs the following steps:
36
+
37
+ - The output sequence X' of the previous round (X in case of the first
38
+ round) is permuted to obtain the intermediate state V:
39
+ ``` cpp
40
+ Vⱼ = X'_{fₙ(j)}
41
+ ```
42
+
43
+ where j = 0, …, n - 1 and fₙ(j) is defined in [[rand.eng.philox.f]].
44
+ **Table: Values for the word permutation $\bm{f}_{\bm{n}}\bm{(j)}$** <a id="rand.eng.philox.f">[rand.eng.philox.f]</a>
45
+
46
+ | | |
47
+ | --------------------------------------------- | ---------------------------- |
48
+ | *[spans 2 columns]* $\bm{f}_{\bm{n}}\bm{(j)}$ | *[spans 4 columns]* $\bm{j}$ |
49
+ | \multicolumn{2}{|c|} | 0 | 1 | 2 | 3 |
50
+ | $\bm{n} $ | 2 | 0 | 1 | \multicolumn{2}{c|} |
51
+ | | 4 | 2 | 1 | 0 | 3 |
52
+
53
+
54
+ \[*Note 1*: For n = 2 the sequence is not permuted. — *end note*]
55
+ - The following computations are applied to the elements of the V
56
+ sequence:
57
+ ``` cpp
58
+ X_2k + 0} = \mulhi(V_2k, Mₖ, w) \xor key^qₖ \xor V_2k + 1}
59
+ X_2k + 1} = \mullo(V_2k, Mₖ, w)
60
+ ```
61
+
62
+ where:
63
+ - μllo(`a`, `b`, `w`) is the low half of the modular multiplication of
64
+ `a` and `b`: $(\tcode{a} \cdot \tcode{b}) \mod 2^w$,
65
+ - μlhi(`a`, `b`, `w`) is the high half of the modular multiplication
66
+ of `a` and `b`: (⌊ (`a` ⋅ `b`) / 2ʷ ⌋),
67
+ - k = 0, …, n/2 - 1 is the index in the sequences,
68
+ - q = 0, …, r - 1 is the index of the round,
69
+ - $\mathit{key}^q_k$ is the kᵗʰ round key for round q,
70
+ $\mathit{key}^q_k \cedef (K_k + q \cdot C_k) \mod 2^w$,
71
+ - Kₖ are the elements of the key sequence K,
72
+ - Mₖ is `multipliers[k]`, and
73
+ - Cₖ is `round_consts[k]`.
74
+
75
+ After r applications of the single-round function, `Philox` returns the
76
+ sequence Y = X'.
77
+
78
+ ``` cpp
79
+ namespace std {
80
+ template<class UIntType, size_t w, size_t n, size_t r, UIntType... consts>
81
+ class philox_engine {
82
+ static constexpr size_t array-size = n / 2; // exposition only
83
+ public:
84
+ // types
85
+ using result_type = UIntType;
86
+
87
+ // engine characteristics
88
+ static constexpr size_t word_size = w;
89
+ static constexpr size_t word_count = n;
90
+ static constexpr size_t round_count = r;
91
+ static constexpr array<result_type, array-size> multipliers;
92
+ static constexpr array<result_type, array-size> round_consts;
93
+ static constexpr result_type min() { return 0; }
94
+ static constexpr result_type max() { return m - 1; }
95
+ static constexpr result_type default_seed = 20111115u;
96
+
97
+ // constructors and seeding functions
98
+ philox_engine() : philox_engine(default_seed) {}
99
+ explicit philox_engine(result_type value);
100
+ template<class Sseq> explicit philox_engine(Sseq& q);
101
+ void seed(result_type value = default_seed);
102
+ template<class Sseq> void seed(Sseq& q);
103
+
104
+ void set_counter(const array<result_type, n>& counter);
105
+
106
+ // equality operators
107
+ friend bool operator==(const philox_engine& x, const philox_engine& y);
108
+
109
+ // generating functions
110
+ result_type operator()();
111
+ void discard(unsigned long long z);
112
+
113
+ // inserters and extractors
114
+ template<class charT, class traits>
115
+ friend basic_ostream<charT, traits>&
116
+ operator<<(basic_ostream<charT, traits>& os, const philox_engine& x); // hosted
117
+ template<class charT, class traits>
118
+ friend basic_istream<charT, traits>&
119
+ operator>>(basic_istream<charT, traits>& is, philox_engine& x); // hosted
120
+ };
121
+ }
122
+ ```
123
+
124
+ *Mandates:*
125
+
126
+ - `sizeof...(consts) == n` is `true`, and
127
+ - `n == 2 || n == 4` is `true`, and
128
+ - `0 < r` is `true`, and
129
+ - `0 < w && w <= numeric_limits<UIntType>::digits` is `true`.
130
+
131
+ The template parameter pack `consts` represents the Mₖ and Cₖ constants
132
+ which are grouped as follows:
133
+ $[ M_0, C_0, M_1, C_1, M_2, C_2, \dotsc, M_{n/2 - 1}, C_{n/2 - 1} ]$.
134
+
135
+ The textual representation consists of the values of
136
+ $K_0, \dotsc, K_{n/2 - 1}, X_{0}, \dotsc, X_{n - 1}, i$, in that order.
137
+
138
+ [*Note 2*: The stream extraction operator can reconstruct Y from K and
139
+ X, as needed. — *end note*]
140
+
141
+ ``` cpp
142
+ explicit philox_engine(result_type value);
143
+ ```
144
+
145
+ *Effects:* Sets the K₀ element of sequence K to
146
+ $\texttt{value} \mod 2^w$. All elements of sequences X and K (except K₀)
147
+ are set to `0`. The value of i is set to n - 1.
148
+
149
+ ``` cpp
150
+ template<class Sseq> explicit philox_engine(Sseq& q);
151
+ ```
152
+
153
+ *Effects:* With p = ⌈ w / 32 ⌉ and an array (or equivalent) `a` of
154
+ length (n/2) ⋅ p, invokes `q.generate(a + 0, a + n / 2 * `p`)` and then
155
+ iteratively for k = 0, …, n/2 - 1, sets Kₖ to
156
+ $\left(\sum_{j = 0}^{p - 1} a_{k p + j} \cdot 2^{32j} \right) \mod 2^w$.
157
+ All elements of sequence X are set to `0`. The value of i is set to
158
+ n - 1.
159
+
160
+ ``` cpp
161
+ void set_counter(const array<result_type, n>& c);
162
+ ```
163
+
164
+ *Effects:* For j = 0, …, n - 1 sets Xⱼ to $C_{n - 1 - j} \mod 2^w$. The
165
+ value of i is set to n - 1.
166
+
167
+ [*Note 1*: The counter is the value Z introduced at the beginning of
168
+ this subclause. — *end note*]
169
+