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

[Eric Blake]

On 08/10/2012 07:47 AM, Daniel P. Berrange wrote:
> From: "Daniel P. Berrange" <berrange at 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 at redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 620 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20120810/7105f715/attachment-0001.sig>