5 ms·
I don't think I've ever seen anyone use division to get a ranged random number. I copied all of the examples I saw, and every one of them multiplied n by a rand
by hinkley 4y ago
I don't think I've ever seen anyone use division to get a ranged random number. I copied all of the examples I saw, and every one of them multiplied n by a randomized floating point number in the interval of [0,1) and take the whole number part.
The only time I hear about 'other ways' is here on Hacker News.
edit: range notation
- IncRnd 4y agoThis seems as it was a fun project. I'd caution people not to take it as a "better" way to generate cryptographically secure random numbers. It's just a method that is used, which is good enough for lots of instances that need a randomish number.
- thaumasiotes 4y ago> I copied all of the examples I saw, and every one of them multiplied n by a randomized floating point number in the interval of (0,1] and take the whole number part. Really? I would have expected at least a 20:1 ratio in favor of [0,1) over (0,1]. Most obviously, (0,1] can't produce a uniform distribution, because the input value 1 produces its own unique output value. Whereas the input value 0 shares its output value with the rest of the interval (0, 1/n).
- hinkley 4y agoYeah I knew I was going to get the syntax wrong. My point is you're multiplying a float, not dividing an integer.
- thaumasiotes 4y agoI'm not really familiar with the larger issue, but the scaling method is easy as long as you have an easy way of producing a uniformly distributed random value between 0 and 1. That's not so easy to do; I suspect the fancier methods of generating random numbers are of interest because they have an easier requirement such as "32 random bits".
- hinkley 4y agoI've not looked at implementation details for long enough that I don't trust my answer, but I presume it has something to do with getting 30-some bits of data from the RNG, then coercing it to a floating point with zero on the left side of the mantissa.
- Dylan16807 4y ago> I'm not really familiar with the larger issue, but the scaling method is easy as long as you have an easy way of producing a uniformly distributed random value between 0 and 1. That's not so easy to do It's plenty easy to do. Start with 1.0 then fill the mantissa with random bits. For a flat distribution subtract 1.0. For an "every float is possible" distribution count the leading 0 bits in another chunk of random, and subtract count+1 from the exponent. You'd probably want the former for a situation like this.
- CodesInChaos 4y agoIn Germany we write `[0,1[` which is easier to remember.
- 112233 4y agoI'm curious in what field (of programming) are these examples. The reason is because I cannot recall a single rng I've looked at that uses floating point. Must be a different use case
- hinkley 4y agoLanguages that use this pattern, in decreasing order of familiarity and increasing levels of Googling: Java, Javascript, Python, Ruby, Perl languages where it's optional: C#, Elixir, Go That's about when I got tired of Googling.
- silon42 4y agofor Java first hit in google 'java random' has counterexamples
- hinkley 4y agohttps://docs.oracle.com/javase/7/docs/api/java/lang/Math.html https://docs.oracle.com/javase/7/docs/api/java/lang/Math.htm... Random also exists, with a bunch of options including CSPRNG. But if you’re just simulating a die roll, Math.random is sufficient unless you’re writing gambling software.
- edflsafoiewq 4y agoJava, Python, and Ruby all have explicit functions to generate an integer in a range. Java: Random.nextInt(b) Python: random.randrange(b) Ruby: rand(b)
- adunk 4y agoThis article goes through a bunch of ways to get both biased and unbiased random numbers by using a variety of methods, some of which use division: https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html Those examples are all relatively low-level. Many high-level languages provide a floating point interface on top of such an underlying integer pseudo randomness algorithm. This is the reason why much high-level code use multiplication to get a ranged value. This post goes into some detail about how the V8 JavaScript engine creates a [0, 1) floating point pseudo random value from its underlying integer pseudo-random algorithm: https://v8.dev/blog/math-random https://v8.dev/blog/math-random
- Dylan16807 4y ago> This post goes into some detail about how the V8 JavaScript engine creates a [0, 1) floating point pseudo random value from its underlying integer pseudo-random algorithm: https://v8.dev/blog/math-random https://v8.dev/blog/math-random You'd think so but it doesn't really say. It's almost entirely about how they make the integer. Following the commit link shows that they use the method of filling 1.0 with random mantissa bits and then subtracting 1.0 >> The number of random values it can generate is limited to 2^32 as opposed to the 2^52 numbers between 0 and 1 that double precision floating point can represent. Not really true. That's how many numbers their algorithm returns, which is almost as many evenly-spaced floats there are between 0 and 1. But because it starts with a number between 1 and 2, that method actually wastes a bit, and that number really should be 2^53. But floating point itself has 1/4 of its values between 0 and 1, so for double precision that's roughly 2^62!
- deleted 4y ago[deleted]
- Retr0id 4y agoThe implementation you describe would be slightly biased (for any n that is not an integer power of 2), due to the finite precision of floats. This makes it unsuitable for certain applications.
- moonchild 4y agoI 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 agoA 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 agoRight. I was not thinking straight.
- lifthrasiir 4y agoSmall 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.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- EthicalSimilar 4y agoMost JavaScript codebases that I have read over use the division based method, it’s rare to find one that uses a random floating point multiplied by the limit (outside of Math.random(), I’m talking about crypto.getRandomBytes() implementations). I think this is likely due to the nature of JavaScript’s whacky integer and float implementations.