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>
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.
--
Eric Blake eblake(a)redhat.com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
Attachments:
- signature.asc (application/pgp-signature — 620 bytes)