In order to seed a pseudo random number generator of type `EngineT` that
meets the requirements of *random number engine* (=C2=A7 20.5.1.4) with a
non-deterministic seed, most people seem to use code like in the
following snippet.

    template <typename EngineT>
      // requires RandomNumberEngine(EngineT)
    void
    seed_non_deterministically(EngineT& engine)
    {
      std::random_device rnddev {};
      engine.seed(rnddev());
    }

While apparently simple, this technique has the disadvantage that it can
only put the engine into one of

    1ULL << CHAR_BIT * sizeof(std::random_device::result_type)

different states.  If the state size of `EngineT` is less than or equal
to 32 bits, this is guaranteed to be fine.  However, almost all random
number engines specified by the standard have considerably larger state
sizes.  In order to seed such an engine in a way that each of its
possible states is about equally likely, I have resorted to using a
*seed sequence* (=C2=A7 26.5.1.2) created from an array of non-deterministi=
c
random numbers.  Baum mit Augen has independently discovered this
workaround and initiated a discussion [1] on *Code Review* where all
participants concluded that -- apart from minor tweaks -- there was no
better way to seed the engine.  The code might look something like this.

    template <typename EngineT, std::size_t StateSize =3D EngineT::state_si=
ze>
      // requires RandomNumberEngine(EngineT)
    void
    seed_non_deterministically(EngineT& engine)
    {
      using result_type =3D typename EngineT::result_type;
      std::array<result_type, StateSize> noise {};
      std::random_device rnddev {};
      std::generate(noise.begin(), noise.end(), std::ref(rnddev));
      std::seed_seq seedseq(noise.cbegin(), noise.cend());
      engine.seed(seedseq);
    }

I have just realized that the above code is also flawed as it is not
guaranteed that

    sizeof(std::random_device::result_type) >=3D sizeof(result_type)

In fact, on my implementation, this is not true.  This defect can be
fixed but it shows how difficult it is to correctly seed the engine -- a
supposedly simple task.

The use of a seed sequence is also less than desirable in other
respects.  It scrambles the numbers from its input sequence beyond
recognition in an attempt to remove any skew but `std::random_device` is
already supposed to produce highly uniform output so at best this
scrambling is wasting CPU cycles.  At worst, it *introduces* skew.  This
shortcoming could be avoided by implementing a custom seed sequence type
that takes the input sequence as given.  A seed sequence also needs to
store its internal state in a dynamically allocated buffer which seems
wasteful and unnecessary.

I believe that the standard library should address this issue and
provide an easy-to-use and difficult-to-use-incorrectly way to seed a
random number engine with a non-deterministic seed such that each of its
possible states is entered with about equal chance.

The seemingly obvious solution of making `std::random_device` meet the
requirements of seed sequence unfortunately doesn't work because a seed
sequence must (1) have a finite state and (2) needs to be able to
serialize that state.  This is contrary to the very idea of
`std::random_device`.

However, the only functionality of seed sequence that the `seed`
function of the random number engines *really* need is its `generate`
member function.  Implementing this function would totally be in scope
for `std::random_device`.

As a matter of fact, it would also allow for a performance optimization.
Currently, my libstdc++ implementation makes a call to `read` (or even
`fread` on systems where `unistd.h` is not available) for each and every
call to `std::random_device::operator()` [*].  When generating more than
a few integers, this becomes incredibly slow.  `generate` -- called with
appropriate iterators -- on the other hand, could be optimized to only
make a single system call that reads directly into the destination
buffer.  This could also be useful in other contexts.

So my proposed change is to weaken the requirements for the `seed`
function taking a seed sequence (and the corresponding constructor) in
random number engine to not require a seed sequence but only a type with
the `generate` member function specified in the requirements for seed
sequence.  In addition, such member function should be added to the
specification of `std::random_device`.  I think this is a small
non-breaking change that would be highly useful in many programs.

I would be happy to hear feedback about the proposed change.  I'd also
be interested in opinions about what procedure should I follow to push
this further.  Should I write a proposal or file a defect report?


Thanks for reading

Moritz


Footnotes:

[*] It does this when the source of entropy is a file like
    `/dev/urandom`.  On platforms that support it, libstdc++ will use a
    special hardware instruction to generate non-deterministic random
    numbers extremely fast.

References:

[1] http://codereview.stackexchange.com/q/109260

--=20

---=20
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 e=
mail 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-propos=
als/.

.

------=_Part_2585_107313511.1451794091592
Content-Type: multipart/alternative;
 boundary="----=_Part_2586_119705594.1451794091592"

