5 ms·
The only part of this I care about right now is the random number generation. It looks good. Pity there's no way to get a float though, for a drop-in drand repl
by ZoFreX 12y ago
The only part of this I care about right now is the random number generation. It looks good. Pity there's no way to get a float though, for a drop-in drand replacement.
- TillE 12y agoGenerate 8 random bytes, shove them in an unsigned 64-bit int, then divide that number by 2^64 - 1. I assume that's what any function which returns a random value between 0.0 and 1.0 is actually doing.
- mjevans 12y agoIt would probably be faster to directly 'hack' a raw IEEE 754 floating number: http://en.wikipedia.org/wiki/IEEE_754-1985 http://en.wikipedia.org/wiki/IEEE_754-1985 The helpful Examples section already contains the numbers 0 and 1. Let us assume that the output is supposed to be between 0 and 1; it seems that 0 should be inclusive and 1 exclusive for the most balanced 'quick' output. Those two numbers have the leading binary format: 0 (8 or 11 bits exponent) (23 or 52 bits fraction) For either 32 or 64 bit floats. Thus for a float (32 bit): 0 0 (7 bits) (23 bits) 30 bits of randomness are necessary, HOWEVER 0 01111111 is already one when the fraction is all 0s. The easiest solution I can see is to evenly drop some precision: A reference for the casting procedure: http://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code http://en.wikipedia.org/wiki/Fast_inverse_square_root#Overvi... Pseudo: uint32 randomNumber; ... set the random somehow, maybe rand() maybe /dev/urandom etc ... randomNumber &= 0x3F7FFFFF; return * (float *) &randomNumber;
- ZoFreX 12y agoThere's a really big problem with dumping random bytes straight into a float, which is that you'll end up with a distribution that, while random, is not linear - i.e. the chance of it being between 0 and 0.5 will not be the same as the chance of it being between 0.5 and 1.0. This is because the gaps between representable numbers increases as the magnitude increases, i.e. there are "more numbers" between 0 and 1 than 100 and 101. The best technique I've found (so far) is to dump the bytes into an int, and divide.
- mjevans 12y agoNow that you mention it, that would also be an issue for the technique you describe; specifiable to the rounding characteristics for truncated numbers. It's probably a better design idea to have a predictable sequence of float (like, application dependent) results and randomly select from within said sequence.
- ZoFreX 12y agoIn my (naive and possibly flawed) tests, the division method is giving uniformly distributed results. Can you explain more what the limitations of that approach are?
- lmm 12y agoThe default rounding method is round-to-even, so e.g. 0.9999999 would be expected to come up slightly more often than 0.99999994 (the last two floats smaller than 1). Being more precise would probably require thinking about all the possible int values.
- gjm11 12y agoIf you put 0 (i.e., plus) in the sign bit, and 1023 (i.e., zero) in the exponent field, and 52 random bits in the fraction field, of an IEEE double, then you get a number between 1 (inclusive) and 2 (exclusive); the representable numbers in that range are evenly spaced, and if your random bits are good then they are all equally likely, so you've got a uniform random number between 1 and 2. Subtract 1 if you want a uniform random number between 0 and 1 (this doesn't lose information; if a number between 1 and 2 is representable, subtracting 1 yields a representable number). If your machine happens to work the same way as mine, the following will do it (unportable, untested, yadda yadda): double randomDouble() { uint64_t bits = random64bits(); bits &= ~(3ull<<62); // clear sign and MSB of expt bits |= (1023ull<<52); // rest of exponent is 1-bits return (*(double*)&bits) - 1; }
- ZoFreX 12y agoInteresting, I'll test this. Thanks! Btw, what is the advantage of this over dividing? Is it faster, does it give better distribution?
- ZoFreX 12y agoI'm dividing by UULONG_MAX + 1.0, because it expects a number between 0 (inclusive) and 1.0 (exclusive). I'm not sure how portable it is though.
- sarciszewski 12y agoOpen an issue on GitHub?
- dbaupp 12y agoHow often do you need cryptographically secure random floats? (I'm genuinely interested in the use cases.)
- ZoFreX 12y agoI don't think it would be a common use-case when creating new software, but when patching legacy software to use better RNGs it's not unheard of for them to be using older RNGs that return a float between 0 and 1 (drand48 as an example).