Random Device initialization is platform dependant?

[Christian Steins]

Hi,
the program from this tutorial video:

https://youtu.be/iCL6GYoi1RU

works a bit different on my system (GCC-TDM, Windows7):

C:\apps\CodeBlocks\Projects>.\a.exe
632059 632059

C:\apps\CodeBlocks\Projects>.\a.exe
632059 632059

So, on every run the same numbers are displayed.

How to get different random numbers on each run?

Version of my compiler: g++ (tdm64-1) 4.9.2

Christian

------------------------------------------------
// c++14 future test

#include <iostream>
#include <set>
#include <future>
#include <algorithm>
#include <random>

using namespace std;

auto make_sorted_random(const size_t num_elems)
{
std::set<int> retval;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, num_elems-1);

std::generate_n( std::inserter(retval, retval.end()),
num_elems,
[&](){ return dis(gen); } );

return retval;
}

int main()
{
auto f1 = async(launch::async, make_sorted_random, 1000000);
auto f2 = async(launch::async, make_sorted_random, 1000000);

cout << f1.get().size() << ' ' << f2.get().size() << endl;

}

[Ben Bacarisse]

Christian Steins <cs...@quantentunnel.de> writes:
<snip>

> How to get different random numbers on each run?

<snip>

> ------------------------------------------------
> // c++14 future test
>
> #include <iostream>
> #include <set>
> #include <future>
> #include <algorithm>
> #include <random>
>
> using namespace std;
>
> auto make_sorted_random(const size_t num_elems)
> {
> std::set<int> retval;
> std::random_device rd;

std::random_device is not guaranteed to use a genuinely random source
and may yield the same sequence every time.

The simplest solution is to delete that line and seed the mt19937
object with the time. You should only seed a generator once, so you
need to make the mt19937 object static:

> std::mt19937 gen(rd());

static std::mt19937 gen(std::time(0));

(#include <ctime> at the top). You can use C++'s own std::crono support
but for simple testing, I just use the old time function.

> std::uniform_int_distribution<> dis(0, num_elems-1);
>
> std::generate_n( std::inserter(retval, retval.end()),
> num_elems,
> [&](){ return dis(gen); } );
>
> return retval;
> }

<snip>
--
Ben.

[Richard]

[Please do not mail me a copy of your followup]

Ben Bacarisse <ben.u...@bsb.me.uk> spake the secret code
<87oa0ne...@bsb.me.uk> thusly:

>The simplest solution is to delete that line and seed the mt19937
>object with the time. You should only seed a generator once, so you
>need to make the mt19937 object static:

Nit: static objects like this make unit testing more difficult.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Christian Steins]

Am 07.12.2016 um 22:14 schrieb Ben Bacarisse:

>> How to get different random numbers on each run?

>> std::random_device rd;

> std::random_device is not guaranteed to use a genuinely random source
> and may yield the same sequence every time.

Ok, and by checking rd.entropy() I can find out if it's a real random
device (entropy > 0) or not.

In my case it returns 0.

Christian

[Öö Tiib]

If you want slightly less predictable seeds than time then Windows API
contains a CryptGenRandom function.

[Christian Steins]

Am 08.12.2016 um 08:25 schrieb Öö Tiib:

>>> std::random_device is not guaranteed to use a genuinely random source
>>> and may yield the same sequence every time.

>> Ok, and by checking rd.entropy() I can find out if it's a real random
>> device (entropy > 0) or not.

> If you want slightly less predictable seeds than time then Windows API
> contains a CryptGenRandom function.

Thanks, but this is not portable.

Yesterday I tested:

unsigned int seed; // uninitialized stack variable
seed = seed + reinterpret_cast<size_t> (&seed); // add it's address
seed = seed + time(0); // add current time

Very ugly, but it works.

Christian

[Ben Bacarisse]

Christian Steins <cs...@quantentunnel.de> writes:

> Am 08.12.2016 um 08:25 schrieb 嘱 Tiib:
>
>>>> std::random_device is not guaranteed to use a genuinely random source
>>>> and may yield the same sequence every time.
>
>>> Ok, and by checking rd.entropy() I can find out if it's a real random
>>> device (entropy > 0) or not.
>
>> If you want slightly less predictable seeds than time then Windows API
>> contains a CryptGenRandom function.
>
> Thanks, but this is not portable.
>
> Yesterday I tested:
>
> unsigned int seed; // uninitialized stack variable
> seed = seed + reinterpret_cast<size_t> (&seed); // add it's address
> seed = seed + time(0); // add current time

The fact that seed is a stack variable suggests that you are re-seeding
the generator with every call. That's going to undo all the good work
the authors of the generator put in to make the results pseudo-random.