------=_Part_2586_119705594.1451794091592
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Saturday, January 2, 2016 at 10:11:39 PM UTC-5, Moritz Klammler wrote:
>
> In order to seed a pseudo random number generator of type `EngineT` that=
=20
> meets the requirements of *random number engine* (=C2=A7 20.5.1.4) with a=
=20
> non-deterministic seed, most people seem to use code like in the=20
> following snippet.=20
>
>     template <typename EngineT>=20
>       // requires RandomNumberEngine(EngineT)=20
>     void=20
>     seed_non_deterministically(EngineT& engine)=20
>     {=20
>       std::random_device rnddev {};=20
>       engine.seed(rnddev());=20
>     }=20
>
> While apparently simple, this technique has the disadvantage that it can=
=20
> only put the engine into one of=20
>
>     1ULL << CHAR_BIT * sizeof(std::random_device::result_type)=20
>
> different states.  If the state size of `EngineT` is less than or equal=
=20
> to 32 bits, this is guaranteed to be fine.  However, almost all random=20
> number engines specified by the standard have considerably larger state=
=20
> sizes.  In order to seed such an engine in a way that each of its=20
> possible states is about equally likely, I have resorted to using a=20
> *seed sequence* (=C2=A7 26.5.1.2) created from an array of non-determinis=
tic=20
> random numbers.  Baum mit Augen has independently discovered this=20
> workaround and initiated a discussion [1] on *Code Review* where all=20
> participants concluded that -- apart from minor tweaks -- there was no=20
> better way to seed the engine.  The code might look something like this.=
=20
>
>     template <typename EngineT, std::size_t StateSize =3D=20
> EngineT::state_size>=20
>       // requires RandomNumberEngine(EngineT)=20
>     void=20
>     seed_non_deterministically(EngineT& engine)=20
>     {=20
>       using result_type =3D typename EngineT::result_type;=20
>       std::array<result_type, StateSize> noise {};=20
>       std::random_device rnddev {};=20
>       std::generate(noise.begin(), noise.end(), std::ref(rnddev));=20
>       std::seed_seq seedseq(noise.cbegin(), noise.cend());=20
>       engine.seed(seedseq);=20
>     }=20
>
> I have just realized that the above code is also flawed as it is not=20
> guaranteed that=20
>
>     sizeof(std::random_device::result_type) >=3D sizeof(result_type)=20
>
> In fact, on my implementation, this is not true.  This defect can be=20
> fixed but it shows how difficult it is to correctly seed the engine -- a=
=20
> supposedly simple task.=20
>
> The use of a seed sequence is also less than desirable in other=20
> respects.  It scrambles the numbers from its input sequence beyond=20
> recognition in an attempt to remove any skew but `std::random_device` is=
=20
> already supposed to produce highly uniform output so at best this=20
> scrambling is wasting CPU cycles.  At worst, it *introduces* skew.  This=
=20
> shortcoming could be avoided by implementing a custom seed sequence type=
=20
> that takes the input sequence as given.  A seed sequence also needs to=20
> store its internal state in a dynamically allocated buffer which seems=20
> wasteful and unnecessary.=20
>
> I believe that the standard library should address this issue and=20
> provide an easy-to-use and difficult-to-use-incorrectly way to seed a=20
> random number engine with a non-deterministic seed such that each of its=
=20
> possible states is entered with about equal chance.=20
>
> The seemingly obvious solution of making `std::random_device` meet the=20
> requirements of seed sequence unfortunately doesn't work because a seed=
=20
> sequence must (1) have a finite state and (2) needs to be able to=20
> serialize that state.  This is contrary to the very idea of=20
> `std::random_device`.=20
>
> However, the only functionality of seed sequence that the `seed`=20
> function of the random number engines *really* need is its `generate`=20
> member function.  Implementing this function would totally be in scope=20
> for `std::random_device`.=20
>
> As a matter of fact, it would also allow for a performance optimization.=
=20
> Currently, my libstdc++ implementation makes a call to `read` (or even=20
> `fread` on systems where `unistd.h` is not available) for each and every=
=20
> call to `std::random_device::operator()` [*].  When generating more than=
=20
> a few integers, this becomes incredibly slow.  `generate` -- called with=
=20
> appropriate iterators -- on the other hand, could be optimized to only=20
> make a single system call that reads directly into the destination=20
> buffer.


