6 ms·
Really divisionless random numbers
- deleted 4y ago[deleted]
- hinkley 4y agoI 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.
- mildbyte 4y agoKind of off-topic, but this person's e-mail address is "dot at dotat dot at", which is very unique (see https://dotat.at/email.html https://dotat.at/email.html).
- fanf2 4y agoThat’s me! and my domain name recently had its 25th birthday https://twitter.com/fanf/status/1577952281764454400 https://twitter.com/fanf/status/1577952281764454400 … I should probably scavenge some bits from that twitter thread to add to my web site.
- the_mitsuhiko 4y agoI get the feeling the Austrian TLD is still mismanaged. You can’t even have it on route53 unless they finally added support. I’m assuming that’s not an accident.
- fanf2 4y agoI don't think .at is mismanaged, quite the opposite, but in the way of many ccTLDs it is a little bit eccentric. I don't know why route53 might not support them: perhaps it's to do with contractual faff, or possibly because nic.at uses a less common flavour of EPP. (Sadly the common flavour of EPP has a bonkers data model; a few ccTLDs use an alternative model with a more sensible data model, but although the more sensible flavour of EPP is easier to use in isolation, it has the downside of being different from the ICANN flavour.)
- moffkalast 4y ago> Austrian TLD > a little bit eccentric Stereotype checks out :D
- prvit 4y agoWhy would you not be able to add an .at domain on route53? It’s not like there’s any difference from the dns point of view. Is it .at blocking the nameserver changes or AWS refusing to serve .at domains from their nameservers?
- twic 4y agoWhat would happen if you did rejection sampling one bit at a time? Find the largest multiple of your limit which is less than W. We want to find a random number less than this multiple, because then we can just divide down to get an unbiased result. Maybe this is already implied in how these algorithms are set up, not sure. Generate a candidate random number. If it is smaller than the multiplied limit, you are done. If not, double it, and add a random bit. Repeat until success. To supply the random bits, generate a random number, and use it up one bit at a time. If you need more, generate another random number. I suppose this doesn't work, because the second-most-significant bit of a rejected candidate isn't unbiased. If the multiplied limit is 3/4 of W, then we only reject candidates where the top two bits are both 1! Can you rescue this by discarding more than one bit when you reject? Probably not. Think about the case where the multiplied limit is W-1. The only candidate you would reject is all 1s. You'd have to discard all the bits for the next candidate to be unbiased. Oh well.
- fanf2 4y agoTFA's "really divisionless" algorithm is basically what you suggest, except it adds 32 or 64 bits of randomness in each iteration, instead of 1 random bit.