4 ms·

There'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

by ZoFreX 12y ago

There'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 ago
Now 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 ago
  In 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 ago
    The 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 ago
If 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 ago
  Interesting, I'll test this. Thanks! Btw, what is the advantage of this over dividing? Is it faster, does it give better distribution?
  - lmm 12y ago
    It should be faster than dividing. It will give you a uniform distribution over some (but not all) of the representable values between 0.0 and 1.0 (there are as many representable values between e.g. 0.25 and 0.5 as there are between 0.5 and 1.0, so a uniform distribution over representable values probably isn't what you want), which is probably as good as you can do.

by ZoFreX 12y ago

mjevans 12y ago

Now 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 ago
In 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 ago
  The 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 ago

If 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 ago
Interesting, I'll test this. Thanks! Btw, what is the advantage of this over dividing? Is it faster, does it give better distribution?
- lmm 12y ago
  It should be faster than dividing. It will give you a uniform distribution over some (but not all) of the representable values between 0.0 and 1.0 (there are as many representable values between e.g. 0.25 and 0.5 as there are between 0.5 and 1.0, so a uniform distribution over representable values probably isn't what you want), which is probably as good as you can do.