Random-access iterators are not necessarily contiguous. So you aren't=20
allowed to read into the iterators passed to `generate` like that. Of=20
course, you can always create your own buffer, read into that, and then=20
write each value out to the random-access iterators.

That being said, requiring that these be *contiguous* iterators (once we=20
get those into the standard) would be entirely legitimate.
=20

> This could also be useful in other contexts.
>
> So my proposed change is to weaken the requirements for the `seed`=20
> function taking a seed sequence (and the corresponding constructor) in=20
> random number engine to not require a seed sequence but only a type with=
=20
> the `generate` member function specified in the requirements for seed=20
> sequence.  In addition, such member function should be added to the=20
> specification of `std::random_device`.  I think this is a small=20
> non-breaking change that would be highly useful in many programs.=20
>
> I would be happy to hear feedback about the proposed change.  I'd also=20
> be interested in opinions about what procedure should I follow to push=20
> this further.  Should I write a proposal or file a defect report?=20
>
>
> Thanks for reading=20
>
> Moritz=20
>
>
> Footnotes:=20
>
> [*] It does this when the source of entropy is a file like=20
>     `/dev/urandom`.  On platforms that support it, libstdc++ will use a=
=20
>     special hardware instruction to generate non-deterministic random=20
>     numbers extremely fast.=20
>
> References:=20
>
> [1] http://codereview.stackexchange.com/q/109260=20
>

There may be something you have not considered here.

For all random number engines, the constructor that takes a seed sequence=
=20
and the `seed` member function that takes such a sequence is required to:

1) Set up the initial state such that it "depends on a sequence produced by=
 *one=20
call* to `q.generate`" (emphasis added)

2) Have complexity that is the "same as complexity of `q.generate` called=
=20
on a sequence whose length is size of state".

