Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/numeric/random/subtract with carry engine"

From cppreference.com
< cpp‎ | numeric‎ | random
(→‎Member constants: LWG3809 (WIP))
(Mathjax update.)
 
(3 intermediate revisions by one user not shown)
Line 13: Line 13:
 
Is a random number engine that uses {{enwiki|subtract with carry}} algorithm.
 
Is a random number engine that uses {{enwiki|subtract with carry}} algorithm.
  
−
The state of a {{tt|subtract_with_carry_engine}} consists of a sequence {{mathjax-or|\(\small{\{ X_i\}(0 \le i <r)}\)|{X{{su|b=i}}<nowiki/>} (0 ≤ i <r)}}, every {{mathjax-or|\(\small{X_i}\)|X{{su|b=i}}}} is in interval {{mathjax-or|\(\small{[0, 2^w)}\)|[0, 2{{su|p=w}})}}.
+
===Template parameters===
 +
{{par begin}}
 +
{{cpp/numeric/random/param list|UIntType}}
 +
{{par|w|the word size, in bits, of the state sequence}}
 +
{{par|s|the short lag}}
 +
{{par|r|the long lag}}
 +
{{par end}}
 +
 
 +
If {{c|w}} is not in {{range|1|std::numeric_limits<UIntType>::digits|right=]}}, or {{c|s}} is not in {{range|1|r}}, the program is ill-formed.
 +
 
 +
===Generator properties===
 +
The {{rlp|/#Random number engines|size}} of the states of {{tt|subtract_with_carry_engine}} is {{mathjax-or|\(\scriptsize O(r)\)|O(r)}}, each of them consists of two parts:
 +
* A sequence {{c|X}} of {{c|r}} integer values, where each value is in {{range/core|{{c|0}}|{{box|{{math|{{tt|2}}{{su|p={{tt|w}}}}}}}}}}.
 +
* An integer {{c|c}} (known as the ''carry''{{sep}}), whose value is either {{c|0}} or {{c|1}}.
 +
 
 +
Given that {{mathjax-or|\(\scriptsize X_j\)|X{{su|b=j}}}} stands for the {{mathjax-or|\(\scriptsize j\mod r\)|j mod r}}th value (starting from 0) of {{c|X}}, the {{rlp|/#Random number engines|transition algorithm}} of {{tt|subtract_with_carry_engine}} ({{mathjax-or|\(\scriptsize TA(x_i)\)|TA(x{{su|b=i}})}}) is defined as follows:
 +
# Let {{c|Y}} be {{mathjax-or|\(\scriptsize X_{i-s}-X_{i-r}-c\)|X{{su|b=i-s}}-X{{su|b=i-r}}-c}}.
 +
# Let {{c|y}} be {{mathjax-or|\(\scriptsize Y\mod 2^w\)|Y mod 2{{su|p=w}}}}, and set {{mathjax-or|\(\scriptsize X_i\)|X{{su|b=i}}}} to {{c|y}}.
 +
# If {{c|Y}} is negative, set {{c|c}} to {{c|1}}, otherwise set {{c|c}} to {{c|0}}.
  
−
Let all subscripts applied to sequence be taken modulo {{tt|r}}, {{tt|c}} be the carry value which is either {{tt|0}} or {{tt|1}}. The state transition is performed as follows:
+
The {{rlp|/#Random number engines|generation algorithm}} of {{tt|subtract_with_carry_engine}} is {{mathjax-or|1=\(\scriptsize GA(x_i) = y\)|2=GA(x{{su|b=i}}) = y}}, where {{c|y}} is the value produced in step 2 of the transition algorithm.
−
* let {{mathjax-or|1=\(\small{Y=X_{i-s}-X_{i-r}-c}\)|2=Y=X{{su|b=i-s}}-X{{su|b=i-r}}-c}}{{math|Y=X{{su|b=i-s}}-X{{su|b=i-r}}-c}},
+
−
* set {{mathjax-or|\(\small{X_i}\)|X{{su|b=i}}}} to {{mathjax-or|\(\small{Y \mod 2^w}\)|Y mod 2{{su|p=w}}}},
+
−
* set {{tt|c}} to {{tt|1}}, if {{mathjax-or|\(\small{Y<0}\)|Y<0}}, to {{tt|0}} otherwise.
+
  
−
The following typedefs define the random number engine with two commonly used parameter sets:
+
===Predefined specializations===
 +
The following specializations define the random number engine with two commonly used parameter sets:
 
{{dsc begin}}
 
{{dsc begin}}
 
{{dsc header|random}}
 
{{dsc header|random}}
Line 28: Line 44:
 
{{dsc end}}
 
{{dsc end}}
  
−
===Template parameters===
+
===Nested types===
−
{{par begin}}
+
{{dsc begin}}
−
{{cpp/numeric/random/param_list|UIntType}}
+
{{dsc hitem|Type|Definition}}
−
{{par|w|The word size, in bits, of the state sequence, {{c|1= 10 < w <= std::numeric_limits<UIntType>::digits}}.}}
+
{{dsc|{{tt|result_type}}|{{tt|UIntType}}}}
−
{{par|s|The ''short lag''.}}
+
{{dsc end}}
−
{{par|r|The ''long lag'', where {{c|0 < s < r}}.}}
+
−
{{par end}}
+
  
−
===Member types===
+
===Data members===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc hitem|Member type|Definition}}
+
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} word_size|{{c|w}}}}
−
{{dsc|{{tt|result_type}} {{mark c++11}}|The integral type generated by the engine. Results are undefined if this is not an unsigned integral type.}}
+
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} short_lag|{{c|s}}}}
 +
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} long_lag|{{c|r}}}}
 +
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::uint_least32_t}}}} default_seed|{{c|19780503u}}}}
 