You might want to consider using a high-resolution timer from
std::chrono.

--
Ben.

[Öö Tiib]

On Thursday, 8 December 2016 11:09:32 UTC+2, Christian Steins wrote:
> Am 08.12.2016 um 08:25 schrieb Öö Tiib:
>
> >>> std::random_device is not guaranteed to use a genuinely random source
> >>> and may yield the same sequence every time.
>
> >> Ok, and by checking rd.entropy() I can find out if it's a real random
> >> device (entropy > 0) or not.
>
> > If you want slightly less predictable seeds than time then Windows API
> > contains a CryptGenRandom function.
>
> Thanks, but this is not portable.

When there are no portable solutions then it is usually good idea to
look for platform-specific solutions.

>
> Yesterday I tested:
>
> unsigned int seed; // uninitialized stack variable
> seed = seed + reinterpret_cast<size_t> (&seed); // add it's address
> seed = seed + time(0); // add current time
>
> Very ugly, but it works.

That I would not use. Lot of undefined behaviors seem to work
until most embarrassing situation. Next version of gcc may
optimize it into 'unsigned int seed = 42;' and that may cause
major stakeholder to lose pile of money. Who to blame?

[Ben Bacarisse]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> writes:

>>Christian Steins <cs...@quantentunnel.de> writes:
>>> unsigned int seed; // uninitialized stack variable
>>> seed = seed + reinterpret_cast<size_t> (&seed); // add it's address
>>> seed = seed + time(0); // add current time
>>The fact that seed is a stack variable suggests that you are re-seeding
>>the generator with every call. That's going to undo all the good work
>>the authors of the generator put in to make the results pseudo-random.
>>You might want to consider using a high-resolution timer from
>>std::chrono.
>

> What I show in the classroom is:
>
> ::std::srand
> ( ::std::time( 0 )* ::std::time( 0 )+ ::std::time( 0 ));
>
> so as to shift some of the variation from the least-
> significant digits of the time to some more significant
> digits of the result.

And thereby introducing some predictable structure into the seed (for
example the bottom bit in now known with high probability). What
evidence so you have that is generally a good thing to do?

> And then
>
> ::std::rand(); ::std::rand(); ::std::rand();
>
> to throw away the first values of »rand()«
> which might be related to the seed in an
> obvious manner.

That seems odd too. The all of the values of std::rand() are probably
related to the seed in an obvious way. They certainly are in the case
being discussed.

> We now have ::std::filesystem, and it might be possible
> to get some entropy from there (for example, from struct
> space_info).

Presumably it's optional. Is there a portable way to test if it's
available?

--
Ben.

[Alf P. Steinbach]

On 08.12.2016 14:07, Stefan Ram wrote:

> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>>> What I show in the classroom is:
>>> ::std::srand
>>> ( ::std::time( 0 )* ::std::time( 0 )+ ::std::time( 0 ));
>>> so as to shift some of the variation from the least-
>>> significant digits of the time to some more significant
>>> digits of the result.
>> And thereby introducing some predictable structure into the seed (for
>> example the bottom bit in now known with high probability). What
>> evidence so you have that is generally a good thing to do?
>

> I did not claim that it is /generally good/.
> But when one just does
>
> ::std::srand( ::std::time( 0 )); ::std::cout << ::std::rand();
>
> , one can see that the value printed one second later
> (when the whole program is being started anew)
> is near to the value printed one second earlier.
> E.g., subsequent runs of the program might print
> 5811, 5912, and 5984. The multiplication will make
> this obvious correlation disappear (under many
> implementations).

You're seeing the time values. Just advance the generator one number.
Successive pseudo-random numbers have no easily discernible relation to
each other.


> The above multiplication makes this effect disappear
> /in the course room/ so the participiants can see that
> they can exert some control over it. I do not claim
> that this is generally a good thing - generally one would
> not use »::std::rand()« at all!

>
>> That seems odd too. The all of the values of std::rand() are probably
>> related to the seed in an obvious way.
>

> It has the same effect of making the obvious correlation
> go away.
>
> In the course room, the participiants are always like,
> "But those values all are near to each other!«, and I
> want to show them that it is possible to change this.

I recommend Knuth's “The Art of Computer Programming”, I think it was vol I.

Well, that's the only book about random generators I can recommend,
because it's they only one I've read. :)


Cheers & hth.,

- Alf

[Ben Bacarisse]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>>>What I show in the classroom is:
>>>::std::srand
>>>( ::std::time( 0 )* ::std::time( 0 )+ ::std::time( 0 ));
>>>so as to shift some of the variation from the least-
>>>significant digits of the time to some more significant
>>>digits of the result.
>>And thereby introducing some predictable structure into the seed (for
>>example the bottom bit in now known with high probability). What
>>evidence so you have that is generally a good thing to do?
>

