Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | numeric‎ | random
m (Text replace - "{{tdcl list end" to "{{dcl list end")
(Mathjax update.)
 
(24 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
{{cpp/title|subtract_with_carry_engine}}
 
{{cpp/title|subtract_with_carry_engine}}
−
{{cpp/numeric/random/subtract_with_carry_engine/sidebar}}
+
{{cpp/numeric/random/subtract_with_carry_engine/navbar}}
−
{{ddcl | header=random | notes={{mark since c++11}} | 1=
+
{{dcl begin}}
 +
{{dcl header|random}}
 +
{{dcl|since=c++11|
 
template<
 
template<
−
     class UIntType,  
+
     class UIntType,
−
     size_t w, size_t s, size_t r
+
     std::size_t w, std::size_t s, std::size_t r
 
> class subtract_with_carry_engine;
 
> class subtract_with_carry_engine;
 
}}
 
}}
 +
{{dcl end}}
  
−
{{todo}}
+
Is a random number engine that uses {{enwiki|subtract with carry}} algorithm.
  
−
===Member types===
+
===Template parameters===
−
{{dcl list begin}}
+
{{par begin}}
−
{{tdcl list hitem | Member type | Definition}}
+
{{cpp/numeric/random/param list|UIntType}}
−
{{tdcl list item | {{tt|result_type}} | The integral type generated by the engine.  Results are undefined if this is not an unsigned integral type.}}
+
{{par|w|the word size, in bits, of the state sequence}}
−
{{dcl list end}}
+
{{par|s|the short lag}}
 +
{{par|r|the long lag}}
 +
{{par end}}
  
−
===Member variables===
+
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.
−
{{dcl list begin}}
+
 
−
{{dcl list mem sconst | nolink=true | {{dcl small|constexpr size_t}} word_size | {{todo}} }}
+
===Generator properties===
−
{{dcl list mem sconst | nolink=true | {{dcl small|constexpr size_t}} short_lag | {{todo}} }}
+
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:
−
{{dcl list mem sconst | nolink=true | {{dcl small|constexpr size_t}} long_lag | {{todo}} }}
+
* 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}}}}}}}}}}.
−
{{dcl list mem sconst | nolink=true | {{dcl small|constexpr UIntType}} default_seed | {{todo}} }}
+
* An integer {{c|c}} (known as the ''carry''{{sep}}), whose value is either {{c|0}} or {{c|1}}.
−
{{dcl list end}}
+
 
 +
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}}.
 +
 
 +
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.
 +
 
 +
===Predefined specializations===
 +
The following specializations define the random number engine with two commonly used parameter sets:
 +
{{dsc begin}}
 +
{{dsc header|random}}
 +
{{dsc hitem|Type|Definition}}
 +
{{dsc inc|cpp/numeric/random/dsc ranlux24_base}}
 +
{{dsc inc|cpp/numeric/random/dsc ranlux48_base}}
 +
{{dsc end}}
 +
 
 +
===Nested types===
 +
{{dsc begin}}
 +
{{dsc hitem|Type|Definition}}
 +
{{dsc|{{tt|result_type}}|{{tt|UIntType}}}}
 +
{{dsc end}}
 +
 
 +
===Data members===
 +
{{dsc begin}}
 +
{{dsc mem sconst|nolink=true|{{dsc small|constexpr {{lc|std::size_t}}}} word_size|{{c|w}}}}
 +
{{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}}
  
 
===Member functions===
 
===Member functions===
−
{{dcl list begin}}
+
{{dsc begin}}
−
{{dcl list h2 | Construction and Seeding}}
+
{{dsc h2|Construction and Seeding}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list constructor |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc constructor|subtract_with_carry_engine}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list seed |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc seed|subtract_with_carry_engine}}
  
−
{{dcl list h2 | Generation}}
+
{{dsc h2|Generation}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list operator() |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc operator()|subtract_with_carry_engine}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list discard |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc discard|subtract_with_carry_engine}}
  
−
{{dcl list h2 | Characteristics}}
+
{{dsc h2|Characteristics}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list min |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc min|subtract_with_carry_engine}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list max |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc max|subtract_with_carry_engine}}
−
{{dcl list end}}
+
{{dsc end}}
  
 
===Non-member functions===
 
===Non-member functions===
−
{{dcl list begin}}
+
{{dsc begin}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list operator_cmp |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc operator cmp|subtract_with_carry_engine}}
−
{{dcl list template | cpp/numeric/random/engine/dcl list operator_ltltgtgt |subtract_with_carry_engine}}
+
{{dsc inc|cpp/numeric/random/engine/dsc operator ltltgtgt|subtract_with_carry_engine}}
−
{{dcl list end}}
+
{{dsc end}}
 +
 
 +
===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}}

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"