"Peter Dimov" <pdimov@mmltd.net> wrote in news:013b01c7a6cf$feb64e30$6407a80a@pdimov2:

Andy wrote:

...

4. Use the current seed as the random numbers directly. Will this solution provide 'good' uuids? That is, is this source of random numbers good enough?

You'll need to perform statistical tests to be sure, but:

1. On POSIX systems where /dev/urandom is available, it should be close to the best, at least in theory;

2. Under a typical use case where the application only generates one UUID, it should be as good as any other RNG seeded with its entire state, and should be better than a RNG seeded with a 32 bit seed;

3. In the multiple UUIDs case, I expect it to be competitive with any RNG, even though it only keeps 160 bits of state (another 160 bits - the old value of 'rd' - can also contribute, depending on the compiler and the use pattern).

Thanks! This is the assurance I needed. Andy.

Janek Kozicki wrote:

Andy said: (by the date of Mon, 4 Jun 2007 20:32:35 +0000 (UTC))

...

"Peter Dimov" <pdimov@mmltd.net> wrote in news:013b01c7a6cf$feb64e30$6407a80a@pdimov2:

...

Andy wrote:

Thanks! This is the assurance I needed.

Andy, that's the opinion of one person.

It is more than opinion, although it would certainly help if a probability/stats expert takes a look at the code.

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

Jos Hickson wrote:

...

On 04/06/07, Andy <atompkins@fastmail.fm> wrote:

...

I am favoring number 4, unless it will not produce good uuids. Then I favor number 5.

I guess I am looking for direction as to how to proceed.

Andy.

I prefer number 5. All you need do then is provide a get_seed() method that generates a decent seed; with number 4 it might well take a lot more time to implement and test a good source of random numbers and then it might add a extra dimension to maintaining the library. It seems to me that Boost.Random exists then it should be used by default as the source of random number generators unless, of course, what it provides is not good enough but I presume that is not the case.

Number 5 is a good solution for batch UUID generation, assuming that the RNG is seeded well.

That said, I should note that a RNG is not really a source of randomness. Sure, it can be used to produce a sequence that appears sufficiently random for most computing purposes. For UUID generation, however, and specifically in the "one UUID per program" case, a RNG contributes exactly zero random bits. If you have a seed that contains K bits of entropy, and you generate from that seed an UUID by using a RNG, the UUID will contain exactly K bits of entropy. To put it differently, the probability that two seeds collide - 2^-K - is equal to the probability that two UUIDs collide, because equal seeds generate equal UUIDs.

In other words, if you have a "decent" 32 bit seed, you're looking at 2^-32 probability of collisions, no matter how many RNGs you use as an intermediate layer. If you have a decent 128 bit seed, you can use it as an UUID as is, and passing it through a RNG will not change anything. And conversely, if you don't have a good source of randomness to use as a seed, you will not be able to generate a good UUID, so it's not possible to eliminate the "extra dimension".

Understood. However, if the best implementation of uuid::create() depends on which of two usage patterns is assumed ("batch" or "one per program") maybe a better approach is to have both uuid_generator (for batch purposes) and uuid::create() (for the one-per-program usage) with the generator seeded using the randomness that uuid::create() uses. Jos

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

Jos Hickson wrote:

...

Understood. However, if the best implementation of uuid::create() depends on which of two usage patterns is assumed ("batch" or "one per program") maybe a better approach is to have both uuid_generator (for batch purposes) and uuid::create() (for the one-per-program usage) with the generator seeded using the randomness that uuid::create() uses.

We can consider dropping the two forms of uuid::create entirely and only provide uuid_generator. The discussion has demonstrated that they have some non-obvious pitfalls (one is slower than expected, the other assumes that the user has supplied a good seed and this is unlikely).

class uuid_generator { unsigned rd_[5]; mt19937 en_;

uuid_generator() { init rd_; seed en_ with rd_[4]; }

operator() { generate a 128-bit number using en_; xor it with rd_[0..3]; return a uuid based on it; } };

seems to address both issues.

Yes, that's probably a better idea but if both versions of create() are dropped then should there be some means of providing a different engine for those who really want to? Jos