The quotes are taken from Table 117 in section 26.5.1.4, p4 (in N4140=20
<http://wg21.link/N4140>).

Given those complexity guarantees, there's not much a valid implementation=
=20
of sequence-based initializers can do. They can't call `param`, since that=
=20
breaks the complexity guarantee. They can't create a non-default sequence.=
=20
And sequences aren't required to be copy/moveable. So the only valid=20
operations they could do and still maintain their required complexity=20
guarantees are default construction, calling `generate`, and calling `size`=
..

So I think your requirements are already satisfied in that regard.

Granted, what that will do once concepts come to random number engines, I=
=20
can't say. But for the time being, there's no reason you couldn't get away=
=20
with just providing `generate` and a constant `size`.

That's not to say that a specialized tool for doing this would not be=20
unreasonable. I don't much care for having to use seed_seq's memory=20
allocation just to seed an RNG, so a general solution would be good.

I think it would be best to do it with a template function based on the=20
engine:

template<typename engine>
engine random_device_seed();

The function would be able to use a compile-time determined size for the=20
state of the seed sequence, since it knows exactly how much the `engine`=20
will require. So it won't need to allocate any memory, outside of the stack=
..

--=20

---=20
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 e=
mail 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-propos=
als/.

------=_Part_2586_119705594.1451794091592
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Saturday, January 2, 2016 at 10:11:39 PM UTC-5, Moritz Klammler wrote:<b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;">In order to seed a pseudo random=
 number generator of type `EngineT` that
<br>meets the requirements of *random number engine* (=C2=A7 20.5.1.4) with=
 a
<br>non-deterministic seed, most people seem to use code like in the
<br>following snippet.
<br>
<br>=C2=A0 =C2=A0 template &lt;typename EngineT&gt;
<br>=C2=A0 =C2=A0 =C2=A0 // requires RandomNumberEngine(EngineT)
<br>=C2=A0 =C2=A0 void
<br>=C2=A0 =C2=A0 seed_non_deterministically(<wbr>EngineT&amp; engine)
<br>=C2=A0 =C2=A0 {
<br>=C2=A0 =C2=A0 =C2=A0 std::random_device rnddev {};
<br>=C2=A0 =C2=A0 =C2=A0 engine.seed(rnddev());
<br>=C2=A0 =C2=A0 }
<br>
<br>While apparently simple, this technique has the disadvantage that it ca=
n
<br>only put the engine into one of
<br>
<br>=C2=A0 =C2=A0 1ULL &lt;&lt; CHAR_BIT * sizeof(std::random_device::<wbr>=
result_type)
<br>
<br>different states. =C2=A0If the state size of `EngineT` is less than or =
equal
<br>to 32 bits, this is guaranteed to be fine. =C2=A0However, almost all ra=
ndom
<br>number engines specified by the standard have considerably larger state
<br>sizes. =C2=A0In order to seed such an engine in a way that each of its
<br>possible states is about equally likely, I have resorted to using a
<br>*seed sequence* (=C2=A7 26.5.1.2) created from an array of non-determin=
istic
<br>random numbers. =C2=A0Baum mit Augen has independently discovered this
<br>workaround and initiated a discussion [1] on *Code Review* where all
<br>participants concluded that -- apart from minor tweaks -- there was no
<br>better way to seed the engine. =C2=A0The code might look something like=
 this.
<br>
<br>=C2=A0 =C2=A0 template &lt;typename EngineT, std::size_t StateSize =3D =
EngineT::state_size&gt;
<br>=C2=A0 =C2=A0 =C2=A0 // requires RandomNumberEngine(EngineT)
<br>=C2=A0 =C2=A0 void
<br>=C2=A0 =C2=A0 seed_non_deterministically(<wbr>EngineT&amp; engine)
<br>=C2=A0 =C2=A0 {
<br>=C2=A0 =C2=A0 =C2=A0 using result_type =3D typename EngineT::result_typ=
e;
<br>=C2=A0 =C2=A0 =C2=A0 std::array&lt;result_type, StateSize&gt; noise {};
<br>=C2=A0 =C2=A0 =C2=A0 std::random_device rnddev {};
<br>=C2=A0 =C2=A0 =C2=A0 std::generate(noise.begin(), noise.end(), std::ref=
(rnddev));
<br>=C2=A0 =C2=A0 =C2=A0 std::seed_seq seedseq(noise.cbegin(), noise.cend()=
);
<br>=C2=A0 =C2=A0 =C2=A0 engine.seed(seedseq);
<br>=C2=A0 =C2=A0 }
<br>
<br>I have just realized that the above code is also flawed as it is not
<br>guaranteed that
<br>
<br>=C2=A0 =C2=A0 sizeof(std::random_device::<wbr>result_type) &gt;=3D size=
of(result_type)
<br>
<br>In fact, on my implementation, this is not true. =C2=A0This defect can =
be
<br>fixed but it shows how difficult it is to correctly seed the engine -- =
a
<br>supposedly simple task.
<br>
<br>The use of a seed sequence is also less than desirable in other
<br>respects. =C2=A0It scrambles the numbers from its input sequence beyond
<br>recognition in an attempt to remove any skew but `std::random_device` i=
s
<br>already supposed to produce highly uniform output so at best this
<br>scrambling is wasting CPU cycles. =C2=A0At worst, it *introduces* skew.=
 =C2=A0This
<br>shortcoming could be avoided by implementing a custom seed sequence typ=
e
<br>that takes the input sequence as given. =C2=A0A seed sequence also need=
s to
<br>store its internal state in a dynamically allocated buffer which seems
<br>wasteful and unnecessary.
<br>
<br>I believe that the standard library should address this issue and
<br>provide an easy-to-use and difficult-to-use-incorrectly way to seed a
<br>random number engine with a non-deterministic seed such that each of it=
s
<br>possible states is entered with about equal chance.
<br>
<br>The seemingly obvious solution of making `std::random_device` meet the
<br>requirements of seed sequence unfortunately doesn&#39;t work because a =
seed
<br>sequence must (1) have a finite state and (2) needs to be able to
<br>serialize that state. =C2=A0This is contrary to the very idea of
<br>`std::random_device`.
<br>
<br>However, the only functionality of seed sequence that the `seed`
<br>function of the random number engines *really* need is its `generate`
<br>member function. =C2=A0Implementing this function would totally be in s=
cope
<br>for `std::random_device`.
<br>
<br>As a matter of fact, it would also allow for a performance optimization=
..
<br>Currently, my libstdc++ implementation makes a call to `read` (or even
<br>`fread` on systems where `unistd.h` is not available) for each and ever=
y
<br>call to `std::random_device::operator(<wbr>)` [*]. =C2=A0When generatin=
g more than
<br>a few integers, this becomes incredibly slow. =C2=A0`generate` -- calle=
d with
<br>appropriate iterators -- on the other hand, could be optimized to only
<br>make a single system call that reads directly into the destination
<br>buffer.</blockquote><div><br>Random-access iterators are not necessaril=
y contiguous. So you aren&#39;t allowed to read into the iterators passed t=
o `generate` like that. Of course, you can always create your own buffer, r=
ead into that, and then write each value out to the random-access iterators=
..<br><br>That being said, requiring that these be <i>contiguous</i> iterato=
rs (once we get those into the standard) would be entirely legitimate.<br>=
=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">This could also be=
 useful in other contexts.<br>
<br>So my proposed change is to weaken the requirements for the `seed`
<br>function taking a seed sequence (and the corresponding constructor) in
<br>random number engine to not require a seed sequence but only a type wit=
h
<br>the `generate` member function specified in the requirements for seed
<br>sequence. =C2=A0In addition, such member function should be added to th=
e
<br>specification of `std::random_device`. =C2=A0I think this is a small
<br>non-breaking change that would be highly useful in many programs.
<br>
<br>I would be happy to hear feedback about the proposed change. =C2=A0I&#3=
9;d also
<br>be interested in opinions about what procedure should I follow to push
<br>this further. =C2=A0Should I write a proposal or file a defect report?
<br>
<br>
<br>Thanks for reading
<br>
<br>Moritz
<br>
<br>
<br>Footnotes:
<br>
<br>[*] It does this when the source of entropy is a file like
<br>=C2=A0 =C2=A0 `/dev/urandom`. =C2=A0On platforms that support it, libst=
dc++ will use a
<br>=C2=A0 =C2=A0 special hardware instruction to generate non-deterministi=
c random
<br>=C2=A0 =C2=A0 numbers extremely fast.
<br>
<br>References:
<br>
<br>[1] <a href=3D"http://codereview.stackexchange.com/q/109260" target=3D"=
_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;http://www.google.=
com/url?q\75http%3A%2F%2Fcodereview.stackexchange.com%2Fq%2F109260\46sa\75D=
\46sntz\0751\46usg\75AFQjCNFETgUBh8NXMbu-LLHIC_JUmCusZA&#39;;return true;" =
onclick=3D"this.href=3D&#39;http://www.google.com/url?q\75http%3A%2F%2Fcode=
review.stackexchange.com%2Fq%2F109260\46sa\75D\46sntz\0751\46usg\75AFQjCNFE=
TgUBh8NXMbu-LLHIC_JUmCusZA&#39;;return true;">http://codereview.<wbr>stacke=
xchange.com/q/109260</a>
<br></blockquote><div><br>There may be something you have not considered he=
re.<br><br>For all random number engines, the constructor that takes a seed=
 sequence and the `seed` member function that takes such a sequence is requ=
ired to:<br><br>1) Set up the initial state such that it &quot;depends on a=
 sequence produced by <b>one call</b> to `q.generate`&quot; (emphasis added=
)<br><br>2) Have complexity that is the &quot;same as complexity of `q.gene=
rate` called on a sequence whose length is size of state&quot;.<br><br>The =
quotes are taken from Table 117 in section 26.5.1.4, p4 (in <a href=3D"http=
://wg21.link/N4140">N4140</a>).<br><br>Given those complexity guarantees, t=
here&#39;s not much a valid implementation of sequence-based initializers c=
an do. They can&#39;t call `param`, since that breaks the complexity guaran=
tee. They can&#39;t create a non-default sequence. And sequences aren&#39;t=
 required to be copy/moveable. So the only valid operations they could do a=
nd still maintain their required complexity guarantees are default construc=
tion, calling `generate`, and calling `size`.<br><br>So I think your requir=
ements are already satisfied in that regard.<br><br>Granted, what that will=
 do once concepts come to random number engines, I can&#39;t say. But for t=
he time being, there&#39;s no reason you couldn&#39;t get away with just pr=
oviding `generate` and a constant `size`.<br><br>That&#39;s not to say that=
 a specialized tool for doing this would not be unreasonable. I don&#39;t m=
uch care for having to use seed_seq&#39;s memory allocation just to seed an=
 RNG, so a general solution would be good.<br><br>I think it would be best =
to do it with a template function based on the engine:<br><br><div class=3D=
"prettyprint" style=3D"background-color: rgb(250, 250, 250); border-color: =
rgb(187, 187, 187); border-style: solid; border-width: 1px; word-wrap: brea=
k-word;"><code class=3D"prettyprint"><div class=3D"subprettyprint"><span st=
yle=3D"color: #008;" class=3D"styled-by-prettify">template</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">typename</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> engine</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"><br>engine random_device_seed</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">();</span></div></code></=
div><br>The function would be able to use a compile-time determined size fo=
r the state of the seed sequence, since it knows exactly how much the `engi=
ne` will require. So it won&#39;t need to allocate any memory, outside of t=
he stack.<br></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_2586_119705594.1451794091592--
------=_Part_2585_107313511.1451794091592--

.

On Sat, Jan 2, 2016 at 9:11 PM, Moritz Klammler
<moritz.klammler@gmail.com> wrote:
>
> So my proposed change is to weaken the requirements for the `seed`
> function taking a seed sequence (and the corresponding constructor) in
> random number engine to not require a seed sequence but only a type with
> the `generate` member function specified in the requirements for seed
> sequence.  In addition, such member function should be added to the
> specification of `std::random_device`.  I think this is a small
> non-breaking change that would be highly useful in many programs.

Same idea came up here:

  "C++ Seeding Surprises"
  http://www.pcg-random.org/posts/cpp-seeding-surprises.html

, but if you continue read all the articles posted later by
the same author, you may find that tweaking random_device
etc is not a preferable way; we need a guaranteed source
of entropy for seeding, and also better seed sequences.
Purely addition, doing better job.

> I would be happy to hear feedback about the proposed change.  I'd also
> be interested in opinions about what procedure should I follow to push
> this further.  Should I write a proposal or file a defect report?

That will be a proposal, maybe even multiple ones.  You may
want to contact the author of the blog I mentioned above for
co-authoring.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://bit.ly/blog4bsd

--

---
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/.

.

>> As a matter of fact, it would also allow for a performance
>> optimization.  Currently, my libstdc++ implementation makes a call to
>> `read` (or even `fread` on systems where `unistd.h` is not available)
>> for each and every call to `std::random_device::operator()` [*].
>> When generating more than a few integers, this becomes incredibly
>> slow.  `generate` -- called with appropriate iterators -- on the
>> other hand, could be optimized to only make a single system call that
>> reads directly into the destination buffer.
>
>
> Random-access iterators are not necessarily contiguous. So you aren't
> allowed to read into the iterators passed to `generate` like that. Of
> course, you can always create your own buffer, read into that, and
> then write each value out to the random-access iterators.

My idea was that implementations could specialize the template for the
case where the iterators are raw pointers (or types from the standard
library that are known to wrap raw pointers like
`std::vector::iterator`).  Of course, they'd still need a fallback for
when the iterators don't refer to contiguous memory.  Anyway, this is
only a potential optimization that should be left to the
implementation.  The standard should not mandate anything like this.

> There may be something you have not considered here.
>
> For all random number engines, the constructor that takes a seed
> sequence and the `seed` member function that takes such a sequence is
> required to:
>
> 1) Set up the initial state such that it "depends on a sequence
>    produced by *one call* to `q.generate`" (emphasis added)
>
> 2) Have complexity that is the "same as complexity of `q.generate`
>    called on a sequence whose length is size of state".
>
> The quotes are taken from Table 117 in section 26.5.1.4, p4 (in N4140
> <http://wg21.link/N4140>).
>
> Given those complexity guarantees, there's not much a valid
> implementation of sequence-based initializers can do. They can't call
> `param`, since that breaks the complexity guarantee. They can't create
> a non-default sequence.  And sequences aren't required to be
> copy/moveable. So the only valid operations they could do and still
> maintain their required complexity guarantees are default
> construction, calling `generate`, and calling `size`.
>
> So I think your requirements are already satisfied in that regard.
>
> Granted, what that will do once concepts come to random number
> engines, I can't say. But for the time being, there's no reason you
> couldn't get away with just providing `generate` and a constant
> `size`.

I wasn't aware of those complexity constraints.

I have in fact tried out the following and it "works" with current
libstdc++ (GCC 5.3.0).  (I have also verified this by reading the source
code.)

    #include <algorithm>
    #include <functional>
    #include <iostream>
    #include <random>

    namespace /* anonymous */
    {

      class nd_seed_seq final
      {

      private:

        std::random_device rnddev_ {};

      public:

        template <typename OutputIterT>
        void
        generate(const OutputIterT first, const OutputIterT last)
        {
          std::generate(first, last, std::ref(this->rnddev_));
        }

      };

    }

    int
    main()
    {
      nd_seed_seq ndseed {};
      std::mt19937 rndeng {ndseed};
      std::cout << rndeng() << std::endl;
    }

However, I believe that it formally invokes undefined behavior because
`nd_seed_seq` does not meet the requirements of *seed sequence*.  Even
if an implementation might not be allowed to *call* those functions, it
certainly would be allowed to `static_assert` on their existence.  After
thinking about your remarks, however, I think that I could get away with
implementing those member functions with the correct signature but
make their bodies simply unconditionally throw an exception or likewise.

Nevertheless, while this might be a feasible workaround for C++14, I
would very much welcome a standard library feature to do this in a
simple way without having to write my own adapters.

--

---
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/.

.

>> So my proposed change is to weaken the requirements for the `seed`
>> function taking a seed sequence (and the corresponding constructor)
>> in random number engine to not require a seed sequence but only a
>> type with the `generate` member function specified in the
>> requirements for seed sequence.  In addition, such member function
>> should be added to the specification of `std::random_device`.  I
>> think this is a small non-breaking change that would be highly useful
>> in many programs.
>
> Same idea came up here:
>
>   "C++ Seeding Surprises"
>   http://www.pcg-random.org/posts/cpp-seeding-surprises.html
>
> , but if you continue read all the articles posted later by the same
> author, you may find that tweaking random_device etc is not a
> preferable way; we need a guaranteed source of entropy for seeding,
> and also better seed sequences.  Purely addition, doing better job.
>
>> I would be happy to hear feedback about the proposed change.  I'd
>> also be interested in opinions about what procedure should I follow
>> to push this further.  Should I write a proposal or file a defect
>> report?
>
> That will be a proposal, maybe even multiple ones.  You may want to
> contact the author of the blog I mentioned above for co-authoring.

That's a great article, thank you.  It's assuring to see that other
people already had the same idea.  I have contacted the author and asked
her whether she would be interested in co-authoring a proposal.

--

---
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/.

.

Based on your feedback, I have drafted an initial version of a proposal
to allow for a random number engine to be seeded non-deterministically
like this.

    std::random_device device {};
    auto engine = std::mt19937 {device};  // NOT calling operator()

Please find the current working draft in a variety of formats online
here:

    http://klammler.eu/data/computer-science/iso-c++/2016-01-18_seedseq/

If you want to send me patches, please edit the `seedseq.rst` file; the
other two are generated from it.

I'm excited to hear your comments about it.  This is my first proposal
so I guess I could need any amount of guidance.

--

---
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_1072_977875625.1454107432249
Content-Type: multipart/alternative;
 boundary="----=_Part_1073_903562412.1454107432249"

------=_Part_1073_903562412.1454107432249
Content-Type: text/plain; charset=UTF-8

I'm glad to see someone moving forward on this.

In the current random number engine requirements there's a requirement on
`e.seed(q)` that the post condition `e == E(q)` hold. Taken literally, this
suggests that given this proposal, the following code will work:

    std::random_device q;
    using E = std::mt19937;
    E e;

    e.seed(q);
    assert(e == E(q));

Since under this proposal the literal interpretation of `e == E(q)` will
not necessarily hold true, it should probably be modified. The
post-condition should instead make it clear that the state of `e` is the
only the same as if `e = E(q)` had been done instead of `e.seed(q)`.

--

---
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_1073_903562412.1454107432249
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m glad to see someone moving forward on this.<div><b=
r></div><div>In the current random number engine requirements there&#39;s a=
 requirement on `e.seed(q)` that the post condition `e =3D=3D E(q)` hold. T=
aken literally, this suggests that given this proposal, the following code =
will work:</div><div><br></div><div>=C2=A0 =C2=A0 std::random_device q;</di=
v><div>=C2=A0 =C2=A0 using E =3D std::mt19937;</div><div>=C2=A0 =C2=A0 E e;=
</div><div><br></div><div>=C2=A0 =C2=A0 e.seed(q);</div><div>=C2=A0 =C2=A0 =
assert(e =3D=3D E(q));</div><div><br></div><div>Since under this proposal t=
he literal interpretation of `e =3D=3D E(q)` will not necessarily hold true=
, it should probably be modified. The post-condition should instead make it=
 clear that the state of `e` is the only the same as if `e =3D E(q)` had be=
en done instead of `e.seed(q)`.</div></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_1073_903562412.1454107432249--
------=_Part_1072_977875625.1454107432249--

.

--=-=-=
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Thank you for pointing this out.  I believe that this already isn't true
by the C++14 standard.  Table 115 says for the `generate` function:

> Does nothing if `rb =3D=3D re`.  Otherwise, fills the supplied sequence
> `[rb, re)` with 32-bit quantities that depend on the sequence supplied
> to the constructor and possibly also depend on the history of
> `generate`=E2=80=99s previous invocations.

The key phrase here is of course *depend on the history*.  So even
though subsequent calls to `std::seed_seq::generate` (with the same
length of the output range) will produce the same numbers, the *seed
sequence* concept does not mandate this.  Hence, the "literal
interpretation" of `e =3D=3D E(q)` is not guaranteed to hold.

I agree that the wording in table 117 should be changed for the sake of
clarity.  I would prefer to define the constructors in terms of `seed`.
Since I believe that this doesn't actually *change* the standard, I
think it would be a defect report.  If others agree, I can write it up.

By the way, in the mean-time, I received a document number for my
proposal!  Please see the current draft attached.


seth.cantrell@gmail.com writes:

> I'm glad to see someone moving forward on this.
>
> In the current random number engine requirements there's a requirement
> on `e.seed(q)` that the post condition `e =3D=3D E(q)` hold. Taken
> literally, this suggests that given this proposal, the following code
> will work:
>
>     std::random_device q;
>     using E =3D std::mt19937;
>     E e;
>
>     e.seed(q);
>     assert(e =3D=3D E(q));
>
> Since under this proposal the literal interpretation of `e =3D=3D E(q)`
> will not necessarily hold true, it should probably be modified. The
> post-condition should instead make it clear that the state of `e` is
> the only the same as if `e =3D E(q)` had been done instead of
> `e.seed(q)`.

--=20

---=20
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 e=
mail 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-propos=
als/.

--=-=-=
Content-Type: text/html; charset=utf-8
Content-Disposition: attachment; filename=d0205r0.html
Content-Transfer-Encoding: quoted-printable
Content-Description: D0205R0 -- Allow Seeding Random Number Engines With
 std::random_device

<!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>D0205R0 &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;  */
      }

      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>D0205R0</td>
      </tr>
      <tr>
        <td>Date:</td>
        <td>2016-01-31</td>
      </tr>
      <tr>
        <td>Project:</td>
        <td>Programming Language C++</td>
      </tr>
      <tr>
        <td>Audience:</td>
        <td>Library Working Group, SG6 (Numerics)</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></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>
        </ol>
      </li>
      <li><a href=3D"#sec-tech-spec">5. Technical Specifications</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;
  // requires(RandomNumberEngine(EngineT))
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 found out that
      a <code>std::mt19937</code> engine seeded like above can never produc=
