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 &mdash; 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&nbsp;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
          &lt;<code><a id=3D"email">moritz\x2Eklammler\x40gmail\x2Ecom</a><=
/code>&gt;
          (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&nbsp;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>&lt;random&gt;</code> header.  It provides <em>random numbe=
r engines</em> (=C2=A7&nbsp;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&nbsp;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&nbsp;26.5.6 [rand.device]),
      a <em>uniform random number generator</em> (=C2=A7&nbsp;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&iuml;ve approach that most people seem to use is the following.
    </p>
    <pre>template &lt;typename EngineT&gt;
  <span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_1st(EngineT&amp; 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&#x202f;968&nbsp;bits.  However, if an <code>unsigned int</code> is=
 32&nbsp;bits (as is the common case on many
      platforms today), then of the up to 2<sup>19&#x202f;968</sup> states,=
 at most 2<sup>32</sup> (that is one
      2<sup>&minus;19&#x202f;936</sup>-th) can possibly be chosen!
    </p>
    <p>
      To illustrate that this is in fact a real problem, O'Neill&nbsp;[<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&nbsp;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&nbsp;26.5.7.1 [rand.util.seedseq])=
..  This type can be used to seed a random engine
      more thoroughly.
    </p>
    <pre>template &lt;typename EngineT, std::size_t StateSize =3D EngineT::=
state_size&gt;
  <span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_2nd(EngineT&amp; 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) &lt; sizeof(seedse=
q_type))
    ? (bytes_needed / sizeof(device_type))
    : (bytes_needed / sizeof(seedseq_type));
  std::array&lt;device_type, numbers_needed&gt; 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&nbsp;[<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 &lt;typename EngineT&gt;
  <span class=3D"comment">// requires(RandomNumberEngine(EngineT))</span>
void
seed_non_deterministically_3rd(EngineT&amp; 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&nbsp;[<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&nbsp;[<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&nbsp;117 in section&nbsp;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&nbsp;=3D=3D&nbsp;=
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&nbsp;11=
5 says about
      <code>q.generate(rb,&nbsp;re)</code> (emphasis added):
    </p>
    <blockquote>
      <p>
        Does nothing if <code>rb&nbsp;=3D=3D&nbsp;re</code>.  Otherwise, fi=
lls the supplied sequence
        <code>[rb,&nbsp;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 &lt;typename RandEngT, typename SeedSeqT&gt;
  <span class=3D"comment">// requires(RandomNumberEngine(RandEngT) &amp;&am=
p; SeedSequence(SeedSeqT))</span>
void
test(RandEngT&amp; engine, SeedSeqT&amp; 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&nbsp;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&nbsp;{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&nbsp=
;[<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 &lt;typename UrngT&gt;
  <span class=3D"comment">// requires(UniformRandomNumberGenerator(UrngT))<=
/span>
class seed_gen
{

private:

  UrngT urng_;

public:

  template &lt;typename... ArgTs&gt;
  seed_gen(ArgTs&amp;&amp;... args) : urng_ {std::forward&lt;ArgTs&gt;(args=
)...}
  {
  }

  template &lt;typename FwdIterT&gt;
    <span class=3D"comment">// requires(ForwardIterator(FwdIterT)</span>
    <span class=3D"comment">//          &amp;&amp; Assignable(FwdIterT::val=
ue_type, std::uint32_t))</span>
  void
  generate(const FwdIterT first, const FwdIterT last)
  {
    std::uniform_int_distribution&lt;std::uint32_t&gt; dist {};
    std::generate(first, last, [this, &amp;dist](){ return dist(urng_); });
  }

};</pre>
    <p>
      It would then be used like this.
    </p>
    <pre>std::seed_gen&lt;std::random_device&gt; generator {};
std::mt19937 engine {generator};
std::cout &lt;&lt; engine() &lt;&lt; '\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&nbsp;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&nbsp;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&nbsp;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&hellip;</span>
  return std::mt19937 {device};  <span class=3D"comment">// &hellip;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>&nbsp;[<a href=3D"#ref-03">3</a>] (=
GCC) and
      <code>libc++</code>&nbsp;[<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&iuml;ve way like this.
    </p>
    <pre>template &lt;typename RandIterT&gt;
  <span class=3D"comment">// requires(RandomAccessIterator(RandIterT)</span>
  <span class=3D"comment">//          &amp;&amp; Unsigned(RandIterT::value_=
type)</span>
  <span class=3D"comment">//          &amp;&amp; (std::numeric_limits&lt;Ra=
ndIterT::value_type&gt;::digits &gt;=3D 32))</span>
void
random_device::generate(const RandIterT first, const RandIterT last)
{
  std::uniform_int_distribution&lt;std::uint32_t&gt; dist {};
  std::generate(first, last, [this, &amp;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&lt;unsigned&gt;::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)
      &gt; 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&nbsp;[<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&nbsp;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 &le; <var>i</var> &lt; 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&nbsp;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,&nbsp;re)</code>
            </p>
          </td>
          <td>
            <p>
              <code>void</code>
            </p>
          </td>
          <td>
            <p>
              Does nothing if <code>rb&nbsp;=3D=3D&nbsp;re</code>.  Otherwi=
se, fills the supplied sequence
              [<code>rb</code>,&nbsp;<code>re</code>) with 32-bit quantitie=
s in a possibly non-deterministic way.
            </p>
          </td>
          <td>
            <p>
              <var>&Omicron;</var>(<code>re&nbsp;-&nbsp;rb</code>)
            </p>
          </td>
        </tr>
      </table>
      <p><!-- phantom space --></p>
    </blockquote>
    <p>
      In the existing section =C2=A7&nbsp;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 [&hellip;]
    </p>
    </blockquote>
    <p>
      In the current table 115, remove the first (<code>S::result_type</cod=
e>)
      and the fifth (<code>q.generate(rb,&nbsp;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 &lt;typename RandIterT&gt; 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 &lt;typename RandIterT&gt; 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&nbsp;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>=
,&nbsp;<code>last</code>).  This function
        behaves as if it were implemented by the following code.
      </p>
<pre>uniform_int_distribution&lt;uint32_t&gt; dist {};
generate(first, last, [this, &amp;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&nbsp;26.5.1.4 [rand.req.eng] paragraph&nbsp;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&nbsp;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>&Omicron;</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>&Omicron;</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>&Omicron;</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. &mdash;&nbsp;<em>end note</em>&nbsp;]
            </p>
          </td>
          <td><p><var>&Omicron;</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>&lt;random&gt;</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&nbsp;[<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&nbsp;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>&lt;random&gt;</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&#39;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&#39;s nothing wrong with using std::random_dev=
ice to seed a typical random number generator, so long as you&#39;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&#39;;return true;" onclick=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-R4hZYgu=
KG7HLlKK3qAQUw&#39;;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&quot; 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--

.