4 ms·

I do not think there would be any bias for bounds <=2^53. (Assuming the original float is uniformly distributed in [0 1), which is fairly straightforward to en

I do not think there would be any bias for bounds <=2^53. (Assuming the original float is uniformly distributed in [0 1), which is fairly straightforward to ensure.)

Retr0id 4y ago
A uniform float in the range [0, 1) has exactly 2^53 possible values (if you generate it in any sensible way). No matter how you do it, mapping that set of values onto a range of integers, where the number of integers does not evenly divide 2^53, requires there to be a bias.
- moonchild 4y ago
  Right. I was not thinking straight.
- lifthrasiir 4y ago
  Small correction: Assuming "uniform" to mean the uniform distribution, there are actually 2^62 - 2^52 possible binary64 values in the [0, 1) range with differing probabilities. So the maximally correct implementation can't generate just a single 32-bit or 64-bit integer to generate one fp number as some numbers would have a probability much smaller than 2^64. Of course this is not how they are typically generated, nor this improves the uniformity of formulas like `Math.random() * range`.
  - Dylan16807 4y ago
    > Assuming "uniform" to mean the uniform distribution Well, yes, but a discrete/integer-ish version. Every number is equidistant and equally likely.
- orlp 4y ago
  > A uniform float in the range [0, 1) has exactly 2^53 possible values (if you generate it in any sensible way). No, there are 2^62 - 2^52 float64 values in [0, 1), so your method (which I assume is to fix the exponent at 0, randomize mantissa so we get 1.abcdef... and subtract 1) can't possible be sensible, if your sense of sensibility includes correctness. First note that the only correct way to generate a floating point in [a, b] is to generate a random number in [a, b] with infinite precision and then round it to the closest floating point number in that range. This maintains all the nice properties of real uniform generation (assuming a, b are representable floating point numbers), expectation of (a + b) / 2, continuity of ranges such that generating U[a, c] is the same as choosing between U[a, b] and U[b, c] with weights (b-a) and (c-b) respectively, etc, while having an non-zero chance of generating any floating point value in [a, b]. An efficient algorithm for generating a float in [0, 1] is described in "Generating Pseudo-random Floating-Point Values" by Allen B. Downey. Correctly implemented it uses a handful of instructions and single call to the word-sized random number generator > 99% of the time, using a count-trailing-zeros (or similar) CPU instruction to efficiently sample from an exponential distribution (as opposed to the naive loop in the paper). Note that the mathematical distributions U[0, 1) and U[0, 1] are indistinguishable. So when we say "a uniform float in the range [0, 1)" we can't possibly mean U[0, 1). What we mean in reality is something that approximates U[0, 1] but can't generate the floating point value 1.0. One decent way to do that is to sample from U[0, 1] but reject the 1.0 output. This effectively samples from U[0, 1 - eps] where eps = (1 - floatbefore(1.0)) / 2. This unfortunately does mean we lose our nice expectation of 0.5. Note that the error in expectation for sampling from [1, 2) using strictly mantissa and subtracting 1 is significantly worse. For example in a 2-bit exponent 2-bit mantissa unsigned floating point with exponent bias -1 (giving the following list of values) 0.0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, 1.0, 1.25, 1.5, 1.75, 2.0, 2.5, 3.0, 3.5 we find that sampling using Allen B. Downey's method from [0.0, 1.0] but rejecting 1.0 as output has an expectation of 0.46875, sampling uniformly from {1.0, 1.25, 1.5, 1.75} and subtracting 1 like the mantissa method would have an expectation of 0.375.
  - deleted 4y ago
    [deleted]
  - Dylan16807 4y ago
    Most of that bias boils down to the subtraction method always wasting a single bit of mantissa. Which is worth noting but also a very tiny problem to have. It doesn't make things "not sensible".

I do not think there would be any bias for bounds <=2^53. (Assuming the original float is uniformly distributed in [0 1), which is fairly straightforward to ensure.)

Retr0id 4y ago

A uniform float in the range [0, 1) has exactly 2^53 possible values (if you generate it in any sensible way). No matter how you do it, mapping that set of values onto a range of integers, where the number of integers does not evenly divide 2^53, requires there to be a bias.

moonchild 4y ago
Right. I was not thinking straight.
lifthrasiir 4y ago
Small correction: Assuming "uniform" to mean the uniform distribution, there are actually 2^62 - 2^52 possible binary64 values in the [0, 1) range with differing probabilities. So the maximally correct implementation can't generate just a single 32-bit or 64-bit integer to generate one fp number as some numbers would have a probability much smaller than 2^64. Of course this is not how they are typically generated, nor this improves the uniformity of formulas like `Math.random() * range`.
- Dylan16807 4y ago
  > Assuming "uniform" to mean the uniform distribution Well, yes, but a discrete/integer-ish version. Every number is equidistant and equally likely.
orlp 4y ago
> A uniform float in the range [0, 1) has exactly 2^53 possible values (if you generate it in any sensible way). No, there are 2^62 - 2^52 float64 values in [0, 1), so your method (which I assume is to fix the exponent at 0, randomize mantissa so we get 1.abcdef... and subtract 1) can't possible be sensible, if your sense of sensibility includes correctness. First note that the only correct way to generate a floating point in [a, b] is to generate a random number in [a, b] with infinite precision and then round it to the closest floating point number in that range. This maintains all the nice properties of real uniform generation (assuming a, b are representable floating point numbers), expectation of (a + b) / 2, continuity of ranges such that generating U[a, c] is the same as choosing between U[a, b] and U[b, c] with weights (b-a) and (c-b) respectively, etc, while having an non-zero chance of generating any floating point value in [a, b]. An efficient algorithm for generating a float in [0, 1] is described in "Generating Pseudo-random Floating-Point Values" by Allen B. Downey. Correctly implemented it uses a handful of instructions and single call to the word-sized random number generator > 99% of the time, using a count-trailing-zeros (or similar) CPU instruction to efficiently sample from an exponential distribution (as opposed to the naive loop in the paper). Note that the mathematical distributions U[0, 1) and U[0, 1] are indistinguishable. So when we say "a uniform float in the range [0, 1)" we can't possibly mean U[0, 1). What we mean in reality is something that approximates U[0, 1] but can't generate the floating point value 1.0. One decent way to do that is to sample from U[0, 1] but reject the 1.0 output. This effectively samples from U[0, 1 - eps] where eps = (1 - floatbefore(1.0)) / 2. This unfortunately does mean we lose our nice expectation of 0.5. Note that the error in expectation for sampling from [1, 2) using strictly mantissa and subtracting 1 is significantly worse. For example in a 2-bit exponent 2-bit mantissa unsigned floating point with exponent bias -1 (giving the following list of values) 0.0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, 1.0, 1.25, 1.5, 1.75, 2.0, 2.5, 3.0, 3.5 we find that sampling using Allen B. Downey's method from [0.0, 1.0] but rejecting 1.0 as output has an expectation of 0.46875, sampling uniformly from {1.0, 1.25, 1.5, 1.75} and subtracting 1 like the mantissa method would have an expectation of 0.375.
- deleted 4y ago
  [deleted]
- Dylan16807 4y ago
  Most of that bias boils down to the subtraction method always wasting a single bit of mantissa. Which is worth noting but also a very tiny problem to have. It doesn't make things "not sensible".