28 Numerics library [numerics]

28.5 Random number generation [rand]

28.5.4 Random number engine class templates [rand.eng]

28.5.4.5 Class template philox_engine [rand.eng.philox]

A philox_engine random number engine produces unsigned integer random numbers in the closed interval [0, m], where

m = 2^{w} - 1

and the template parameter w defines the range of the produced numbers.

The state of a philox_engine object consists of a sequence X of n unsigned integer values of width w, a sequence K of

n / 2

values of result_type, a sequence Y of n values of result_type, and a scalar i, where

(1.1)
X is the interpretation of the unsigned integer counter value $Z : = \sum_{j = 0}^{n - 1} X_{j} \cdot 2^{w j}$ of $n \cdot w$ bits,
(1.2)
K are keys, which are generated once from the seed (see constructors below) and remain constant unless the seed function ([rand.req.eng]) is invoked,
(1.3)
Y stores a batch of output values, and
(1.4)
i is an index for an element of the sequence Y.

The generation algorithm returns

Y_{i}

, the value stored in the

i^{t h}

element of Y after applying the transition algorithm.

The state transition is performed as if by the following algorithm: i = i + 1 if (i == n) { Y = Philox(K, X) // see below Z = Z + 1 i = 0 }

The Philox function maps the length-

n / 2

sequence K and the length-n sequence X into a length-n output sequence Y.

Philox applies an r-round substitution-permutation network to the values in X.

A single round of the generation algorithm performs the following steps:

(4.1)
The output sequence $X^{'}$ of the previous round (X in case of the first round) is permuted to obtain the intermediate state V: $V_{j} = X_{f_{n} (j)}^{'}$ where $j = 0, \dots, n - 1$ and $f_{n} (j)$ is defined in Table 101.
Table 101: Values for the word permutation $f_{n} (j)$ [tab:rand.eng.philox.f]
🔗
$f_{n} (j)$
j
🔗
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
🔗
n
2
0
1
🔗
4
0
3
2
1
🔗
8
2
1
4
7
6
5
0
3
🔗
16
0
9
2
13
6
11
4
15
10
7
12
3
14
5
8
1
🔗

[Note 1:
For $n = 2$ the sequence is not permuted.
— end note]
(4.2)
The following computations are applied to the elements of the V sequence: $X_{2 k + 0} = mullo (V_{2 k + 1}, M_{k}, w)$ $X_{2 k + 1} = mulhi (V_{2 k + 1}, M_{k}, w) x o r {k e y}_{k}^{q} x o r V_{2 k}$ where:
- (4.2.1)
  mullo(a, b, w) is the low half of the modular multiplication of a and b: $(a \cdot b) mod 2^{w}$ ,
- (4.2.2)
  mulhi(a, b, w) is the high half of the modular multiplication of a and b: $(⌊ (a \cdot b) / 2^{w} ⌋)$ ,
- (4.2.3)
  $k = 0, \dots, n / 2 - 1$ is the index in the sequences,
- (4.2.4)
  $q = 0, \dots, r - 1$ is the index of the round,
- (4.2.5)
  ${k e y}_{k}^{q}$ is the $k^{th}$ round key for round q, ${k e y}_{k}^{q} : = (K_{k} + q \cdot C_{k}) mod 2^{w}$ ,
- (4.2.6)
  $K_{k}$ are the elements of the key sequence K,
- (4.2.7)
  $M_{k}$ is multipliers[k], and
- (4.2.8)
  $C_{k}$ is round_consts[k].

After r applications of the single-round function, Philox returns the sequence

Y = X^{'}

🔗

namespace std { template<class UIntType, size_t w, size_t n, size_t r, UIntType... consts> class philox_engine { static constexpr size_t array-size = n / 2; // exposition only public: // types using result_type = UIntType; // engine characteristics static constexpr size_t word_size = w; static constexpr size_t word_count = n; static constexpr size_t round_count = r; static constexpr array<result_type, array-size> multipliers; static constexpr array<result_type, array-size> round_consts; static constexpr result_type min() { return 0; } static constexpr result_type max() { return m - 1; } static constexpr result_type default_seed = 20111115u; // constructors and seeding functions philox_engine() : philox_engine(default_seed) {} explicit philox_engine(result_type value); template<class Sseq> explicit philox_engine(Sseq& q); void seed(result_type value = default_seed); template<class Sseq> void seed(Sseq& q); void set_counter(const array<result_type, n>& counter); // equality operators friend bool operator==(const philox_engine& x, const philox_engine& y); // generating functions result_type operator()(); void discard(unsigned long long z); // inserters and extractors template<class charT, class traits> friend basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& os, const philox_engine& x); template<class charT, class traits> friend basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, philox_engine& x); }; }

Mandates:

(6.1)
sizeof...(consts) == n is true, and
(6.2)
n == 2 || n == 4 || n == 8 || n == 16 is true, and
(6.3)
0 < r is true, and
(6.4)
0 < w && w <= numeric_limits<UIntType>::digits is true.

The template parameter pack consts represents the

M_{k}

and

C_{k}

constants which are grouped as follows:

[M_{0}, C_{0}, M_{1}, C_{1}, M_{2}, C_{2}, \dots, M_{n / 2 - 1}, C_{n / 2 - 1}]

The textual representation consists of the values of

K_{0}, \dots, K_{n / 2 - 1}, X_{0}, \dots, X_{n - 1}, i

, in that order.

[Note 2:

The stream extraction operator can reconstruct Y from K and X, as needed.

— end note]

🔗

explicit philox_engine(result_type value);

Effects: Sets the

K_{0}

element of sequence K to

value mod 2^{w}

All elements of sequences X and K (except

K_{0}

) are set to 0.

The value of i is set to

n - 1

🔗

template<class Sseq> explicit philox_engine(Sseq& q);

Effects: With

p = ⌈ w / 32 ⌉

and an array (or equivalent) a of length

(n / 2) \cdot p

, invokes q.generate(a + 0, a + n / 2 * p) and then iteratively for

k = 0, \dots, n / 2 - 1

, sets

K_{k}

(\sum_{j = 0}^{p - 1} a_{k p + j} \cdot 2^{32 j}) mod 2^{w}

All elements of sequence X are set to 0.

The value of i is set to

n - 1

🔗

void set_counter(const array<result_type, n>& c);

Effects: For

j = 0, \dots, n - 1

sets

X_{j}

C_{n - 1 - j} mod 2^{w}

The value of i is set to

n - 1

[Note 3:

The counter is the value Z introduced at the beginning of this subclause.

— end note]

🔗	$f_{n} (j)$		j
🔗			0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
🔗	n	2	0	1
🔗		4	0	3	2	1
🔗		8	2	1	4	7	6	5	0	3
🔗		16	0	9	2	13	6	11	4	15	10	7	12	3	14	5	8	1
🔗