Boost logo

Boost :

From: Peter Dimov (pdimov_at_[hidden])
Date: 2007-06-05 07:23:54


Jos Hickson wrote:
> On 04/06/07, Andy <atompkins_at_[hidden]> 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".


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk