-
March 10th, 2015, 03:55 AM
#1
Seeding a C++11 random
I was wondering if there was a recommendation in regards to seeding C++11 randoms.
The thing is that C-rand can be seeded with time, as it is a global random that only gets seeded once (though even then, arguably, that's a low quality seed).
C++11 randoms are instantiated on demand, so using raw time is dangerous, should two randoms be initialized in very quick succession. What you'd usually want to do is keep some sort of utility that can take a seed (such as time) and further hack it with some sort of global, to make sure that there is never duplicate seeding. For example, this is how java default initializes its randoms.
Currently, I'm doing something like:
default_random_engine generator{random_device{}()};
This *should* be good enough, but I'm not quite comfortable with this solution, as I don't know how fully portable random_device is. Nor do we the quality of its entropy.
How would you recommend seeding a C++11 random?
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
March 10th, 2015, 05:18 AM
#2
Re: Seeding a C++11 random
Originally Posted by monarch_dodra
C++11 randoms are instantiated on demand
what do you mean ? random engines are not used "on demand", at least not necessarily; you can use it as any other variable carring state ( can be local, static , global, whatever ), nothing stops you from seeding and using it as you did with rand().
Originally Posted by monarch_dodra
Currently, I'm doing something like:
default_random_engine generator{random_device{}()};
This *should* be good enough, but I'm not quite comfortable with this solution, as I don't know how fully portable random_device is. Nor do we the quality of its entropy.
random_device is designed to be a replacement for hand-crafted possibly-horrible-time-whatever-based seeds, so I think it is the raccomended way for a general purpose user-pov-unpredictable seeding. You'll get an exception if unsupported ( that is, almost nowhere in "consumer" oriented devices, being it allowed to be a simple rng ), and you can check entropy()==0 to discriminate between non/determinsitic sources, provided such a thing makes sense; note that a non-deterministic engine has not necessarily a better "quality" than a deterministic one.
The point is that proper seeding is the exact reason why std::random_device was introduced in the first place, and it's explicitly used in tutorials written by the very authors of <random> for this purpose.
Yes, unpredictability with respect to a malicious attacker is a totally another story, but then you'll need specially crafted engines anyway ( and possibly special hardware if you are really paranoic ).
Moreover, if you need a big number of random engine ( do you ? ) you can pass a full seed sequence to the engine to exploit the full engine state space; of course, the "quality" of this will be engine dependent though ... the purpose of seeding is not to have "better" randomness, this is a responsability of the engine/distribution that in turn specifies how seeding affects its state and the mutual statistical properties of differently seeded engine instances ...
-
March 10th, 2015, 05:28 AM
#3
Re: Seeding a C++11 random
Originally Posted by monarch_dodra
How would you recommend seeding a C++11 random?
You could have a Singleton with a seed function. The first time it's called it returns a seed number based on the system clock. All subsequent calls return the previous seed number + 1.
-
March 10th, 2015, 05:34 AM
#4
Re: Seeding a C++11 random
Interesting. Empirical testing seems to indicate that the first random number generated after the seed has been refreshed using random_device() will be the same as a previously first generated number in approx 0.023% of the time when undertaken in a tight loop.
Code:
#include <random>
#include <unordered_set>
#include <iostream>
#include <iomanip>
using namespace std;
const unsigned long RNDNUMBS = 1000000;
int main()
{
unordered_set<unsigned long> rnd;
unsigned long cnt = 0;
for (unsigned long i = 0; i < RNDNUMBS; ++i) {
default_random_engine generator{random_device{}()};
if (rnd.insert(generator()).second == false)
++cnt;
}
cout << "found " << cnt << " dulicate initial rnd from a sample of " << RNDNUMBS << " (" << fixed << setprecision(3) << ((double)cnt / RNDNUMBS) * 100.0 << "%)" << endl;
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 10th, 2015, 05:46 AM
#5
Re: Seeding a C++11 random
Originally Posted by razzle
You could have a Singleton with a seed function. The first time it's called it returns a seed number based on the system clock. All subsequent calls return the previous seed number + 1.
Changing to using that for the code in post #4 reduces the %sameness to approx 0.012%.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 10th, 2015, 06:16 AM
#6
Re: Seeding a C++11 random
This program was compiled for 32 bit running on a 64 bit Windows 7.
Compiling the program for 64 bit using a type of unsigned long long doesn't change the results.
Increasing the sample size by a factor of 10 also increases the duplicate % by a factor of approx 10.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 10th, 2015, 06:27 AM
#7
Re: Seeding a C++11 random
ok, but you should also check the number of bits in the result type of the engine;
moreover, note that that probability is not small at all ( is a variant of the good ol birthday paradox ):
indeed, the expected count of duplicates in a sequence of one million indipendent numbers uniformly distributed in [0,2^32-1] is approximately 1000000^2 / 2^32 that is 0.023... %
( sorry for the previously deleted post, as I misread your post initially )
-
March 10th, 2015, 07:03 AM
#8
Re: Seeding a C++11 random
Originally Posted by 2kaud
Changing to using that for the code in post #4 reduces the %sameness to approx 0.012%.
And that corresponds very well with the number of collisions you can expect when you draw 1.000.000 numbers at random from the unsigned int range (0 through 4.294.967.295). I modified a section of your code a little like this,
Code:
//random_device generator;
default_random_engine generator;
for (unsigned long i = 0; i < RNDNUMBS; ++i) {
// default_random_engine generator{random_device{}()};
And with both random_device and default_random_engine as random number generators I got the same "sameness" value namely 0.011%
This doesn't mean of course that you should use 1 million seeds and then use only the first number of each random sequence. It would be bad but not a catastrophy.
Last edited by razzle; March 10th, 2015 at 07:05 AM.
-
March 10th, 2015, 07:39 AM
#9
Re: Seeding a C++11 random
The OP question was re initial seeding. That was why I defined generator within the loop so that it would be freshly seeded each time round the loop and the first generated number each time would be from a fresh seed.
I draw no conclusions from this - I only offered my observations for info and discussion.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 10th, 2015, 08:32 AM
#10
Re: Seeding a C++11 random
Ideally, you want to use a single seeding for your entire application. If you need multiple separate RNG's with independant seeding, then this is difficult to do in a single program without outside access.
don't use seed a single PRNG, then use it's output to seed other PRNG's, that's going to create a highly dependable set of seeds.
seeding by time is a typical case scenario and if you only need a single seed it is good enough for almost all usage scenario's. However I have seen this very scenario fail on machines without a real time clock (or with a dead RTC battery) and where the seed was initialised before the PC was synced up to network time.
clock() is worse for what should be obvious reasons
and yes, seen this happen too.
If you need more randomness, there are several webservices that offer random seeds generated by truely random hardware devices (typically radioactive decay)
don't get into one of the many pitfalls I've seen people resort to.
Process ID, thread ID etc are all going to be fairly predictable everytime your PC boots
clock(), CPU clock count, etc again, fairly predictable
system id's like CPU ID, network MAC, hard disk ID or volume id don't typically change, so while they may help to differentiate seeding between individual computer, they won't help at all for seeding everytime your app starts on a single specific computer.
short story.
time() is enough for most usage cases if you need only a single seed for your entire application, or if you need multiple but don't care much about interdependency of the seeds.
if you need better randomness (or unpredictablity rather), or more seeds and need to guarantee the seeds are independant, considier using one of the RNG webservices. you can try several in case one is down.
-
March 10th, 2015, 09:55 AM
#11
Re: Seeding a C++11 random
Originally Posted by superbonzo
what do you mean ? random engines are not used "on demand", at least not necessarily; you can use it as any other variable carring state ( can be local, static , global, whatever ), nothing stops you from seeding and using it as you did with rand().
I mean that C has a "ready to use" global PRNG that you only need to seed once for the global application. C++11 has a lot of PRNG *types* but no global PRNG for sharing.
Originally Posted by superbonzo
The point is that proper seeding is the exact reason why std::random_device was introduced in the first place, and it's explicitly used in tutorials written by the very authors of <random> for this purpose.
That is a good answer. I actually looked around, but did not find any tutorial that actually did this (though I have to admit I did not find that many tutorials either).
Originally Posted by razzle
You could have a Singleton with a seed function. The first time it's called it returns a seed number based on the system clock. All subsequent calls return the previous seed number + 1.
That is also a possibility. It doesn't play that well when trying to post a 5 line snippet to a forum though
Originally Posted by OReubens
short story.
time() is enough for most usage cases if you need only a single seed for your entire application, or if you need multiple but don't care much about interdependency of the seeds.
if you need better randomness (or unpredictablity rather), or more seeds and need to guarantee the seeds are independant, considier using one of the RNG webservices. you can try several in case one is down.
The issue with using *just* time is if you happen to seed two PRNG's at the same time (or in rapid succession), then you have high odds of seeding with the same number. I've seen this happen before, it's not pretty.
For example, in Java, when asking for a seeds are generated from a XOR of a global PRNG element and the current time.
I could implement all of that of course (not very complicated), but mostly wanted to know if there was "1 liner goto recommendation" when you want to write a small program.
So I guess using random_device is good enough.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
March 10th, 2015, 10:52 AM
#12
Re: Seeding a C++11 random
Originally Posted by monarch_dodra
I actually looked around, but did not find any tutorial that actually did this (though I have to admit I did not find that many tutorials either).
here it is: n3551
Originally Posted by monarch_dodra
I mean that C has a "ready to use" global PRNG that you only need to seed once for the global application. C++11 has a lot of PRNG *types* but no global PRNG for sharing.
if you *really want it*, it does ( and you don't even need to seed it ):
Code:
auto rand(){ static std::default_random_engine eng{ std::random_device{}() }; return e(); }
that said, I agree we'd need a quick standard way of saying "get a (properly seeded) pseudorandom integer/real from a to b" for simple program prototyping and the like ...
-
March 10th, 2015, 12:30 PM
#13
Re: Seeding a C++11 random
Originally Posted by monarch_dodra
That is also a possibility. It doesn't play that well when trying to post a 5 line snippet to a forum though
Are you sure. I think it could look quite impressive.
Code:
inline unsigned seeder() {
static unsigned seed = std::random_device{}();
return seed++;
}
-
March 10th, 2015, 01:04 PM
#14
Re: Seeding a C++11 random
Code:
auto rand(){ static std::default_random_engine eng{ std::random_device{}() }; return e(); }
This doesn't compile for me with MS VS 2013. error C3551: expected a trailing return type. Also shouldn't e() be eng()?
For me this compiles
Code:
auto rand11()->decltype(std::default_random_engine{}())
{
static std::default_random_engine eng{ std::random_device{}() };
return eng();
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 10th, 2015, 01:17 PM
#15
Re: Seeding a C++11 random
I think it could look quite impressive.
It does
Code:
inline auto seeder()->decltype(std::random_device{}())
{
static auto seed( std::random_device{}() );
return seed++;
}
inline auto rand11()->decltype(std::default_random_engine{}())
{
static std::default_random_engine eng{ seeder() };
return eng();
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|