Andy wrote: ...

template <typename Engine>

We can supply a default here: template<class Engine = mt19937> It's still slightly less convenient to use uuid_generator<> g; and I'm not quite sure why one would want to replace the default engine, but it's good enough, I guess.

class uuid_generator { unsigned rd_[5]; Engine en_;

uuid_generator() { init rd_; seed en_ with rd_[4]; }

uuid operator() { generate a 128-bit number using en_; xor it with rd_[0..3]; return a uuid based on it; } };

But, how does the xor part help? It is just for the case where we are only producing one uuid?

The xor part just varies the sequence produced by the RNG by rd_[0..3]. The RNG seeded by the 32-bit value rd_[4] can produce 2^32 distinct UUID sequences. With the xor part - and assuming that the contents of rd_[] are random for simplicity - it will produce 2^32 * 2^128 distinct UUID sequences. The statistical properties of the UUID sequence will still correspond to the original 2^32 source, but this doesn't matter for our purposes since UUID's or their bits are not cross-checked for correlations with one another, only collisions matter. In short, the above is a relatively easy way to approximate a RNG seeded with the entire contents of rd_ instead of throwing 4/5 of it away. You said earlier that you had a problem with the iterator range seed, and if Engine is a template parameter, we probably need to support engines that only take a 32 bit seed anyway. It also has the advantage of being "obviously" at least as random as just using the Engine, so this should help alleviate people's concerns. :-)

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

and I'm not quite sure why one would want to replace the default engine, but it's good enough, I guess.

uuid_generator<random_device> seems like a reasonable desire to me, particularly if someone implemented it for windows (using RtlGenRandom as was mentioned in the other thread, perhaps). ~ Scott McMurray

Jos Hickson wrote:

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

...

[snip] ... and if Engine is a template parameter, we probably need to support engines that only take a 32 bit seed anyway.

Isn't it the case that the maximum seed size is related (equal?) to the difference between the max and min values produced by a particular engine and also that all the engines in Boost Random provide the iterator version of seed?

The seed for mt19937 is 624 words.

"Jos Hickson" <jos.hickson@gmail.com> wrote in news:fc03d05a0706060823v59628c64xd1bcda61e9fd5f48@mail.gmail.com:

On 06/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

...

Jos Hickson wrote:

...

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

...

[snip] ... and if Engine is a template parameter, we probably need to support engines that only take a 32 bit seed anyway.

Isn't it the case that the maximum seed size is related (equal?) to the difference between the max and min values produced by a particular engine and also that all the engines in Boost Random provide the iterator version of seed?

The seed for mt19937 is 624 words. Aah, a bit bigger then!

I have been thinking about this for awhile now, and maybe I should use Peter's suggestion and only support random number generators that can be seeded with a single number. And xor with rd_. I have been playing with another solution. I wrapped the seed function in a class that models the random number generator concept. Then used Boost.Iterators' function output iterator, and feed it into the seed function that takes iterators of the random number generator. // not that this is not quite complete class seed_rng { public: seed_rng() : rd_index_(5) {} unsigned operator()() { if (rd_index_ >= 5) { sha1_random_digest_(); // fill rd_ with new data rd_index_ = 0; } return rd_[rd_index_++]; } private: sha1_random_digest_(); unsigned rd_[5]; int rd_index_; }; template <typename Engine=boost::mt19937> class uuid_generator { public: uuid_generator() { boost::seed_rgn e; boost::generator_iterator<boost::seed_rng> begin(&e); boost::generator_iterator<boost::seed_rnd> end; en_.seed(begin, end); } boost::uuid operator()() { // get random data from en_ // return uuid based on this data } private: Engine en_; }; Now this works fine, the slow seed_rng is used to fully seed the random number generator used. It can be specialized for boost::random_device since boost::random_device does not have a seed function. Andy.

On 11/06/07, Andy <atompkins@fastmail.fm> wrote:

"Jos Hickson" <jos.hickson@gmail.com> wrote in news:fc03d05a0706060823v59628c64xd1bcda61e9fd5f48@mail.gmail.com:

...

On 06/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

...

Jos Hickson wrote:

...

