[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]

*From*: Eric Blake <eblake redhat com>*To*: "Daniel P. Berrange" <berrange redhat com>*Cc*: libvir-list redhat com, Daniel J Walsh <dwalsh redhat com>*Subject*: Re: [libvirt] [PATCH 1/8] Add virRandom() API to generate numbers with non-power-of-2 limit*Date*: Fri, 10 Aug 2012 10:06:39 -0600

On 08/10/2012 09:31 AM, Daniel P. Berrange wrote: > On Fri, Aug 10, 2012 at 08:58:04AM -0600, Eric Blake wrote: >> On 08/10/2012 07:47 AM, Daniel P. Berrange wrote: >>> From: "Daniel P. Berrange" <berrange 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. >> >>> + 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); This part is independently useful, while we still discuss the algorithm; I'll have the gnulib module complete later today. >> 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. > > Hmm, it was the looping that I used originally, but I wanted to get > something that had a deterministic upper bound, instead of just a > probablistic bound. Oh, I see your point - you don't want to drag on for a long time on the rare occasions where probabilities are against you. > > The alternative I wanted to use was drand48_t() which returns a double > in the range 0.0 -> 1.0, with 48 bits of entropy. You could multiply by > 'max', and cast to int. But this isn't portable and is not fixed by > GNULIB. Might not be too hard to make drand48_r into a gnulib module (harder than clz, but not intractible, so I'll take a shot at it, but no promises). Using drand48_r does still hit non-uniformity due to rounding, but with much smaller fuzz factor (that is, instead of my example of 50/25/25, you'd be more like 25.000004, 24.999993, 24.999993), which I can live with as being in the noise. Furthermore, since it only gives 48 bits of entropy, if 'max' is larger than 1<<47 you'll have to do some legwork yourself (I'm not quite sure what that legwork involves to still be fair), so I'd feel more comfortable if we capped this function to uint32_t and require the use of powers-of-2 for anything larger than a 32-bit max. > I'm wondering if we could emulate drand48_t() ourselves by doing > something like this: > > #include <ieee754.h> > > double virRandom(void) { > union ieee754_double val; > > val.ieee.negative = 0; > val.ieee.exponent = IEEE754_DOUBLE_BIAS; > val.ieee.mantissa0 = virRandomBits(20); > val.ieee.mantissa0 = virRandomBits(32); > > return val.d - 1.0; > } No need to do that. -lm already gives us a very nice function: ldexp(). Basically, you take an integer in the range [0,1<<48), then multiply that by 2**-48 using ldexp(). -- Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org

**Attachment:
signature.asc**

**Follow-Ups**:

**References**:**[libvirt] [PATCH 0/8] Honour current process label when generating SELinux labels***From:*Daniel P. Berrange

**[libvirt] [PATCH 1/8] Add virRandom() API to generate numbers with non-power-of-2 limit***From:*Daniel P. Berrange

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

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