4 ms·

There's another approach for doing this: generate a random number between 1 and 2 (they all have the same exponent) and then subtract 1 (that's the default impl

by FabHK 1y ago

There's another approach for doing this: generate a random number between 1 and 2 (they all have the same exponent) and then subtract 1 (that's the default implementation in Julia [0]). But I think it also just gives you 2^53 different numbers. So, between .5 and 1 you miss out on every second representable number, between 0.25 and .5 you miss out on 3/4 of them, and so on. I guess for many cases that's good enough, but the article seems like a nice improvement. ETA: Lemire has some thoughts on this [1] and links to what might be a prior solution [2]. Vigna (of xoroshiro fame) writes about it at the bottom of [3] and also links to [2]. So, presumably the implementation described in the article is faster? ("There have been some past attempts to fix these flaws, but none that avoid a huge performance penalty while doing so." EDIT2: BTW, one of the things I love about HN (well, the world, really) is that there are people that care deeply that we can uniformly sample floats between 0 and 1 correctly, and all of them, and do it faster. [0] see https://github.com/JuliaLang/julia/blob/master/stdlib/Random/src/generation.jl https://github.com/JuliaLang/julia/blob/master/stdlib/Random... rand(r::AbstractRNG, ::SamplerTrivial{CloseOpen01_64}) = rand(r, CloseOpen12()) - 1.0 [1] https://lemire.me/blog/2017/02/28/how-many-floating-point-numbers-are-in-the-interval-01/ https://lemire.me/blog/2017/02/28/how-many-floating-point-nu... [2] https://mumble.net/~campbell/2014/04/28/uniform-random-float https://mumble.net/~campbell/2014/04/28/uniform-random-float https://mumble.net/~campbell/2014/04/28/random_real.c https://mumble.net/~campbell/2014/04/28/random_real.c [3] https://prng.di.unimi.it https://prng.di.unimi.it

badmintonbaseba 1y ago
That looks kinda the same end result as the fixed point method, but possibly cheaper to execute.
- thaumasiotes 1y ago
  Well, it has to be. The number can only have 53 bits of precision. There are more than 2^53 floating point values between 0 and 1, but if you use them all, you'll fail to have a uniform distribution. Either certain regions of the space will be far more likely than other regions, or certain values will be far more likely than other values. The article takes the view that the second of those options is desirable, but it's not clear why. And the algorithm the article describes is: 1. Generate a random float the uniform way. 2. If it's close to zero and has extra precision available, generate some more random bits to fill in the extra precision. It's always going to be faster to skip step 2. What are we gaining by not skipping it?
  - Sharlin 1y ago
    Floats are typically used to approximate reals, a uniform distribution over individual float values is usually not what is needed. What is wanted is uniform distribution over equal-sized intervals. 2^53 equally-spaced values within [0, 1) is plenty enough for many use cases, but it's still fundamentally a set of fixed-point rather than floating-point numbers. For a true random floating-point value, all the available precision should be used such that every single value in the domain has some probability mass (except maybe subnormals, but you can usually forget about subnormals). Especially with 32-bit floats it's not that difficult to run out of precision when you start doing math and only have a fixed-point subset of size 2^23 available.
    - tialaramex 1y ago
      The floats are a surprisingly bad approximation of the reals. They're barely better than the integers, while their shortcomings are much harder to understand, so I'd say it's like if you want approximately a spaceship and you're choosing between an F-14 Tomcat and a Fiat Punto. Neither of these things is a spaceship, but, it will be obvious to almost anybody why the Punto isn't a spaceship whereas you are less likely to know enough about the F-14 to see why it's not "good enough".
      - thaumasiotes 1y ago
        > The floats are a surprisingly bad approximation of the reals. They're barely better than the integers They are integers. Each float is a pattern of 64 discrete bits. Discretion means integers.
        kbolino 1y ago
        In float32 land, if x = 0.5 (with bit pattern 0x3f000000) y = 0.25 (with bit pattern 0x3e800000) then x+y = 0.75 (with bit pattern 0x3f400000) But if we just added the bit patterns like integers, we would get 0x7d800000 (with a float value of over 10^37). Just because they are discrete doesn't mean they are integers only that they can be mapped one-to-one with integers. The bit pattern is not the semantic meaning of the value, and you cannot perform correct operations if you ignore the semantics.
david-gpu 1y ago
At some point in my career I worked on floating point hardware design, and I agree with your approach.
pclmulqdq 1y ago
That is essentially just the fixed point method mentioned here, and it is uniformly distributed across the range (and faster because you do less), but it does not fill the low bits of the number correctly (53 bits of precision != 2^53 of them between 0 and 1). If you look at the final distribution of numbers and you use under 1-10 million numbers, that method and the division method will appear to be unbiased unless you have a pathological case.

by FabHK 1y ago

badmintonbaseba 1y ago

That looks kinda the same end result as the fixed point method, but possibly cheaper to execute.

thaumasiotes 1y ago
Well, it has to be. The number can only have 53 bits of precision. There are more than 2^53 floating point values between 0 and 1, but if you use them all, you'll fail to have a uniform distribution. Either certain regions of the space will be far more likely than other regions, or certain values will be far more likely than other values. The article takes the view that the second of those options is desirable, but it's not clear why. And the algorithm the article describes is: 1. Generate a random float the uniform way. 2. If it's close to zero and has extra precision available, generate some more random bits to fill in the extra precision. It's always going to be faster to skip step 2. What are we gaining by not skipping it?
- Sharlin 1y ago
  Floats are typically used to approximate reals, a uniform distribution over individual float values is usually not what is needed. What is wanted is uniform distribution over equal-sized intervals. 2^53 equally-spaced values within [0, 1) is plenty enough for many use cases, but it's still fundamentally a set of fixed-point rather than floating-point numbers. For a true random floating-point value, all the available precision should be used such that every single value in the domain has some probability mass (except maybe subnormals, but you can usually forget about subnormals). Especially with 32-bit floats it's not that difficult to run out of precision when you start doing math and only have a fixed-point subset of size 2^23 available.
  - tialaramex 1y ago
    The floats are a surprisingly bad approximation of the reals. They're barely better than the integers, while their shortcomings are much harder to understand, so I'd say it's like if you want approximately a spaceship and you're choosing between an F-14 Tomcat and a Fiat Punto. Neither of these things is a spaceship, but, it will be obvious to almost anybody why the Punto isn't a spaceship whereas you are less likely to know enough about the F-14 to see why it's not "good enough".
    - thaumasiotes 1y ago
      > The floats are a surprisingly bad approximation of the reals. They're barely better than the integers They are integers. Each float is a pattern of 64 discrete bits. Discretion means integers.
      - kbolino 1y ago
        In float32 land, if x = 0.5 (with bit pattern 0x3f000000) y = 0.25 (with bit pattern 0x3e800000) then x+y = 0.75 (with bit pattern 0x3f400000) But if we just added the bit patterns like integers, we would get 0x7d800000 (with a float value of over 10^37). Just because they are discrete doesn't mean they are integers only that they can be mapped one-to-one with integers. The bit pattern is not the semantic meaning of the value, and you cannot perform correct operations if you ignore the semantics.

david-gpu 1y ago

At some point in my career I worked on floating point hardware design, and I agree with your approach.

pclmulqdq 1y ago

That is essentially just the fixed point method mentioned here, and it is uniformly distributed across the range (and faster because you do less), but it does not fill the low bits of the number correctly (53 bits of precision != 2^53 of them between 0 and 1). If you look at the final distribution of numbers and you use under 1-10 million numbers, that method and the division method will appear to be unbiased unless you have a pathological case.