{{dsc end}}
 
{{dsc end}}
  
Line 59: Line 75:
 
===Non-member functions===
 
===Non-member functions===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc|cpp/numeric/random/engine/dsc operator_cmp|subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc operator cmp|subtract_with_carry_engine}}
−
{{dsc inc|cpp/numeric/random/engine/dsc operator_ltltgtgt|subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc operator ltltgtgt|subtract_with_carry_engine}}
−
{{dsc end}}
+
−
 
+
−
===Member constants===
+
−
{{dsc begin}}
+
−
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} word_size|notes={{mark c++11}}|template parameter {{tt|w}}, the word size}}
+
−
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} short_lag|notes={{mark c++11}}|template parameter {{tt|s}}, the short lag}}
+
−
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} long_lag|notes={{mark c++11}}|template parameter {{tt|r}}, the long lag}}
+
−
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::uint_least32_t}}}} default_seed|notes={{mark c++11}}|constant value {{c|19780503u}}}}
+
 
{{dsc end}}
 
{{dsc end}}
  
 
===Example===
 
===Example===
 
{{example}}
 
{{example}}
 +
 +
===Defect reports===
 +
{{dr list begin}}
 +
{{dr list item|wg=lwg|dr=3809|std=C++11|before={{tt|default_seed}} might not be<br>representable with {{tt|result_type}}|after=changed its type to<br>{{lc|std::uint_least32_t}}}}
 +
{{dr list end}}
  
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Latest revision as of 00:32, 19 August 2024

 
C++
 
Numerics library
Common mathematical functions
Mathematical special functions (C++17)
Mathematical constants (C++20)
Basic linear algebra algorithms (C++26)
Floating-point environment (C++11)
Complex numbers
Numeric array (valarray)
Pseudo-random number generation
Factor operations
(C++17)
(C++17)
Interpolations
(C++20)
(C++20)
Saturation arithmetic
(C++26)
(C++26)
(C++26)
(C++26)
(C++26)

Generic numeric operations
Bit operations
(C++20)    
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++23)
(C++20)
 
Pseudo-random number generation
 
std::subtract_with_carry_engine
 
Defined in header <random>
template<

    class UIntType,
    std::size_t w, std::size_t s, std::size_t r

> class subtract_with_carry_engine;
 (since C++11)

Is a random number engine that uses subtract with carry algorithm.

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, of the state sequence
s - the short lag
r - the long lag

If w is not in [1, std::numeric_limits<UIntType>::digits], or s is not in [1, r), the program is ill-formed.

[edit] Generator properties

The size of the states of subtract_with_carry_engine is O(r), each of them consists of two parts:

  • A sequence X of r integer values, where each value is in [​0​, 2w).
  • An integer c (known as the carry ), whose value is either ​0​ or 1.

Given that Xj stands for the j mod rth value (starting from 0) of X, the transition algorithm of subtract_with_carry_engine (TA(xi)) is defined as follows:

  1. Let Y be Xi-s-Xi-r-c.
  2. Let y be Y mod 2w, and set Xi to y.
  3. If Y is negative, set c to 1, otherwise set c to ​0​.

The generation algorithm of subtract_with_carry_engine is GA(xi) = y, where y is the value produced in step 2 of the transition algorithm.

[edit] Predefined specializations

The following specializations define the random number engine with two commonly used parameter sets:

Defined in header <random>
Type Definition
ranlux24_base (C++11) std::subtract_with_carry_engine<std::uint_fast32_t, 24, 10, 24>[edit]
ranlux48_base (C++11) std::subtract_with_carry_engine<std::uint_fast64_t, 48, 5, 12>[edit]

[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 short_lag
[static]
 s
(public static member constant)
constexpr std::size_t long_lag
[static]
 r
(public static member constant)
constexpr std::uint_least32_t default_seed
[static]
 19780503u
(public static member constant)

[edit] Member functions

Construction and Seeding
constructs the engine
(public member function) [edit]
sets the current state of the engine
(public member function) [edit]
Generation
advances the engine's state and returns the generated value
(public member function) [edit]
advances the engine's state by a specified amount
(public member function) [edit]
Characteristics
[static]
 gets the smallest possible value in the output range
(public static member function) [edit]
[static]
 gets the largest possible value in the output range
(public static member function) [edit]

[edit] Non-member functions

(C++11)(C++11)(removed in C++20)
 compares the internal states of two pseudo-random number engines
(function) [edit]
(C++11)
 performs stream input and output on pseudo-random number engine
(function template) [edit]

[edit] Example

This section is incomplete
Reason: no example

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 3809 C++11 default_seed might not be
representable with result_type 		changed its type to
std::uint_least32_t
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/numeric/random/subtract_with_carry_engine&oldid=175313"