e the numbers 7 or 13 as its first value.
      Quite a surprise that can have bad consequences on real-world program=
s.  A program that incorrectly assumes that
      an impossible number will eventually be produced as the engine's firs=
t (or <var>n</var>-th) output is broken in a
      very subtle way.  After all, it would take extensive and practically =
unrealistic unit testing 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;
  // requires(RandomNumberEngine(EngineT))
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.)
        </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;
  // requires(RandomNumberEngine(EngineT))
void
seed_non_deterministically_3rd(EngineT&amp; engine)
{
  std::random_device rnddev {};
  engine.seed(rnddev);  // note: passing rnddev itself as opposed to the
                        // result of invoking its call operator
}</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>
    <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 use, say, a <code>std::mt19937</code> engine=
 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;
  // requires(UniformRandomNumberGenerator(UrngT))
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;
    // requires(ForwardIterator(FwdIterT)
    //          &amp;&amp; Assignable(FwdIterT::value_type, std::uint32_t))
  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 {}};  // won't co=
mpile</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 pot=
entially
      undesirable.  To avoid this, a lambda could be used.
    </p>
    <pre>auto engine =3D [](){
  std::random_device device {};  // only lives as long as the lambda ...
  return std::mt19937 {device};  // ... and the copy is hopefully elided
}();</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;
  // requires(RandomAccessIterator(RandIterT)
  //          &amp;&amp; Unsigned(RandIterT::value_type)
  //          &amp;&amp; (std::numeric_limits&lt;RandIterT::value_type&gt;:=
:digits &gt;=3D 32))
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>
    <h2 id=3D"sec-tech-spec">5. Technical Specifications</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 rows that are already 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.
      </p>
    </blockquote>
    <h2 id=3D"sec-acknowledgments">Acknowledgments</h2>
    <p>
      Melissa O'Neill has written a remarkable blog post&nbsp;[<a href=3D"#=
ref-01">1</a>] that discusses 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 f=
act that its author had independently
      suggested the same addition to the standard library was very affirmin=
g.
    </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>
    <p>
      Nicol Bolas and Zhihao Yuan have provided valuable feedback on the
      <code>std-proposals@isocpp.org</code> mailing list.
    </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-06">
        Walter Brown,
        <em>Three <code>&lt;random&gt;</code> related Proposals.</em>
        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-07">
        <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>
    </ol>
  </body>
</html>

--=-=-=--

.