3 ms·

> but if you use them all, you'll fail to have a uniform distribution Only if you generate them all with equal probability.

thaumasiotes 1y ago
Did you read the rest of my comment? You can't have a uniform distribution no matter what.
- camel-cdr 1y ago
  Ah, sorry I didn't see the "or certain values will be far more likely than other values". But I don't understand why that wouldn't fall under the definition of a uniform distribution. The way I would define a uniform distribution is the following: For any two floating-point numbers, r1 and r2, which form the range [r1,r2] over the real numbers, and any second pair of floating point numbers s1 and s2, which form a range [s1,s2] over the real numbers, which is contained in [r1,r2]. The probability of getting a result in [s1,s2] when sampling from [r1,r2] must be equivalent to the result of (s2-s1)/(r2-r1) with infinite precision. This is obviously possible to achieve.
  - thaumasiotes 1y ago
    Given a uniform distribution over an interval (α, β) and a tolerance ε, sample the distribution twice. What is the probability that |x_1 - x_2| < ε?
darkmighty 1y ago
Indeed, there's a simple algorithm using interval arithmetic to do so (within bounded time too!). Think of it as binary subdivision/search of [0,1], using a stream of random bits. Steps: (1) Divide the current interval in 2 (using its midpoint); (2) Using one random bit, pick one of the 2 intervals; (3) if the picked interval (new current interval) lies entirely on the domain of a single floating point value[def1], stop and return this value, else go to (1). [def1] The domain associated to a floating point value is the interval between the midpoint between it and its lower neighbor on the left, and the midpoint between it and its higher neighbor on the right. I expect the performance is very poor, but it does cover all floating point numbers in [0,1] with exactly correct probabilities (assuming the bit probabilities are exactly correct). That's in part because naively you need higher precision arithmetic to do so, as well as up to 53 or so iterations, on average well over 32 I presume. (I've left out the proof that probabilities are correct, but I believe it's easy to show)
- corsix 1y ago
  You can start with this idea, and then make it _very_ performant by using bit counting instructions. See https://www.corsix.org/content/higher-quality-random-floats https://www.corsix.org/content/higher-quality-random-floats for an exposition.

thaumasiotes 1y ago

Did you read the rest of my comment? You can't have a uniform distribution no matter what.

camel-cdr 1y ago
Ah, sorry I didn't see the "or certain values will be far more likely than other values". But I don't understand why that wouldn't fall under the definition of a uniform distribution. The way I would define a uniform distribution is the following: For any two floating-point numbers, r1 and r2, which form the range [r1,r2] over the real numbers, and any second pair of floating point numbers s1 and s2, which form a range [s1,s2] over the real numbers, which is contained in [r1,r2]. The probability of getting a result in [s1,s2] when sampling from [r1,r2] must be equivalent to the result of (s2-s1)/(r2-r1) with infinite precision. This is obviously possible to achieve.
- thaumasiotes 1y ago
  Given a uniform distribution over an interval (α, β) and a tolerance ε, sample the distribution twice. What is the probability that |x_1 - x_2| < ε?

darkmighty 1y ago

Indeed, there's a simple algorithm using interval arithmetic to do so (within bounded time too!). Think of it as binary subdivision/search of [0,1], using a stream of random bits. Steps: (1) Divide the current interval in 2 (using its midpoint); (2) Using one random bit, pick one of the 2 intervals; (3) if the picked interval (new current interval) lies entirely on the domain of a single floating point value[def1], stop and return this value, else go to (1). [def1] The domain associated to a floating point value is the interval between the midpoint between it and its lower neighbor on the left, and the midpoint between it and its higher neighbor on the right. I expect the performance is very poor, but it does cover all floating point numbers in [0,1] with exactly correct probabilities (assuming the bit probabilities are exactly correct). That's in part because naively you need higher precision arithmetic to do so, as well as up to 53 or so iterations, on average well over 32 I presume. (I've left out the proof that probabilities are correct, but I believe it's easy to show)

corsix 1y ago
You can start with this idea, and then make it _very_ performant by using bit counting instructions. See https://www.corsix.org/content/higher-quality-random-floats https://www.corsix.org/content/higher-quality-random-floats for an exposition.