3 ms·

You can apply the core ideas of Hacker's Delight to floats too. Your example problem, taken from [0]: float frand( int *seed ) { union {

You can apply the core ideas of Hacker's Delight to floats too. Your example problem, taken from [0]: float frand( int *seed ) { union { float fres; unsigned int ires; }; seed[0] *= 16807; ires = ((((unsigned int)seed[0])>>9 ) | 0x3f800000); return fres - 1.0f; } You basically assemble a float building a random mantissa and assigning the right exponent and sign bits. It's not portable, but it's a very neat trick! [0] https://iquilezles.org/www/articles/sfrand/sfrand.htm https://iquilezles.org/www/articles/sfrand/sfrand.htm*

orlp 5y ago
It's a neat trick, but can not generate all floating point values. See my other comment for that.
- torotonnato 5y ago
  If you want max entropy and normally distributed values then, I think, there's no other way to go. Nice post btw
  - orlp 5y ago
    What do you mean by "normally distributed values"? Your reply also doesn't follow a normal distribution by the way. Did you mean uniform? For uniform values there is a way to go and my other reply exactly describes how.
    - torotonnato 5y ago
      Of course, it's uniform. I always swap the two names randomly hehe. I understand your code. The difference with the snippet I posted (which, btw, is not mine) is that the difference between successive floats is always a constant, i.e. there is no rounding. It's fast, has 23 bits of entropy and it's suited for constrained platforms/small demos [0], since it can be coded with very few asm instructions. I'm not saying that your solution hasn't its merits, well done. [0] The author of the code is a known member of the demoscene
      - orlp 5y ago
        Oh, I know very well who iq is :) And for a visual demo it might make perfect sense to sacrifice completeness of a solution for speed / code size. But to me, "pick a random number from {k/2^23 : 0 <= k < 2^23, k ∈ ℕ}" and "pick a random number uniformly at random from [0, 1)" are not the same. All operations (add/sub, mul/div, sin, exp, log, etc...), with IEEE754 floats are defined using real arithmetic, and then assumed to round to the nearest representable floating point value. I don't see why random number generation, at least as a default before micro-optimizing, should be any different.
        torotonnato 5y ago
        You are right, I was uncomfortable with the uneven density of the floats approaching zero, but it's just an inherent property of their representation. Have a nice day :)
- prionassembly 5y ago
  The source of disagreement is: his code generates floating point approximations of uniformly-distributed real values in [0,1]; not random floats greater than 0 and smaller than 1. This distinction has little to do with the subtlety of floats. You can e.g. generate numbers up to 100 with - 5d20 (5 dice of 20 sides), - 20d5 or even - 16d6+1d4. [Edit: the point of this exercise: these are different representations of the numbers up to 100.] But even assuming each die with D sides has equiprobable results with prob 1/D, these choices don't have the same probability distribution. To convince yourself of this, compare 1d12 (the probability of getting 1 is 1/12) with 2d6 (the probability of getting 1 is 0).

orlp 5y ago

It's a neat trick, but can not generate all floating point values. See my other comment for that.

torotonnato 5y ago
If you want max entropy and normally distributed values then, I think, there's no other way to go. Nice post btw
- orlp 5y ago
  What do you mean by "normally distributed values"? Your reply also doesn't follow a normal distribution by the way. Did you mean uniform? For uniform values there is a way to go and my other reply exactly describes how.
  - torotonnato 5y ago
    Of course, it's uniform. I always swap the two names randomly hehe. I understand your code. The difference with the snippet I posted (which, btw, is not mine) is that the difference between successive floats is always a constant, i.e. there is no rounding. It's fast, has 23 bits of entropy and it's suited for constrained platforms/small demos [0], since it can be coded with very few asm instructions. I'm not saying that your solution hasn't its merits, well done. [0] The author of the code is a known member of the demoscene
    - orlp 5y ago
      Oh, I know very well who iq is :) And for a visual demo it might make perfect sense to sacrifice completeness of a solution for speed / code size. But to me, "pick a random number from {k/2^23 : 0 <= k < 2^23, k ∈ ℕ}" and "pick a random number uniformly at random from [0, 1)" are not the same. All operations (add/sub, mul/div, sin, exp, log, etc...), with IEEE754 floats are defined using real arithmetic, and then assumed to round to the nearest representable floating point value. I don't see why random number generation, at least as a default before micro-optimizing, should be any different.
      - torotonnato 5y ago
        You are right, I was uncomfortable with the uneven density of the floats approaching zero, but it's just an inherent property of their representation. Have a nice day :)
prionassembly 5y ago
The source of disagreement is: his code generates floating point approximations of uniformly-distributed real values in [0,1]; not random floats greater than 0 and smaller than 1. This distinction has little to do with the subtlety of floats. You can e.g. generate numbers up to 100 with - 5d20 (5 dice of 20 sides), - 20d5 or even - 16d6+1d4. [Edit: the point of this exercise: these are different representations of the numbers up to 100.] But even assuming each die with D sides has equiprobable results with prob 1/D, these choices don't have the same probability distribution. To convince yourself of this, compare 1d12 (the probability of getting 1 is 1/12) with 2d6 (the probability of getting 1 is 0).