> I did not claim that it is /generally good/.

OK, but that was very far from clear. I tried, wherever possible, to
show general solutions in the classroom so it seemed to me you might be
showing this because you think it is generally a good idea.

> But when one just does
>
> ::std::srand( ::std::time( 0 )); ::std::cout << ::std::rand();
>
> , one can see that the value printed one second later
> (when the whole program is being started anew)
> is near to the value printed one second earlier.
> E.g., subsequent runs of the program might print
> 5811, 5912, and 5984. The multiplication will make
> this obvious correlation disappear (under many
> implementations).
>

> The above multiplication makes this effect disappear
> /in the course room/ so the participiants can see that
> they can exert some control over it. I do not claim
> that this is generally a good thing - generally one would
> not use »::std::rand()« at all!

One should not used rand if it's that bad. There's nothing wrong with
using it if your library has a good implementation.

>>That seems odd too. The all of the values of std::rand() are probably
>>related to the seed in an obvious way.
>

> It has the same effect of making the obvious correlation
> go away.
>
> In the course room, the participiants are always like,
> "But those values all are near to each other!«, and I
> want to show them that it is possible to change this.

There is another good teaching point here -- beware of replacing an
obvious correlation with a non-obvious correlation. In some situations
the latter is more dangerous because it might hide the use of bad
generator.

--
Ben.

[bartekltg]

On 07.12.2016 22:21, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Ben Bacarisse <ben.u...@bsb.me.uk> spake the secret code
> <87oa0ne...@bsb.me.uk> thusly:
>
>> The simplest solution is to delete that line and seed the mt19937
>> object with the time. You should only seed a generator once, so you
>> need to make the mt19937 object static:
>
> Nit: static objects like this make unit testing more difficult.

Do you prefer a global mt19937 object? ;>

bartekltg

[bartekltg]

On 07.12.2016 22:14, Ben Bacarisse wrote:

>
> std::random_device is not guaranteed to use a genuinely random source
> and may yield the same sequence every time.
>
> The simplest solution is to delete that line and seed the mt19937
> object with the time. You should only seed a generator once, so you
> need to make the mt19937 object static:
>
>> std::mt19937 gen(rd());
>
> static std::mt19937 gen(std::time(0));

You can meet in the middle,
std::random_device rd;
static std::mt19937 gen(rd() + std::time(0));

or something like:

auto t = std::chrono::high_resolution_clock::now();
std::chrono::time_point<std::chrono::high_resolution_clock> now() ;
static std::mt19937 gen2(rd() + t.time_since_epoch().count());

If random_device works, we have good seed, an addition would not break
it ( probably... No one can be sure that his random_device do not
terurn - std::time(0) ;-) and if it didn't work, seed still isn't
constant.


bartekltg

[Christian Steins]

Am 09.12.2016 um 02:24 schrieb bartekltg:

> You can meet in the middle,
> std::random_device rd;
> static std::mt19937 gen(rd() + std::time(0));

Simple and good solution.

Until a get_seed() or something is added to the STL.

Christian

[Richard]

[Please do not mail me a copy of your followup]

bartekltg <bar...@gmail.com> spake the secret code
<o2d0a3$dfl$1...@gioia.aioe.org> thusly:

Perhaps, it depends on the situation.

A scoped static is essentially a global variable that you can't access
from outside that scope. This means that in a unit test scenario
you have no way in which you can reset this state. Therefore you
can't write a repeatable test of any code that is calling the
generator. The local statics are hidden global state.

Global state makes unit testing difficult.

The typical solution is to use dependency injection in order to allow
the code to be repeatably tested. In this case, injecting the
dependent state of the random number generator would solve the problem
and make the code testable. So yes, a global variable that is injected
by the caller would make this code more testable.

You can achieve the same end-user API by making a simple delegating
function that injects the global state and forwards any other
arguments. This frees callers from having to know about this global
state and the delegated function can still be unit tested.

[Richard]

[Please do not mail me a copy of your followup]

(Richard) legaliz...@mail.xmission.com spake the secret code
<o29uhk$5gr$1...@news.xmission.com> thusly:

>Nit: static objects like this make unit testing more difficult.

Also nit: they can lead to difficult bugs in multi-threaded code.

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> [...]

>
> I recommend Knuth's "The Art of Computer Programming", I think it

> was vol I. [on random number generators]

The chapter on random numbers is in TAOCP vol. II, "Seminumerical
Algorithms".

But vol. I does discuss threaded trees. :)