1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Random123-1.09: Counter Based RNGs (CBRNGs).</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javaScript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body onload='searchBox.OnSelectItem(0);'>
<div class="tabs"><ul class="tablist"><li style="padding-left: 1.5em; font-weight: bold">Random123-1.09 Documentation</li></ul></div>
<!-- Generated by Doxygen 1.7.1 -->
<script type="text/javascript"><!--
var searchBox = new SearchBox("searchBox", "search",false,'Search');
--></script>
<div class="navigation" id="top">
<div class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li id="searchli">
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
</div>
<div class="header">
<div class="headertitle">
<h1>Counter Based RNGs (CBRNGs). </h1> </div>
</div>
<div class="contents">
<p>The counter-based random number generators (CBRNGs) in the Random123 library are described in more detail in <a href="http://dl.acm.org/citation.cfm?doid=2063405"><em>Parallel Random Numbers: As Easy as 1, 2, 3</em> </a>, which was named the Best Paper at the ACM SC'11 International Conference on High Performance Computing, Networking, Storage, and Analysis. All the CBRNGs in the library conform to a consistent interface. Basically: </p>
<div class="fragment"><pre class="fragment">
value = CBRNGname(counter, key)
</pre></div><p>Thus, with some care, they can be used interchangeably in applications. (Since code compiled with AES-NI instructions will result in an illegal instruction exception on processors without those instructions, Random123 provides a <a class="el" href="sse_8h.html#a0b35a046e85316295476d7d552411044">haveAESNI</a> function that can be used to detect the existence of AES at run-time; user code could use it to either report an error or substitute an alternative compatible CBRNG.)</p>
<p>The API descriptions below are generic, but apply to all the different <a class="el" href="index.html#families">families</a> of Random123 CBRNGs.</p>
<h2><a class="anchor" id="arrays"></a>
Fixed-size Array Types</h2>
<p>Data is passed into and back from the Random123 functions as <a class="el" href="group__arrayNxW.html">r123arrayNxW</a> types; these types contain fixed-size arrays of W-bit types (<code>uintW_t</code> for the most part, but also a special <a class="el" href="structr123m128i.html">r123m128i</a> wrapper for the <a class="el" href="group__AESNI.html">ARS and AESNI</a> CBRNGs). The counter argument and the return value have the same type, referred to as <code>ctr_type</code> in C++, and <code>ctr_t</code> in C. The type of the key argument is referred to as <code>key_type</code> in C++, and <code>key_t</code> in C. For an <a class="el" href="group__arrayNxW.html">r123arrayNxW</a>, <code>r</code>, the data member <code>r.v</code> is an array of N elements, each of width W (each element is type <code>uintW_t</code> or an <a class="el" href="structr123m128i.html">r123m128i</a> wrapper object). C programs can access these elements as <code>r.v</code>[0], ... <code>r.v</code>[N-1] for the <code>uintW_t</code> types.</p>
<p>In C++, these array types closely resemble the C++0x std::array<N, uintW_t> template, but do not require C++0x libraries or compiler features. C++ programs can access array elements via operator[] <code>r</code>[0], ... <code>r</code>[N-1], or via most of the capabilities of a C++ "Container" e.g. <code>at()</code>, <code>begin()</code>, <code>end()</code>, <code>size()</code> and others. In addition, containers have <code> incr() </code> and <code> incr(unsigned long long)</code> member function that do increment-with-carry, which facilitate using r123arrays as very-long-period counters.</p>
<p>If the compiler environment supports it, <code><a class="el" href="array_8h.html">Random123/array.h</a></code> also declares <code><a class="el" href="structr123array1xm128i.html">r123array1xm128i</a></code>, which contains an array of one <code><a class="el" href="structr123m128i.html">r123m128i</a></code>, which in turn is a class wrapping a single element of <code>__m128i</code> SSE type, which can be accessed as <code>r.v</code>[0].m. The <a class="el" href="structr123_1_1ARS1xm128i__R.html">r123::ARS1xm128i_R</a> RNGs use <code><a class="el" href="structr123array1xm128i.html">r123array1xm128i</a></code> for both <code>ctr_type</code> and <code>key_type</code>. For the <a class="el" href="group__AESNI.html">AESNI</a> RNG, <code>ctr_type</code> is an <code><a class="el" href="structr123array1xm128i.html">r123array1xm128i</a></code>, but <code>key_type</code> is an opaque type, which must be initialized by assignment from a <code>userkey_type</code> (an <a class="el" href="structr123array1xm128i.html">r123array1xm128i</a>).</p>
<h2><a class="anchor" id="aliasing"></a>
A note on aliasing and type-punning</h2>
<p>It is easiest (though not necessarily fastest) to choose a CBRNG whose <code>ctr_type</code> matches the width of the random data needed by the application, e.g., Philox4x32 for applications that need random data in 32-bit words. If the application's needs don't match the counter's value_type, it is tempting to use "type punning" and pointer casts to interconvert between types. Such conversions require great care and are very difficult to do safely without use of unions or memcpy. See <a href="http://blog.worldofcoding.com/2010/02/solving-gcc-44-strict-aliasing-problems.html">here</a> and <a href="http://dbp-consulting.com/tutorials/StrictAliasing.html">here</a> for discussions of the pitfalls related to aliasing. The C++ <a class="el" href="structr123_1_1ReinterpretCtr.html">r123::ReinterpretCtr</a> template is a safe way to reinterpret <code>CBRNG</code> counter types. Gcc's <code>-Wstrict-aliasing=2</code> warning level will warn if strict aliasing violations are detected. If you find yourself ignoring or disabling warnings about strict aliasing, you should strongly consider adding something like gcc's <code>-fnostrict-aliasing</code> option to your compiler flags.</p>
<h2><a class="anchor" id="cxxapi"></a>
C++ API</h2>
<p>There are four families of CBRNGs in the library: </p>
<ul>
<li>
<a class="el" href="group__ThreefryNxW.html">Threefry</a>: <a class="el" href="group__ThreefryNxW.html#ga1c32939b65f84966c93677f4382ea36d">r123::Threefry2x32</a>, <a class="el" href="group__ThreefryNxW.html#gacb09a2dcfb7389769f0c58f45f132aaa">r123::Threefry4x32</a>, <a class="el" href="group__ThreefryNxW.html#ga2b54dd1b0d20f09239be5f8757f1f3db">r123::Threefry2x64</a>, <a class="el" href="group__ThreefryNxW.html#gae17c98bddf067365508ed0717f865e8b">r123::Threefry4x64</a> </li>
<li>
<a class="el" href="group__PhiloxNxW.html">Philox</a>: <a class="el" href="group__PhiloxNxW.html#ga81659a3ee5a1ca9e2e85c5d725a1ea4f">r123::Philox2x32</a>, <a class="el" href="group__PhiloxNxW.html#gaafd54060af05012db410034e3c0ecdc4">r123::Philox4x32</a>, <a class="el" href="group__PhiloxNxW.html#ga616a669079ac25119353416c14d46426">r123::Philox2x64</a>, <a class="el" href="group__PhiloxNxW.html#ga7776f4d481b7c0ac00db70272a1c77f0">r123::Philox4x64</a> </li>
<li>
<a class="el" href="structr123_1_1AESNI4x32.html">r123::AESNI4x32</a>, <a class="el" href="structr123_1_1AESNI1xm128i.html">r123::AESNI1xm128i</a> </li>
<li>
<a class="el" href="structr123_1_1ARS4x32__R.html">r123::ARS4x32_R</a> </li>
</ul>
<p>A <em> counter based RNG </em> (CBRNG) with a name of the form <em>FamilynameN</em>x<em>W</em> is a type G with the three member typedefs:</p>
<ul>
<li>
G::ctr_type, which is an <a class="el" href="group__arrayNxW.html">r123arrayNxW</a> container class. </li>
<li>
G::ukey_type, which is an <a class="el" href="group__arrayNxW.html">r123arrayMxV</a> container class. Note that the width, <code>MxV</code> of the key may not be the same as the width <code>NxW</code> of the ctr_type (<a class="el" href="group__PhiloxNxW.html">Philox</a> keys are half as wide as the counter, and future CBRNGs may well have different widths). </li>
<li>
G::key_type, which in most cases is identical to G::ukey_type, but is different for the <a class="el" href="group__AESNI.html">AESNI</a> types. In all cases, there is a G::key_type(G::ukey_type) constructor and a G::key_type assignment operator for a G::ukey_type right-hand-side. In general, one can always write: <div class="fragment"><pre class="fragment"> G::ukey_type uk1, uk2;
<span class="comment">// user code initializes uk1 and uk2</span>
G::key_type k1(uk1), k2;
k2 = uk2;
</pre></div> </li>
</ul>
<p>For most CBRNG's, i.e., any one not in the <a class="el" href="group__AESNI.html">AESNI</a> family, it is also perfectly acceptable to set the elements of a G::key_type directly from application variables. The quality of the results will not be compromised by using highly correlated or "non-random" keys.</p>
<p>A value <code>g</code> of type <code>G</code> can be invoked as <code>g(c,k)</code>, where <code>c</code> is a value of type <code>G::ctr_type</code> and <code>k</code> is a value of type <code>G::key_type</code>, and <code>g(c,k)</code> returns a value of type <code>G::ctr_type</code>.</p>
<ul>
<li>
g() is a stateless, pure function. That is, g(c,k) may be called any number of times in any context and always returns the same result for the same inputs. In particular, c1==c2 and k1==k2 implies that g(c1,k1) == g(c2,k2). </li>
<li>
For constant k, g(*,k) is a bijection. That is, g(c1,k) == g(c2,k) if and only if c1 == c2. </li>
<li>
g "randomizes" its inputs. That is, for most sequences of inputs (c1,k1), (c2, k2), ... (including those obtained by following highly regular patterns of incrementing and striding through the counter and user key spaces) the output sequence, g(c1, k1), g(c2, k2), ... looks like a a sequence of uniformly distributed random variables drawn from the set of all ctr_types. </li>
</ul>
<p>All the CBRNGs in the library work by iterating a randomization function for a specific number of <em>rounds</em>. Too few rounds and the CBRNG is a poor (perhaps catastrophically poor) random number generator. Too many rounds and time is wasted with little or no improvement in the randomness of the output. Each of the CBRNGs has a specific number of rounds which the authors believe is a reasonable compromise between speed and quality. In all cases, the default number of rounds includes a margin of safety above the minimum number of rounds that have passed all of the SmallCrush, Crush and BigCrush tests in the <a href="http://www.iro.umontreal.ca/~simardr/testu01/tu01.html">TestU01</a> suite.</p>
<p>Users may, however wish to employ a different numbers of rounds. Each of the above classes is actually a typedef of a more general class with a template parameter that specifies the number of rounds as <em>name</em>_rounds. The template classes all end in <code>_R:</code> </p>
<ul>
<li>
<a class="el" href="group__ThreefryNxW.html">Threefry</a>: <a class="el" href="structr123_1_1Threefry2x32__R.html">r123::Threefry2x32_R</a>, <a class="el" href="structr123_1_1Threefry4x32__R.html">r123::Threefry4x32_R</a>, <a class="el" href="structr123_1_1Threefry2x64__R.html">r123::Threefry2x64_R</a>, <a class="el" href="structr123_1_1Threefry4x64__R.html">r123::Threefry4x64_R</a> </li>
<li>
<a class="el" href="group__PhiloxNxW.html">Philox</a>: <a class="el" href="structr123_1_1Philox2x32__R.html">r123::Philox2x32_R</a>, <a class="el" href="structr123_1_1Philox4x32__R.html">r123::Philox4x32_R</a>, <a class="el" href="structr123_1_1Philox2x64__R.html">r123::Philox2x64_R</a>, <a class="el" href="structr123_1_1Philox4x64__R.html">r123::Philox4x64_R</a> </li>
<li>
<a class="el" href="structr123_1_1AESNI4x32__R.html">r123::AESNI4x32_R</a>, <a class="el" href="structr123_1_1AESNI1xm128i__R.html">r123::AESNI1xm128i_R</a> </li>
<li>
<a class="el" href="structr123_1_1ARS4x32__R.html">r123::ARS4x32_R</a> </li>
</ul>
<h2><a class="anchor" id="capi"></a>
C API</h2>
<p>A subset of the C++ interface is also directly usable by C programs. All header files may be safely included in C files. The C API to each of the supported RNGs consists of two typedefs, <em>name</em>_ctr_t, <em>name</em>_key_t, two functions <em>name</em>() and <em>name</em>_R(), and the enum <em>name</em>_rounds which specifies the recommended number of rounds. </p>
<ul>
<li>
<em>name</em>(c, k), performs the recommended number of rounds of the <em>name</em> CBRNG. </li>
<li>
<em>name_R</em>(R,c,k), performs an R-round version of the <em>name</em> CBRNG. <em>name</em>(c,k) is equivalent to <em>name</em>_R(<em>name</em>_rounds, c, k). </li>
</ul>
<p>The <code>_R</code> functions are designed and implemented so that an optimizing compiler can achieve good performance when the number of rounds is a compile-time constant. It is likely that <code>philox4x32_R(10,c,k) </code> will perform much better than <code>philox4x32_R(r,c,k)</code> if <code>r</code> cannot be evaluated at compile-time.</p>
<p>The supported names for the C API are </p>
<ul>
<li>
<a class="el" href="group__ThreefryNxW.html">threefry</a>: <a class="el" href="threefry_8h.html#af98f648fb8e458ff0c6825cb903734f2">threefry2x32</a>, <a class="el" href="threefry_8h.html#a1636cce9de54f919e8952a42b7f397fd">threefry4x32</a>, <a class="el" href="threefry_8h.html#aea6a4bd5c80354a4f575c9bec2702172">threefry2x64</a>, <a class="el" href="threefry_8h.html#a382d18a49002d2a5e2b2f06d58669d70">threefry4x64</a>. </li>
<li>
<a class="el" href="group__PhiloxNxW.html">philox</a>: <a class="el" href="philox_8h.html#ab2496424917f063a4990f01943a07fe0">philox2x32</a>, <a class="el" href="philox_8h.html#a432a3df828dd51acd0b7ec2fee1d4d7e">philox4x32</a>, <a class="el" href="philox_8h.html#ae6b57a71e4efa369cc19416fc088b5a5">philox2x64</a>, <a class="el" href="philox_8h.html#a62fb1b4d9775396303ebb2a801fea8e6">philox4x64</a>. </li>
<li>
<a class="el" href="group__AESNI.html#gab13b093252d4bb3389d27d4e3b04dae8">ars4x32_R</a>, <a class="el" href="group__AESNI.html#gaddc6efc2007f6f66ee914eb7074cff1e">ars1xm128i_R</a> </li>
<li>
<a class="el" href="group__AESNI.html#gae3950c524818b49d1cdfad481880a33a">aesni4x32</a>, <a class="el" href="group__AESNI.html#ga3ba5daca2d4d076ece24900084e71311">aesni1xm128i</a> </li>
</ul>
</div>
<!--- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark"> </span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark"> </span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark"> </span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark"> </span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark"> </span>Defines</a></div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<hr class="footer"/><address class="footer"><small>Generated on Mon Mar 7 2016 18:34:00 for Random123-1.09 by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.1 </small></address>
</body>
</html>
|
