Difference between revisions of "cpp/numeric/random/philox engine"
(Adjusted the widths of table columns.) |
YexuanXiao (Talk | contribs) m |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
{{dcl header|random}} | {{dcl header|random}} | ||
{{dcl|since=c++26| | {{dcl|since=c++26| | ||
− | template< class UIntType, size_t w, size_t n, size_t r, UIntType... consts > | + | template< |
− | class | + | class UIntType, std::size_t w, std::size_t n, std::size_t r, |
+ | UIntType... consts | ||
+ | > | ||
+ | class philox_engine; | ||
}} | }} | ||
{{dcl end}} | {{dcl end}} | ||
Line 27: | Line 30: | ||
===Generator properties=== | ===Generator properties=== | ||
− | In the following description, let {{mathjax-or|\(\scriptsize | + | In the following description, let {{mathjax-or|\(\scriptsize Q_i \)|Q{{su|b=i}}}} denote the {{c|i}}th element of sequence {{c|Q}}, where the subscript starts from zero. |
The {{rlp|/#Random number engines|size}} of the states of {{tt|philox_engine}} is {{mathjax-or|\(\scriptsize O(n)\)|O(n)}}, each of them consists of four parts: | The {{rlp|/#Random number engines|size}} of the states of {{tt|philox_engine}} is {{mathjax-or|\(\scriptsize O(n)\)|O(n)}}, each of them consists of four parts: | ||
− | * A sequence {{c| | + | * A sequence {{c|X}} of {{c|n}} integer values, where each value is in {{range/core|{{c|0}}|{{box|{{math|{{tt|2}}{{su|p={{tt|w}}}}}}}}}}. |
:* This sequence represents a large unsigned integer counter value {{mathjax-or|1=\(\scriptsize Z=\sum_{j=0}^{n-1} X \cdot 2^{wj} \)|2=Z=∑{{su|p=n-1|b=j=0}}X⋅2{{su|p=wj}}}} of {{mathjax-or|\(\scriptsize n \cdot w \)|n⋅w}} bits. | :* This sequence represents a large unsigned integer counter value {{mathjax-or|1=\(\scriptsize Z=\sum_{j=0}^{n-1} X \cdot 2^{wj} \)|2=Z=∑{{su|p=n-1|b=j=0}}X⋅2{{su|p=wj}}}} of {{mathjax-or|\(\scriptsize n \cdot w \)|n⋅w}} bits. | ||
* A sequence {{c|K}} of {{c|n / 2}} keys of type {{tt|UIntType}}. | * A sequence {{c|K}} of {{c|n / 2}} keys of type {{tt|UIntType}}. | ||
Line 139: | Line 142: | ||
{{dsc header|random}} | {{dsc header|random}} | ||
{{dsc hitem|Type|Definition}} | {{dsc hitem|Type|Definition}} | ||
− | {{dsc| | + | {{dsc inc|cpp/numeric/random/dsc philox4x32}} |
− | {{dsc| | + | {{dsc inc|cpp/numeric/random/dsc philox4x64}} |
{{dsc end}} | {{dsc end}} | ||
Line 162: | Line 165: | ||
{{dsc begin}} | {{dsc begin}} | ||
{{dsc h2|Construction and Seeding}} | {{dsc h2|Construction and Seeding}} | ||
− | {{dsc inc|cpp/numeric/random/engine/dsc constructor|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc constructor|philox_engine}} |
− | {{dsc inc|cpp/numeric/random/engine/dsc seed|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc seed|philox_engine}} |
{{dsc inc|cpp/numeric/random/philox_engine/dsc set_counter}} | {{dsc inc|cpp/numeric/random/philox_engine/dsc set_counter}} | ||
{{dsc h2|Generation}} | {{dsc h2|Generation}} | ||
− | {{dsc inc|cpp/numeric/random/engine/dsc operator()|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc operator()|philox_engine}} |
− | {{dsc inc|cpp/numeric/random/engine/dsc discard|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc discard|philox_engine}} |
{{dsc h2|Characteristics}} | {{dsc h2|Characteristics}} | ||
− | {{dsc inc|cpp/numeric/random/engine/dsc min|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc min|philox_engine}} |
− | {{dsc inc|cpp/numeric/random/engine/dsc max|philox_engine | + | {{dsc inc|cpp/numeric/random/engine/dsc max|philox_engine}} |
{{dsc end}} | {{dsc end}} | ||
Latest revision as of 14:44, 30 October 2024
Defined in header <random>
|
||
template< class UIntType, std::size_t w, std::size_t n, std::size_t r, |
(since C++26) | |
std::philox_engine
is a counter-based random number engine.
Contents |
[edit] Template parameters
UIntType | - | The result type generated by the generator. The effect is undefined if this is not one of unsigned short, unsigned int, unsigned long, or unsigned long long. |
w | - | the word size in bits |
n | - | the word count |
r | - | the round count |
consts | - | the sequence of multipliers and round constants used for generating random numbers |
If any of the following values is not true, the program is ill-formed:
- sizeof...(consts) == n
- n == 2 || n == 4 || n == 8 || n == 16
- 0 < r
- 0 < w && w <= std::numeric_limits<UIntType>::digits
[edit] Generator properties
In the following description, let Qi denote the ith element of sequence Q, where the subscript starts from zero.
The size of the states of philox_engine
is O(n), each of them consists of four parts:
- A sequence X of n integer values, where each value is in
[
0,
2
w
)
.
- This sequence represents a large unsigned integer counter value Z=∑n-1j=0X⋅2wj of n⋅w bits.
- A sequence K of n / 2 keys of type
UIntType
. - A buffer Y of n produced values of type
UIntType
. - An index j in Y buffer.
The transition algorithm of philox_engine
(TA(Xi)) is defined as follows:
- Generates a new sequence of n random values (see below) and stores them in Y.
- Increments the counter Z by 1.
- Resets j to 0.
The generation algorithm of philox_engine
is GA(Xi)=Yj.
- ↑ In this case, the next generation algorithm call returns the next generated value in the buffer.
- ↑ In this case, the buffer is refreshed, and the next generation algorithm call returns the first value in the new buffer.
[edit] Generating random values
Random values are generated from the following parameters:
- the number of rounds r
- the current counter sequence X
- the key sequence K
- the multiplier sequence M
- the round constant sequence C
The sequences M and C are formed from the values from template parameter pack consts, which represents the Mk and Ck constants as [
M0,
C0,
M1,
C1,... , ...,
Mn/2-1,
Cn/2-1]
.
Random numbers are generated by the following process:
- Initializes the output sequence S with the elements of X.
- Updates the elements of S for r rounds.
- Replaces the values in the buffer Y with the values in S.
[edit] Updating the output sequence
For each round of update, an intermediate sequence V is initialized with the elements of S in a specified order:
n | V0 | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | V11 | V12 | V13 | V14 | V15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | S0 | S1 | N/A | |||||||||||||
4 | S0 | S3 | S2 | S1 | N/A | |||||||||||
8 | S2 | S1 | S4 | S7 | S6 | S5 | S0 | S3 | N/A | |||||||
16 | S0 | S9 | S2 | S13 | S6 | S11 | S4 | S15 | S10 | S7 | S12 | S3 | S14 | S5 | S8 | S1 |
Given the following operation notations:
- xor, built-in bitwise XOR.
- mullo, it calcuates the low half of modular multiplication and is defined as mullo(a,b,w)=(a⋅b) mod 2w.
- mulhi, it calcuates the high half of multiplication and is defined as mulhi(a,b,w)=⌊(a⋅b)/2w⌋.
Let q be the current round number (starting from zero), for each integer k in [
0,
n / 2)
, the elements of the output sequence S are updated as follows:
- X2⋅k=mullo(V2⋅k+1,Mk,w)
- X2⋅k+1=mulhi(V2⋅k+1,Mk,w) xor ((Kk+q⋅Ck) mod 2w) xor V2⋅k
[edit] Predefined specializations
The following specializations define the random number engine with two commonly used parameter sets:
Defined in header
<random> | |
Type | Definition |
philox4x32 (C++26)
|
std::philox_engine<std::uint_fast32_t, 32, 4, 10, 0xD2511F53, 0x9E3779B9, 0xCD9E8D57, 0xBB67AE85>
|
philox4x64 (C++26)
|
std::philox_engine<std::uint_fast64_t, 64, 4, 10, 0xD2E7470EE14C6C93, 0x9E3779B97F4A7C15, 0xCA5A826395121157, 0xBB67AE8584CAA73B>
|
[edit] Nested types
Type | Definition |
result_type
|
UIntType
|
[edit] Data members
constexpr std::size_t word_size [static] |
w (public static member constant) |
constexpr std::size_t word_count [static] |
n (public static member constant) |
constexpr std::size_t round_count [static] |
r (public static member constant) |
constexpr std::array<result_type, word_count / 2> multipliers [static] |
the multiplier sequence M (public static member constant) |
constexpr std::array<result_type, word_count / 2> round_consts [static] |
the round constant sequence C (public static member constant) |
constexpr std::uint_least32_t default_seed [static] |
20111115u (public static member constant) |
[edit] Member functions
Construction and Seeding | |
constructs the engine (public member function) | |
sets the current state of the engine (public member function) | |
sets the current counter of the engine (public member function) | |
Generation | |
advances the engine's state and returns the generated value (public member function) | |
advances the engine's state by a specified amount (public member function) | |
Characteristics | |
[static] |
gets the smallest possible value in the output range (public static member function) |
[static] |
gets the largest possible value in the output range (public static member function) |
[edit] Non-member functions
(C++26) |
compares the internal states of two pseudo-random number engines (function) |
(C++26) |
performs stream input and output on pseudo-random number engine (function template) |
[edit] Notes
Feature-test macro | Value | Std | Feature |
---|---|---|---|
__cpp_lib_philox_engine |
202406L | (C++26) | std::philox_engine
|
[edit] Example
This section is incomplete Reason: no example |