On 05/06/07, Peter Dimov <pdimov@mmltd.net> wrote:

...

[snip] ... and if Engine is a template parameter, we probably need to support engines that only take a 32 bit seed anyway.

Isn't it the case that the maximum seed size is related (equal?) to the difference between the max and min values produced by a particular engine and also that all the engines in Boost Random provide the iterator version of seed?

The seed for mt19937 is 624 words. Aah, a bit bigger then!

I have been thinking about this for awhile now, and maybe I should use Peter's suggestion and only support random number generators that can be seeded with a single number. And xor with rd_.

IMHO such a restriction would be to the detriment of the library whereas the solution below would seem a lot better to me. Really what we need is a Boost.Seed library to compliment Boost.Random so that anybody like yourself using the latter doesn't have to spend all this time wondering how to seed things generically.

I have been playing with another solution. I wrapped the seed function in a class that models the random number generator concept. Then used Boost.Iterators' function output iterator, and feed it into the seed function that takes iterators of the random number generator.

// not that this is not quite complete class seed_rng { public: seed_rng() : rd_index_(5) {}

unsigned operator()() { if (rd_index_ >= 5) { sha1_random_digest_(); // fill rd_ with new data rd_index_ = 0; } return rd_[rd_index_++]; } private: sha1_random_digest_();

unsigned rd_[5]; int rd_index_; };

template <typename Engine=boost::mt19937> class uuid_generator { public: uuid_generator() { boost::seed_rgn e; boost::generator_iterator<boost::seed_rng> begin(&e); boost::generator_iterator<boost::seed_rnd> end; en_.seed(begin, end); }

boost::uuid operator()() { // get random data from en_ // return uuid based on this data } private: Engine en_; };

Now this works fine, the slow seed_rng is used to fully seed the random number generator used. It can be specialized for boost::random_device since boost::random_device does not have a seed function.

Andy.

"Jos Hickson" <jos.hickson@gmail.com> wrote in news:fc03d05a0706120226n717d457fueca21627444a90d3@mail.gmail.com: < snip >

...

Really what we need is a Boost.Seed library to compliment Boost.Random so that anybody like yourself using the latter doesn't have to spend all this time wondering how to seed things generically.

I think that the seed class would be a good addition to Boost.Random. < snip >

...

...

template <typename Engine=boost::mt19937> class uuid_generator { public: uuid_generator() { boost::seed_rgn e; boost::generator_iterator<boost::seed_rng> begin(&e); boost::generator_iterator<boost::seed_rnd> end; en_.seed(begin, end); }

boost::uuid operator()() { // get random data from en_ // return uuid based on this data } private: Engine en_; };

Now this works fine, the slow seed_rng is used to fully seed the random number generator used. It can be specialized for boost::random_device since boost::random_device does not have a seed function.

Andy.

So now I have this, and I like it, but I have been unable to use boost::enable_if, and boost::disable_if to enable/disable the constructors.

template <typename Engine = boost::mt19937> class basic_uuid_generator { public: // only enable if engine can not be seeded // boost::random_device does not need seeding basic_uuid_generator(/*enable only if Engine=boost::random_device*/) {} // enable if engine can be seeded // seed engine basic_uuid_generator(/*enable if Engine != boost::random_device*/) { boost::seed_rgn seed; boost::generator_iterator<boost::seed_rng> begin(&seed); boost::generator_iterator<boost::seed_rng> end; en_.seed(begin, end); } // assume they have already seeded e and make a copy // maybe we should store a reference to e? explicit uuid_generator(Engine const& e) : en_(e) {} boost::uuid operator()() { ... } priavte: Engine en_; }; typedef basic_uuid_generator<> uuid_generator;

Andy wrote:

I have been playing with another solution. I wrapped the seed function in a class that models the random number generator concept. Then used Boost.Iterators' function output iterator, and feed it into the seed function that takes iterators of the random number generator.

The Boost.Random engines seem to provide a seed overload that takes a generator, so it would be easier to just use that. But you should also keep in mind that this approach will result in 125 calls to sha1_random_digest each time an uuid_generator<> is created. This might not be acceptable for the typical case where the user only needs one UUID.