CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 37
  1. #1
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    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.

  2. #2
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Seeding a C++11 random

    Quote Originally Posted by monarch_dodra View Post
    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().

    Quote Originally Posted by monarch_dodra View Post
    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 ...

  3. #3
    Join Date
    Jul 2013
    Posts
    576

    Re: Seeding a C++11 random

    Quote Originally Posted by monarch_dodra View Post
    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.

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    Re: Seeding a C++11 random

    Quote Originally Posted by razzle View Post
    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++20 Compiler: Microsoft VS2019 (16.11.5)

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  7. #7
    Join Date
    Oct 2008
    Posts
    1,456

    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 )

  8. #8
    Join Date
    Jul 2013
    Posts
    576

    Re: Seeding a C++11 random

    Quote Originally Posted by 2kaud View Post
    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.

  9. #9
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  10. #10
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    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.

  11. #11
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Seeding a C++11 random

    Quote Originally Posted by superbonzo View Post
    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.

    Quote Originally Posted by superbonzo View Post
    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).

    Quote Originally Posted by razzle View Post
    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

    Quote Originally Posted by OReubens View Post
    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.

  12. #12
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Seeding a C++11 random

    Quote Originally Posted by monarch_dodra View Post
    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

    Quote Originally Posted by monarch_dodra View Post
    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 ...

  13. #13
    Join Date
    Jul 2013
    Posts
    576

    Re: Seeding a C++11 random

    Quote Originally Posted by monarch_dodra View Post
    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++;
    }

  14. #14
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    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++20 Compiler: Microsoft VS2019 (16.11.5)

  15. #15
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,553

    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++20 Compiler: Microsoft VS2019 (16.11.5)

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured