Really divisionless random numbers | Hacker News Reader

Really divisionless random numbers

dotat.at

48 pointsingve34 comments

Kind 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).

That’s me! and my domain name recently had its 25th birthday https://twitter.com/fanf/status/1577952281764454400 … I should probably scavenge some bits from that twitter thread to add to my web site.

I 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.

I 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.)

> Austrian TLD

> a little bit eccentric

Stereotype checks out :D

Why 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?

You can point the DNS to it but you can’t host the registration there. Unsure why.

Oh, I didn’t even know route53 did domain registrations. I thought it was just a DNS service, my mistake.

What 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.

TFA'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.

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

> 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).

Yeah I knew I was going to get the syntax wrong.

My point is you're multiplying a float, not dividing an integer.

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; I suspect the fancier methods of generating random numbers are of interest because they have an easier requirement such as "32 random bits".

I'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.

> 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.

In Germany we write `[0,1[` which is easier to remember.

I'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

Languages 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.

for Java first hit in google 'java random' has counterexamples

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.

Java, 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)

This 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

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

> 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

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!

This 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.

The 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.

I 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.)

A 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.

Right. I was not thinking straight.

Small 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`.

> Assuming "uniform" to mean the uniform distribution

Well, yes, but a discrete/integer-ish version. Every number is equidistant and equally likely.

> A uniform float in the range [0, 1) has exactly 2^53 possible values (if you generate it in any sensible way).

No, there are 2^62 - 2^52 float64 values in [0, 1), so your method (which I assume is to fix the exponent at 0, randomize mantissa so we get 1.abcdef... and subtract 1) can't possible be sensible, if your sense of sensibility includes correctness.

First note that the only correct way to generate a floating point in [a, b] is to generate a random number in [a, b] with infinite precision and then round it to the closest floating point number in that range. This maintains all the nice properties of real uniform generation (assuming a, b are representable floating point numbers), expectation of (a + b) / 2, continuity of ranges such that generating U[a, c] is the same as choosing between U[a, b] and U[b, c] with weights (b-a) and (c-b) respectively, etc, while having an non-zero chance of generating any floating point value in [a, b].

An efficient algorithm for generating a float in [0, 1] is described in "Generating Pseudo-random Floating-Point Values" by Allen B. Downey. Correctly implemented it uses a handful of instructions and single call to the word-sized random number generator > 99% of the time, using a count-trailing-zeros (or similar) CPU instruction to efficiently sample from an exponential distribution (as opposed to the naive loop in the paper).

Note that the mathematical distributions U[0, 1) and U[0, 1] are indistinguishable. So when we say "a uniform float in the range [0, 1)" we can't possibly mean U[0, 1). What we mean in reality is something that approximates U[0, 1] but can't generate the floating point value 1.0. One decent way to do that is to sample from U[0, 1] but reject the 1.0 output. This effectively samples from U[0, 1 - eps] where eps = (1 - floatbefore(1.0)) / 2.

This unfortunately does mean we lose our nice expectation of 0.5. Note that the error in expectation for sampling from [1, 2) using strictly mantissa and subtracting 1 is significantly worse. For example in a 2-bit exponent 2-bit mantissa unsigned floating point with exponent bias -1 (giving the following list of values)

    0.0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, 1.0, 1.25, 1.5, 1.75, 2.0, 2.5, 3.0, 3.5

we find that sampling using Allen B. Downey's method from [0.0, 1.0] but rejecting 1.0 as output has an expectation of 0.46875, sampling uniformly from {1.0, 1.25, 1.5, 1.75} and subtracting 1 like the mantissa method would have an expectation of 0.375.

Most of that bias boils down to the subtraction method always wasting a single bit of mantissa. Which is worth noting but also a very tiny problem to have. It doesn't make things "not sensible".

Most 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.

Reply on news.ycombinator.com