Topic: D0205R1 -- Final draft for "Allow Seeding Random
Author: Moritz Klammler <moritz.klammler@gmail.com>
Date: Wed, 10 Feb 2016 19:09:42 +0100
Raw View
--=-=-=
Content-Type: text/plain; charset=UTF-8
Attached is my final draft for the proposal. My plans are to formally
submit it tomorrow. Until then, I can still apply last-minute fixes but
given how little time is left, I know that this is unrealistic.
There is also an implementation of the proposal available now:
http://klammler.eu/data/computer-science/iso-c++/p0205/
Thank you to all who have provided feedback so far.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
--=-=-=
Content-Type: text/html; charset=utf-8
Content-Disposition: attachment; filename=d0205r1.html
Content-Transfer-Encoding: quoted-printable
Content-Description: D0205R1
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org=
/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns=3D"http://www.w3.org/1999/xhtml" xml:lang=3D"en" lang=3D"en">
<head>
<title>D0205R1 — Allow Seeding Random Number Engines with std::ra=
ndom_device</title>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3DUTF-8=
" />
<meta name=3D"description"
content=3D"The purpose of this proposal is to make properly seedi=
ng a random number engine in a
non-deterministic way easy and fast.
In order to achieve this, the following changes are prop=
osed:
- Introduction of a new concept *seed generator*, which=
is a relaxation of *seed sequence*
(=C2=A7 26.5.1.2 [rand.req.seedseq]).
- Addition of a member function `generate` to `std::ran=
dom_device` in order to make it model the new
concept.
The changes are non-breaking and can be implemented as a=
pure library solution with current C++14
features." />
<meta name=3D"keywords"
content=3D"ISO, C++, C++14, C++17, random, seed, random number en=
gine, RNG, PRNG, std::seed_seq,
std::random_device, entropy, Moritz Klammler" />
<style type=3D"text/css">
/* <![CDATA[ */
body {
font-family: serif;
font-size: 12pt;
margin: 2em;
}
p {
text-align: justify;
}
pre, code {
font-family: monospace;
font-size: inherit;
/* color: #5c3566; */
}
pre .comment {
font-style: italic;
}
blockquote {
margin-left: 2em;
padding: 0.2ex 1em 0.3ex 1em;
background-color: #eeeeec;
border-left: 5px solid #babdb6;
}
ol.toc {
list-style: none;
margin-left: 2em;
padding: 0;
}
ol.toc li {
}
/* ]]> */
</style>
<script type=3D"text/javascript">
/* <![CDATA[ */
function replace_email() {
var node =3D document.getElementById('email');
var email =3D node.innerHTML.replace(/\\x2E/g, '\x2E').replace(/\\x=
40/g, '\x40');
node.innerHTML =3D email;
node.href =3D 'mailto:' + email;
}
/* ]]> */
</script>
</head>
<body onload=3D"replace_email()">
<h1>Allow Seeding Random Number Engines with <code>std::random_device</=
code></h1>
<table border=3D"0" cellspacing=3D"0" cellpadding=3D"5">
<tr>
<td>Document number:</td>
<td>D0205R1</td>
</tr>
<tr>
<td>Date:</td>
<td>2016-02-10</td>
</tr>
<tr>
<td>Project:</td>
<td>Programming Language C++</td>
</tr>
<tr>
<td>Audience:</td>
<td>Study Group 6 (Numerics), Library Evolution Working Group, Libr=
ary Working Group</td>
</tr>
<tr>
<td>Reply-to:</td>
<td>
Moritz Klammler
<<code><a id=3D"email">moritz\x2Eklammler\x40gmail\x2Ecom</a><=
/code>>
(OpenPGP: <code>2732 DA32 C8D0 EEEC A081 BE9D CF6C 5166 F393 A9C0=
</code>)
</td>
</tr>
</table>
<h2 id=3D"sec-toc">Table of Contents</h2>
<ol class=3D"toc">
<li><a href=3D"#sec-intro">1. Introduction</a></li>
<li>
<a href=3D"#sec-motivation-scope">2. Motivation and Scope</a>
<ol class=3D"toc">
<li><a href=3D"#sec-background">2.1 Background</a></li>
<li><a href=3D"#sec-current-problem">2.2 The Problem with the Cur=
rent Standard Library</a></li>
<li><a href=3D"#sec-proposed-solution">2.3 The Proposed Solution<=
/a></li>
</ol>
</li>
<li>
<a href=3D"#sec-impact-std">3. Impact on the Standard</a>
<ol class=3D"toc">
<li><a href=3D"#sec-rand-req-eng">3.1 Clarification on Random Num=
ber Engine Requirements</a></li>
<li><a href=3D"#sec-deprecation">3.2 Deprecation of Existing Feat=
ures</a></li>
</ol>
</li>
<li>
<a href=3D"#sec-design-decisions">4. Design Decisions</a>
<ol class=3D"toc">
<li>
<a href=3D"#sec-alt-solutions">4.1 Alternative Solutions</a>
<ol class=3D"toc">
<li><a href=3D"#sec-alt-adapter">4.1.1 Provide a Generic Adap=
ter Type instead of Modifying <code>std::random_device</code></a></li>
<li><a href=3D"#sec-int-types">4.1.2 Integer Types</a></li>
</ol>
</li>
<li><a href=3D"#sec-shortcomings">4.2 Shortcomings</a></li>
<li><a href=3D"#sec-impact-stdlib-impl">4.3 Impact on Standard Li=
brary Implementations</a></li>
<li><a href=3D"#sec-implementations">4.4 Implementations</a></li>
</ol>
</li>
<li><a href=3D"#sec-prop-word">5. Proposed Wording</a></li>
<li><a href=3D"#sec-acknowledgments">Acknowledgments</a></li>
<li><a href=3D"#sec-references">References</a></li>
</ol>
<h2 id=3D"sec-intro">1. Introduction</h2>
<p>
The purpose of this proposal is to make properly seeding a random num=
ber engine in a non-deterministic way easy
and fast.
</p>
<p>
In order to achieve this, the following changes are proposed:
</p>
<ul>
<li>
<p>
Introduction of a new concept <em>seed generator</em>, which is a=
relaxation of <em>seed sequence</em>
(=C2=A7 26.5.1.2 [rand.req.seedseq]).
</p>
</li>
<li>
<p>
Addition of a member function <code>generate</code> to
<code>std::random_device</code> in order to make it model the new=
concept.
</p>
</li>
</ul>
<p>
The changes are non-breaking and can be implemented as a pure library=
solution with current C++14 features.
</p>
<h2 id=3D"sec-motivation-scope">2. Motivation and Scope</h2>
<h3 id=3D"sec-background">2.1 Background</h3>
<p>
C++11 introduced a powerful random number generation library (=C2=A7&=
nbsp;26.5 [rand]) under
the <code><random></code> header. It provides <em>random numbe=
r engines</em> (=C2=A7 26.5.1.4
[rand.req.eng]) that can be used either directly as a source of unifo=
rmly distributed pseudo random integers of
unsigned type or together with <em>random number distributions</em> (=
=C2=A7 26.5.1.6 [rand.req.dist]) to produce
pseudo random numbers according to a variety of distributions.
</p>
<p>
If an engine has an internal state of <var>N</var> bits, it can produ=
ce at most 2<sup><var>N</var></sup> different
sequences and the longest sequence it can produce will have a period =
of at most 2<sup><var>N</var></sup> values
until it necessarily starts repeating itself. Applications that wish=
to produce high-quality pseudo random
numbers will therefore choose an engine such as the Mersenne twister =
with a large internal state. Choosing an
engine with a large internal state helps ensuring that the period of =
the generated sequence will be large.
However, in order to ensure that the number of different sequences th=
e engine can produce is also exponential in
the size of its state, it has to be made sure that the initial state =
is evenly distributed across all possible
states. This is done by <em>seeding</em> the random number engine. =
If each of the 2<sup><var>N</var></sup>
states should be chosen with equal probability as the initial state, =
seeding requires 2<sup><var>N</var></sup>
bits of entropy.
</p>
<p>
The standard library provides the type <code>std::random_device</code=
> (=C2=A7 26.5.6 [rand.device]),
a <em>uniform random number generator</em> (=C2=A7 26.5.1.3 [ran=
d.req.urng]) that is supposed (but, unfortunately,
not required) to produce a non-deterministic sequence of uniformly di=
stributed integers of type
<code>unsigned int</code>. The natural choice for an application tha=
t wishes to generate pseudo random numbers
and does not need (and often doesn't want) reproducibility is to use =
it for seeding a random engine that is then
used to produce pseudo random numbers.
</p>
<h3 id=3D"sec-current-problem">2.2 The Problem with the Current Standar=
d Library</h3>
<p>
Unfortunately, the current standard library does not provide any conv=
enient way to use
a <code>std::random_device</code> to properly (in the sense that each=
initial state is equally likely) seed a
random engine.
</p>
<p>
The naïve approach that most people seem to use is the following.
</p>
<pre>template <typename EngineT>
<span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_1st(EngineT& engine)
{
std::random_device rnddev {};
engine.seed(rnddev());
}</pre>
<p>
This code is severely flawed. If <code>EngineT</code> is <code>std::=
mt19937</code>, it has a state size of
19 968 bits. However, if an <code>unsigned int</code> is=
32 bits (as is the common case on many
platforms today), then of the up to 2<sup>19 968</sup> states,=
at most 2<sup>32</sup> (that is one
2<sup>−19 936</sup>-th) can possibly be chosen!
</p>
<p>
To illustrate that this is in fact a real problem, O'Neill [<a h=
ref=3D"#ref-01">1</a>] has pointed out that a
<code>std::mt19937</code> engine seeded like above can never produce =
certain integers as its first value. This
can have bad consequences on real-world programs. A program that inc=
orrectly assumes that an impossible number
will eventually be produced as the engine's first (or <var>n</var>-th=
) output is broken in a very subtle way.
After all, it would take extensive and practically unrealistic unit t=
esting to do an exhaustive search over the
possible seeds and even detect the bug.
</p>
<p>
In addition to seeding an engine with an integer, the standard librar=
y also provides a way to seed it with a
so-called <em>seed sequence</em> (=C2=A7 26.5.1.2 [rand.req.seed=
seq]). A seed sequence may be constructed in a
deterministic way from zero or more integers that provide some initia=
l entropy. The numbers are then possibly
scrambled and stored in some internal state of the seed sequence whic=
h can be externalized using
the <code>param</code> member function. Such a memento may then be u=
sed to re-create a seed sequence of the same
type in the same state. A seed sequence provides a member function <=
code>generate</code> that takes a pair of
random access iterators and assigns a uniformly distributed unsigned =
32 bit integer to each element in the range
denoted by the iterator pair. The standard library provides a single=
implementation of a seed sequence in
<code>std::seed_seq</code> (=C2=A7 26.5.7.1 [rand.util.seedseq])=
.. This type can be used to seed a random engine
more thoroughly.
</p>
<pre>template <typename EngineT, std::size_t StateSize =3D EngineT::=
state_size>
<span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_2nd(EngineT& engine)
{
using engine_type =3D typename EngineT::result_type;
using device_type =3D std::random_device::result_type;
using seedseq_type =3D std::seed_seq::result_type;
constexpr auto bytes_needed =3D StateSize * sizeof(engine_type);
constexpr auto numbers_needed =3D (sizeof(device_type) < sizeof(seedse=
q_type))
? (bytes_needed / sizeof(device_type))
: (bytes_needed / sizeof(seedseq_type));
std::array<device_type, numbers_needed> numbers {};
std::random_device rnddev {};
std::generate(std::begin(numbers), std::end(numbers), std::ref(rnddev));
std::seed_seq seedseq(std::cbegin(numbers), std::cend(numbers));
engine.seed(seedseq);
}</pre>
<p>
This code has a number of problems.
</p>
<ul>
<li>
<p>
It is absurdly complicated for what could rightfully be expected =
to be a simple task. (Even the author is not
absolutely sure it is correct.) It is unrealistic (and unreasona=
ble) to expect a casual user to come up with
such a seeding procedure.
</p>
</li>
<li>
<p>
It is not as general as one might hope it is. The <em>random num=
ber engine</em> concept does not require that
an engine exposes its <code>state_size</code> as
<code>std::mersenne_twister_engine</code> does. (The author beli=
eves that making this constant part of the
requirements would have been a good idea but it is too late for t=
his now.) This forces the user of the
function to look up the actual state size in the documentation an=
d provide the correct value as the
second <code>template</code> parameter. (One could write type tr=
aits for the engines provided by the standard
library and fall back to <code>sizeof</code> as a reasonable esti=
mate for third-party types, faithfully
assuming they won't allocate memory to hold state on the free sto=
re.)
</p>
</li>
<li>
<p>
It is not as accurate as it should be. Assuming that <code>std::=
random_device</code> produces truly
independent uniform random numbers, <code>std::seed_seq</code> ac=
tually
<em>introduces</em> non-uniformity [<a href=3D"#ref-01">1</a=
>]. (O'Neill provides experimental evidence for
this. Anyway, it is clear that a deterministic algorithm can onl=
y ever reduce but never increase the entropy
of a given seed.)
</p>
</li>
<li>
<p>
It is not as efficient as it could be. While all that's really n=
eeded is copying a sequence of random bytes
into the internal state of the engine, the <code>std::random_devi=
ce</code> first copies them into a
stack-based <code>std::array</code> from which the <code>std::see=
d_seq</code> copies them into a heap
allocated (!) internal buffer, scrambles them in a (in this case=
counter-productive) attempt to remove bias
until the engine finally copies them to their final destination. =
To make matters worse, the
<code>std::random_device</code> does not know in advance how many=
bytes will be needed. Therefore, on
implementations where it reads from a file such as <code>/dev/ura=
ndom</code>, it cannot buffer the reads
efficiently.
</p>
</li>
</ul>
<h3 id=3D"sec-proposed-solution">2.3 The Proposed Solution</h3>
<p>
With this proposal adopted, properly seeding a random engine could be=
as simple as this.
</p>
<pre>template <typename EngineT>
<span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_3rd(EngineT& engine)
{
std::random_device rnddev {};
engine.seed(rnddev); <span class=3D"comment">// note: passing rnddev its=
elf as opposed to the</span>
<span class=3D"comment">// result of invoking its c=
all operator</span>
}</pre>
<p>
This would be made possible by adding a <code>generate</code> member =
function to
<code>std::random_device</code> directly and relaxing the type requir=
ements on the argument to
the <code>seed</code> member function to only require that <code>gene=
rate</code> member function.
</p>
<p>
There would be no unnecessary copies, no unneeded tempering, no dynam=
ic memory allocation, no introduced bias and
little chance to get anything wrong on the user's side.
</p>
<h2 id=3D"sec-impact-std">3. Impact on the Standard</h2>
<p>
This proposal could be implemented with very little changes, none of =
which would be breaking anything. No core
language changes are needed.
</p>
<p>
The requirements on the type parameter for a random engine's <code>se=
ed</code> member function (and the
corresponding constructor) should be relaxed such that it only requir=
es the <code>generate</code> member function
from <em>seed sequence</em>. Bolas [<a href=3D"#ref-02">2</a>] =
has argued that even today, a conforming
implementation isn't allowed to <em>call</em> anything but <code>gene=
rate</code> and perhaps <code>size</code> due
to existing complexity requirements. Unfortunately, it may still enf=
orce their presence via type checks.
</p>
<p>
To allow also other types than <code>std::random_device</code> to be =
used, a new concept
<em>seed generator</em> that only specifies the <code>generate</code>=
member function should be introduced and
the <em>seed sequence</em> concept be defined as a refinement of it.
</p>
<p>
The specification of <code>std::random_device</code> should be change=
d such that it meets the requirements
of <em>seed generator</em>. The only thing that is needed here is th=
e addition of the <code>generate</code>
member function.
</p>
<p>
This proposal has no dependencies on any other proposal. The author =
is not aware of any other proposal that
depends on or conflicts with this proposal. In particular, it is ort=
hogonal to N3547 [<a href=3D"#ref-05">5</a>].
(However, the sample implementation of <code>std::randomize</code> in=
that paper could benefit from the feature
suggested in this proposal.)
</p>
<h3 id=3D"sec-rand-req-eng">3.1 Clarification on Random Number Engine R=
equirements</h3>
<p>
Currently, table 117 in section 26.5.1.4 [rand.req.eng] def=
ines the various overloads of the
<code>seed</code> member function of a type <code>E</code> that meets=
the requirements of <em>random number
engine</em> in terms of the corresponding constructor and equality op=
erator. For example, <code>e.seed(q)</code>
is defined to have the effect that <q>post: <code>e =3D=3D =
E(q)</code></q> and complexity <q>same as
<code>E(q)</code></q>. This is unfortunate because for a <em>seed se=
quence</em> <code>q</code>, two successive
calls to <code>q.generate</code> (even for ranges of identical size) =
do not have to produce the same sequence of
numbers, even though <code>std::seed_seq</code> happens to behave tha=
t way. The requirements for <em>seed
sequence</em> don't mandate this; the respective row in table 11=
5 says about
<code>q.generate(rb, re)</code> (emphasis added):
</p>
<blockquote>
<p>
Does nothing if <code>rb =3D=3D re</code>. Otherwise, fi=
lls the supplied sequence
<code>[rb, re)</code> with 32-bit quantities that depend on th=
e sequence supplied to the constructor
<strong>and possibly also depend on the history of <code>generate</=
code>'s previous invocations</strong>.
</p>
</blockquote>
<p>
Therefore, the author believes that it is not intended by the current=
standard that the following code should be
guaranteed to work.
</p>
<pre>template <typename RandEngT, typename SeedSeqT>
<span class=3D"comment">// requires(RandomNumberEngine(RandEngT) &&am=
p; SeedSequence(SeedSeqT))</span>
void
test(RandEngT& engine, SeedSeqT& seedseq)
{
engine.seed(seedseq);
assert(engine =3D=3D RandEngT {seedseq}); <span class=3D"comment">// mig=
ht fire</span>
}</pre>
<p>
Regardless of whether this proposal will be adopted, the wording in t=
able 117 should be updated to make it
clear that calling <code>seed</code> puts the engine into the same st=
ate as calling the corresponding constructor
but not create the impression that the <code>assert</code>ion in the =
above example would necessarily hold.
</p>
<h3 id=3D"sec-deprecation">3.2 Deprecation of Existing Features</h3>
<p>
It is not proposed that any existing library features be deprecated.
</p>
<p>
Possible candidates for deprecation could be
</p>
<ul>
<li>
<code>std::random_device::operator()</code> and
</li>
<li>
the overload of <code>E::seed</code> that takes a single value of t=
ype <code>E::result_type</code> and the
corresponding constructor of a <em>random number engine</em> <code>=
E</code>.
</li>
</ul>
<p>
The <code>operator()</code> of <code>std::random_device</code> should=
definitely stay and not be deprecated.
<code>std::random_device</code> meets the requirements of <em>uniform=
random number generator</em> and as such
needs that function. Its presence is also not the root cause of the =
problem this proposal sets out to solve. The
problem is not how the integer is obtained but that using a single in=
teger as a seed is insufficient.
</p>
<p>
Deprecating <code>E::seed</code> overloaded for <code>E::result_type<=
/code> and the corresponding constructor
would be more sensible because those functions actually encourage poo=
rly seeding random number engines. On the
other hand, they remain useful in situations where people want to har=
d-code a specific seed (such as in
<code>std::mt19937 {42}</code>) and don't really care about unif=
ormly choosing an initial state from the
entire state-space of the engine.
</p>
<h2 id=3D"sec-design-decisions">4. Design Decisions</h2>
<h3 id=3D"sec-alt-solutions">4.1 Alternative Solutions</h3>
<p>
The proposed solution falls into two parts:
</p>
<ul>
<li>
relaxing the type requirements on the <code>seed</code> member func=
tion and
</li>
<li>
making <code>std::random_device</code> comply with these relaxed re=
quirements.
</li>
</ul>
<p>
The author is not aware of any substantially different alternative so=
lution regarding the relaxation of the type
requirements. This is confirmed by the observation that O'Neill =
;[<a href=3D"#ref-01">1</a>] has independently
suggested the same change back in April 2015.
</p>
<h4 id=3D"sec-alt-adapter">4.1.1 Provide a Generic Adapter Type instead=
of Modifying <code>std::random_device</code></h4>
<p>
Instead of adding a member function to <code>std::random_device</code=
>, a new adapter type could be provided that
would turn any <em>uniform random number generator</em> into a <em>se=
ed generator</em>. This would have the
advantage that one could also use, say, a <code>std::mt19937</code> e=
ngine to seed another <code>std::ranlux24</code>
engine. (However useful that may be.) On the other hand, it would r=
equire more typing for the common case of
seeding any random engine with a <code>std::random_device</code> as t=
he temporary adapter object would have to be
created. Such an adapter could also not take advantage of the size o=
f the range being known ahead of time.
</p>
<p>
Anyway, here is a suggestion for this alternative.
</p>
<pre>template <typename UrngT>
<span class=3D"comment">// requires(UniformRandomNumberGenerator(UrngT))<=
/span>
class seed_gen
{
private:
UrngT urng_;
public:
template <typename... ArgTs>
seed_gen(ArgTs&&... args) : urng_ {std::forward<ArgTs>(args=
)...}
{
}
template <typename FwdIterT>
<span class=3D"comment">// requires(ForwardIterator(FwdIterT)</span>
<span class=3D"comment">// && Assignable(FwdIterT::val=
ue_type, std::uint32_t))</span>
void
generate(const FwdIterT first, const FwdIterT last)
{
std::uniform_int_distribution<std::uint32_t> dist {};
std::generate(first, last, [this, &dist](){ return dist(urng_); });
}
};</pre>
<p>
It would then be used like this.
</p>
<pre>std::seed_gen<std::random_device> generator {};
std::mt19937 engine {generator};
std::cout << engine() << '\n';</pre>
<h4 id=3D"sec-int-types">4.1.2 Integer Types</h4>
<p>
Another minor design variation would be to require
<code>std::random_device::generate</code> to not assign 32 bit v=
alues to each element in the range but rather
set all bits of the dereferenced iterator to independently chosen ran=
dom values. This would be a more natural
(and, in many contexts, more useful) behavior but it wouldn't be comp=
atible with the existing specification
of <em>seed sequence</em>. Therefore, it seems better to stay with t=
he 32 bit requirement.
</p>
<p>
Conversely, <code>std::random_device</code>'s <code>result_type</code=
> could be changed to
<code>std::uint32_t</code> and its <code>operator()</code> be require=
d to produce values in the range [0,
2<sup>32</sup>). This would integrate better with the other faciliti=
es but could potentially break existing
(brittle) code (on exotic platforms) in subtle ways. It could also a=
ffect performance adversely on platforms
where <code>std::random_device::operator()</code> is implemented via =
a special hardware instruction and the result
of that instruction is not a 32 bit value.
</p>
<h3 id=3D"sec-shortcomings">4.2 Shortcomings</h3>
<p>
A known minor shortcoming of the proposed solution is that the <code>=
seed</code> function (and corresponding
constructor) would have to take their argument by non-<code>const</co=
de> reference, so a temporary cannot bind to
it which means that it is not possible to write the following code.
</p>
<pre>auto engine =3D std::mt19937 {std::random_device {}}; <span class=
=3D"comment">// won't compile</span></pre>
<p>
Instead, one has to write the slightly more verbose
</p>
<pre>std::random_device device {};
auto engine =3D std::mt19937 {device};</pre>
<p>
which leaves the <code>std::random_device</code> in scope longer than=
necessary. Since it can be quite large and
might hold an open file handle, this is potentially undesirable. To =
avoid this, a lambda can be used.
</p>
<pre>auto engine =3D [](){
std::random_device device {}; <span class=3D"comment">// Only lives as l=
ong as the lambda…</span>
return std::mt19937 {device}; <span class=3D"comment">// …and the=
copy is hopefully elided.</span>
}();</pre>
<h3 id=3D"sec-impact-stdlib-impl">4.3 Impact on Standard Library Implem=
entations</h3>
<p>
Little to no code should be required to change in the implementations=
of the random engines. A quick glance over
the code of <code>libstdc++</code> [<a href=3D"#ref-03">3</a>] (=
GCC) and
<code>libc++</code> [<a href=3D"#ref-04">4</a>] (Clang) has show=
n that there are no changes required for
<code>libstdc++</code> and all that is needed for <code>libc++</code>=
is removing or weakening the concept check.
</p>
<p>
The to-be-added <code>generate</code> member function of <code>std::r=
andom_device</code> could be implemented in a
compliant but naïve way like this.
</p>
<pre>template <typename RandIterT>
<span class=3D"comment">// requires(RandomAccessIterator(RandIterT)</span>
<span class=3D"comment">// && Unsigned(RandIterT::value_=
type)</span>
<span class=3D"comment">// && (std::numeric_limits<Ra=
ndIterT::value_type>::digits >=3D 32))</span>
void
random_device::generate(const RandIterT first, const RandIterT last)
{
std::uniform_int_distribution<std::uint32_t> dist {};
std::generate(first, last, [this, &dist](){ return dist(*this); });
}</pre>
<p>
Implementers will probably be interested to provide optimizations for=
the case that <code>RandIterT</code> is a
pointer or can be converted to a pointer (such as
<code>std::vector<unsigned>::iterator_type</code>) so that inst=
ead of calling
<code>(*this)()</code> for each element, they can fill in all bytes a=
t once if reading from a file
like <code>/dev/urandom</code>. Care has to be taken to handle the c=
ase where <code>sizeof(RandIterT::value_type)
> sizeof(std::uint32_t)</code> correctly. This enhanced <code>std=
::random_device</code> could be useful in
other contexts, too.
</p>
<p>
It is worth mentioning that merely adding a member function does not =
break binary compatibility of existing code
that uses <code>std::random_device</code>.
</p>
<h3 id=3D"sec-implementations">4.4 Implementations</h3>
<p>
A patch to implement this proposal for <code>libstdc++</code> can be =
found on the author's
website [<a href=3D"#ref-07">7</a>] and will be continuously upd=
ated.
</p>
<h2 id=3D"sec-prop-word">5. Proposed Wording</h2>
<p>
All proposed changes to the standard mentioned in this section are re=
lative to N4140.
</p>
<p>
Add a new section before the existing =C2=A7 26.5.1.2 [rand.req.=
seeseq] to define
<em>seed generator</em>.
</p>
<blockquote>
<p>
<strong>Seed generator requirements [rand.req.seedgen]</strong>
</p>
<p>
A <em>seed generator</em> is an object that produces a requested nu=
mber of unsigned integer values <var>i</var>
with 0 ≤ <var>i</var> < 2<sup>32</sup>. The generated number=
s may be obtained from a non-deterministic
source of entropy.
</p>
<p>
A class <code>S</code> satisfies the requirements of a seed generat=
or if the expressions shown in the below
table are valid and have the indicated semantics and if <code>S</co=
de> also satisfies all other requirements of
this section. In that table and throughout this section:
</p>
<ol style=3D"list-style-type: lower-alpha">
<li>
<code>T</code> is the type named by <code>S</code>'s associated
<code>result_type</code>;
</li>
<li>
<code>q</code> is a value of <code>S</code>;
</li>
<li>
<code>rb</code> and <code>re</code> are mutable random access ite=
rators with an unsigned
integer <code>value_type</code> of at least 32 bits.
</li>
</ol>
<table border=3D"1" cellspacing=3D"0" cellpadding=3D"5">
<tr>
<th><p>Expression</p></th>
<th><p>Return type</p></th>
<th><p>Pre/post-condition</p></th>
<th><p>Complexity</p></th>
</tr>
<tr>
<td>
<p>
<code>S::result_type</code>
</p>
</td>
<td>
<p>
<code>T</code>
</p>
</td>
<td>
<p>
<code>T</code> is an unsigned integer type of at least 32 bit=
s.
</p>
</td>
<td>
<p>
compile-time
</p>
</td>
</tr>
<tr>
<td>
<p>
<code>q.generate(rb, re)</code>
</p>
</td>
<td>
<p>
<code>void</code>
</p>
</td>
<td>
<p>
Does nothing if <code>rb =3D=3D re</code>. Otherwi=
se, fills the supplied sequence
[<code>rb</code>, <code>re</code>) with 32-bit quantitie=
s in a possibly non-deterministic way.
</p>
</td>
<td>
<p>
<var>Ο</var>(<code>re - rb</code>)
</p>
</td>
</tr>
</table>
<p><!-- phantom space --></p>
</blockquote>
<p>
In the existing section =C2=A7 26.5.1.2 [rand.req.seedseq], chan=
ge the beginning of the second paragraph as
follows.
</p>
<blockquote>
<p>
A class <code>S</code> satisfies the requirements of a seed sequence =
if it satisfies the requirements of a seed
generator and in addition, the expressions […]
</p>
</blockquote>
<p>
In the current table 115, remove the first (<code>S::result_type</cod=
e>)
and the fifth (<code>q.generate(rb, re)</code>) row which will
already be covered by the <em>seed generator</em> requirements.
</p>
<p>
In section 26.5.6 [rand.device], add the following sentence at the en=
d of the first paragraph.
</p>
<blockquote>
<p>
It also meets the requirements of a seed generator.
</p>
</blockquote>
<p>
Add the following declaration to the <code>class</code> overview of <=
code>std::random_device</code> right after
the <code>operator()</code> under the <q>generating functions</q> sec=
tion.
</p>
<blockquote>
<pre>template <typename RandIterT> void generate(RandIterT firs=
t, RandIterT last);</pre>
</blockquote>
<p>
After paragraph 7 of the same section, add the following specificatio=
n.
</p>
<blockquote>
<pre>template <typename RandIterT> void generate(RandIterT firs=
t, RandIterT last);</pre>
<p>
<em>Requires:</em> <code>RandIterT</code> must meet the requirement=
s of random access iterator and
its <code>value_type</code> must be an unsigned integer of at least=
32 bits.
</p>
<p>
<em>Effects:</em> Assigns non-deterministic 32 bit random values un=
iformly distributed over the interval [0,
2<sup>32</sup>) to the elements in the sequence [<code>first</code>=
, <code>last</code>). This function
behaves as if it were implemented by the following code.
</p>
<pre>uniform_int_distribution<uint32_t> dist {};
generate(first, last, [this, &dist](){ return dist(*this); });</pre>
<p>
<em>Throws:</em> A value of an implementation-defined type derived =
from <code>exception</code> if a random
number could not be obtained. It is unspecified in this case what =
and whether any values have been assigned to
the elements in the range.
</p>
</blockquote>
<p>
Replace section 26.5.1.4 [rand.req.eng] paragraph 4 letter&=
nbsp;d by the following sentence with the
appropriate cross-reference to the section defining the requirements =
of <em>seed generator</em>.
</p>
<blockquote>
<p>
<code>q</code> is an lvalue satisfying the requirements of a seed g=
enerator;
</p>
</blockquote>
<p>
Re-structure the first seven rows of the current table 117 as fo=
llows. It is believed that this preserves
the intended meaning of the current wording but avoids confusion.
</p>
<blockquote>
<p><!-- phantom space --></p>
<table border=3D"1" cellspacing=3D"0" cellpadding=3D"5">
<tr>
<th><p>Expression</p></th>
<th><p>Return type</p></th>
<th><p>Pre/post-condition</p></th>
<th><p>Complexity</p></th>
</tr>
<tr>
<td><p><code>E()</code></p></td>
<td><p></p></td>
<td>
<p>
Creates an engine with the same initial state as all other de=
fault-constructed engines of type
<code>E</code>.
</p>
</td>
<td><p><var>Ο</var>(size of state)</p></td>
</tr>
<tr>
<td><p><code>E(x)</code></p></td>
<td><p></p></td>
<td>
<p>
Creates an engine that compares equal to <code>x</code>.
</p>
</td>
<td><p><var>Ο</var>(size of state)</p></td>
</tr>
<tr>
<td><p><code>E(s)</code></p></td>
<td><p></p></td>
<td>
<p>
Creates an engine with an initial state as if by first defaul=
t-constructing the engine and then calling
<code>seed(s)</code> on it.
</p>
</td>
<td><p>no worse than <code>E()</code> followed by <code>seed(s)</=
code></p></td>
</tr>
<tr>
<td><p><code>E(q)</code></p></td>
<td><p></p></td>
<td>
<p>
Creates an engine with an initial state as if by first defaul=
t-constructing the engine and then calling
<code>seed(q)</code> on it.
</p>
</td>
<td><p>no worse than <code>E()</code> followed by <code>seed(q)</=
code></p></td>
</tr>
<tr>
<td><p><code>e.seed()</code></p></td>
<td><p><code>void</code></p></td>
<td>
<p>Puts the engine into the same state as a default-constructed=
engine of type <code>E</code>.</p>
</td>
<td><p><var>Ο</var>(size of state)</p></td>
</tr>
<tr>
<td><p><code>e.seed(s)</code></p></td>
<td><p><code>void</code></p></td>
<td>
<p>
Puts the egine into a state determined by <code>s</code>. [&n=
bsp;<em>Note:</em> For engines with an
internal state larger than <code>sizeof(s)</code>, there will=
be impossible states after calling this
function. — <em>end note</em> ]
</p>
</td>
<td><p><var>Ο</var>(size of state)</p></td>
</tr>
<tr>
<td><p><code>e.seed(q)</code></p></td>
<td><p><code>void</code></p></td>
<td>
<p>
Puts the engine into a state that depends on a sequence produ=
ced by one call to <code>q.generate</code>
for a range of the size of the engine's state.
</p>
</td>
<td>
<p>
same as complexity of <code>q.generate</code> called on a ran=
ge of the size of the engine's state
</p>
</td>
</tr>
</table>
<p><!-- phantom space --></p>
</blockquote>
<h2 id=3D"sec-acknowledgments">Acknowledgments</h2>
<p>
Melissa O'Neill has written a series of remarkable blog posts that di=
scuss the problems with seeding random
engines in-depth. Although not the initial motivation for the author=
of this proposal, that blog post provided
valuable theoretical and experimental support and the fact that its a=
uthor had independently suggested basically
the same addition to the standard library was very affirming.
</p>
<p>
The discussions with the principal author of <code><random></co=
de>, Walter Brown, were very enlightening and
helped the author a lot figuring out the final details of the proposa=
l.
</p>
<p>
Nicol Bolas, Zhihao Yuan and Seth Cantrell have provided valuable fee=
dback on the
<code>std-proposals@isocpp.org</code> mailing list.
</p>
<p>
Baum mit Augen's shared experience of struggling to properly seed a <=
code>std::mt19937</code> from
a <code>std::random_device</code> and the following discussion with D=
eduplicator (out of which came an earlier
version of the code for <code>seed_non_deterministically_2nd</code>) =
were part of the motivation for writing this
proposal [<a href=3D"#ref-06">6</a>].
</p>
<h2 id=3D"sec-references">References</h2>
<ol class=3D"references">
<li id=3D"ref-01">
Melissa O'Neill,
<em>C++ Seeding Surprises.</em> 2015-04-16,
<a href=3D"http://www.pcg-random.org/posts/cpp-seeding-surprises.ht=
ml">http://www.pcg-random.org/posts/cpp-seeding-surprises.html</a>
</li>
<li id=3D"ref-02">
Nicol Bolas, via <code>std-proposals@isocpp.org</code>, 2016-01-03,
<a href=3D"https://groups.google.com/a/isocpp.org/d/msg/std-proposa=
ls/sF-P4VE2Z3Q/u24T-g-hEgAJ">https://groups.google.com/a/isocpp.org/d/msg/s=
td-proposals/sF-P4VE2Z3Q/u24T-g-hEgAJ</a>
</li>
<li id=3D"ref-03">
The <code>libc++</code> C++ Standard Library,
<a href=3D"http://libcxx.llvm.org/">http://libcxx.llvm.org/</a>
</li>
<li id=3D"ref-04">
The GNU Standard C++ Library Version 3,
<a href=3D"https://gcc.gnu.org/libstdc++/">https://gcc.gnu.org/libs=
tdc++/</a>
</li>
<li id=3D"ref-05">
Walter Brown,
<em>Three <code><random></code> related Proposals.</em>
N3547, 2013-03-12,
<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/=
n3547.pdf">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3547.pd=
f</a>
</li>
<li id=3D"ref-06">
<q>Seed <code>std::mt19937</code> from <code>std::random_device</co=
de></q>
in: <em>Code Review</em>,
2015-10-30,
<a href=3D"http://codereview.stackexchange.com/q/109260">http://cod=
ereview.stackexchange.com/q/109260</a>
</li>
<li id=3D"ref-07">
<a href=3D"http://klammler.eu/data/computer-science/iso-c++/p0205/"=
>http://klammler.eu/data/computer-science/iso-c++/p0205/</a>
</li>
</ol>
</body>
</html>
--=-=-=--
.
Author: Myriachan <myriachan@gmail.com>
Date: Thu, 11 Feb 2016 11:08:36 -0800 (PST)
Raw View
------=_Part_1232_1776009480.1455217716749
Content-Type: multipart/alternative;
boundary="----=_Part_1233_235077424.1455217716750"
------=_Part_1233_235077424.1455217716750
Content-Type: text/plain; charset=UTF-8
Wouldn't this encourage the use of std::random_device, typically
implemented as a cryptographically-secure random number generator, to seed
an algorithm that is not cryptographically-secure, possibly making unaware
programmers believe that they are doing correct procedures for generating
keys?
There's nothing wrong with using std::random_device to seed a typical
random number generator, so long as you're aware that the result should not
be considered secure for cryptography.
Melissa
On Wednesday, February 10, 2016 at 10:09:49 AM UTC-8, Moritz Klammler wrote:
>
> Attached is my final draft for the proposal. My plans are to formally
> submit it tomorrow. Until then, I can still apply last-minute fixes but
> given how little time is left, I know that this is unrealistic.
>
> There is also an implementation of the proposal available now:
>
> http://klammler.eu/data/computer-science/iso-c++/p0205/
>
> Thank you to all who have provided feedback so far.
>
>
>
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_1233_235077424.1455217716750
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Wouldn't this encourage the use of std::random_device,=
typically implemented as a cryptographically-secure random number generato=
r, to seed an algorithm that is not cryptographically-secure, possibly maki=
ng unaware programmers believe that they are doing correct procedures for g=
enerating keys?<br><br>There's nothing wrong with using std::random_dev=
ice to seed a typical random number generator, so long as you're aware =
that the result should not be considered secure for cryptography.<br><br>Me=
lissa<br><br>On Wednesday, February 10, 2016 at 10:09:49 AM UTC-8, Moritz K=
lammler wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Attached is my f=
inal draft for the proposal. =C2=A0My plans are to formally
<br>submit it tomorrow. =C2=A0Until then, I can still apply last-minute fix=
es but
<br>given how little time is left, I know that this is unrealistic.
<br>
<br>There is also an implementation of the proposal available now:
<br>
<br>=C2=A0 =C2=A0 <a href=3D"http://klammler.eu/data/computer-science/iso-c=
++/p0205/" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#=
39;http://www.google.com/url?q\75http%3A%2F%2Fklammler.eu%2Fdata%2Fcomputer=
-science%2Fiso-c%2B%2B%2Fp0205%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNGMt1GY=
-R4hZYguKG7HLlKK3qAQUw';return true;" onclick=3D"this.href=3D'http:=
//www.google.com/url?q\75http%3A%2F%2Fklammler.eu%2Fdata%2Fcomputer-science=
%2Fiso-c%2B%2B%2Fp0205%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNGMt1GY-R4hZYgu=
KG7HLlKK3qAQUw';return true;">http://klammler.eu/data/<wbr>computer-sci=
ence/iso-c++/<wbr>p0205/</a>
<br>
<br>Thank you to all who have provided feedback so far.
<br>
<br>
<br></blockquote></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_1233_235077424.1455217716750--
------=_Part_1232_1776009480.1455217716749--
.