Re: [libvirt] [PATCH 1/8] Add virRandom() API to generate numbers with non-power-of-2 limit

On 08/10/2012 07:47 AM, Daniel P. Berrange wrote: > From: "Daniel P. Berrange" <berrange(a)redhat.com&gt; > > The current virRandomBits() API is only usable if the caller wants > a random number in the range [0, (n-1)] where n is a power of two. > This adds a virRandom() API which works for upper limits which are > not a power of two. It works by using virRandomBits() to generate > a number to the next nearest power of 2 limit, and then scales it > down. I like the idea, but NAK to this version of the patch. That algorithm is not uniform. > +/** > + * virRandom: > + * @max: Upper bound on random number (not inclusive) > + * > + * Generate an evenly distributed random number between [0,max-1] > + * If @max is a power of 2, then use virRandomBits instead > + * > + * Return: a random number with @nbits entropy > + */ > +uint64_t virRandom(unsigned long long max) > +{ > + int bits = 0; > + unsigned long long tmp = max - 1; > + uint64_t ret; > + > + while (tmp) { > + tmp >>= 1; > + bits++; > + } Slow. I would suggest using gcc's __builtin_clz (the way qemu does), except that gnulib doesn't yet have a module exposing it. I guess that means I'd better write a quick gnulib module. Once you have clz(), this is much simpler as: assert(max); bits = 64 - clz(max); > + > + ret = virRandomBits(bits); > + > + if ((1 << bits) != max) { > + double d = ret; > + d *= max; > + d /= (1 << bits); > + ret = (uint64_t)d; > + } Wrong. Consider when max == 3 (i.e. generate a random choice between 0, 1, or 2). bits is 2, so d starts as 0, 1, 2, or 3, each with 25% probability. Then after this computation: 0 -> 0*3 / 4.0 -> 0 1 -> 1*3 / 4.0 -> 0 2 -> 2*3 / 4.0 -> 1 3 -> 3*3 / 4.0 -> 2 that is, you have a 50% chance of getting 0, but only a 25% chance of getting 1 or 2 - that is not a uniform distribution. The ONLY way to do this is: do { ret = virRandomBits(bits); } while (ret >= max); Then, with the same input of max == 3, you have a 25% chance of calling virRandomBits at least twice, a 12.5% chance of calling it at least three times, and so on, but you are guaranteed that you will eventually get a result that is uniformly distributed.