Comment by tialaramex | Hacker News Reader

Comment by tialaramex | Hacker News Reader

> For unbiased random floating-point numbers, generate floating-point numbers with probabilities given by drawing a real number and then rounding to floating point.

Immediately there are alarms going off in my mind. Your machine definitely can't pick real numbers, Almost All of them are non-computable. So you definitely can't be doing that, which means you should write down what you've decided to actually do because it's not that.

What you actually want isn't the reals at all, you want a binary fraction (since all your f64s are in fact binary fractions) between 0 and 1, and so you just need to take random bits until you find a one bit (the top bit of your fraction), counting all the zeroes to decide the exponent, then you need 52 more bits for your mantissa.

I'm sure there's a faster way to get the same results, but unlike the article's imagined "drawing a real number" this is actually something we can realize, since it doesn't involve non-computable numbers.

Edited: You need 52 more bits, earlier this comment said 51 but the one bit you've already seen is implied in the floating point type, so we need 52 more, any or all of which might be zero.

The part you're quoting is the spec, not the implementation. It implicitly assumes a machine model where sampling a uniformly random real number in an interval and correctly rounding it to a floating-point number are both supported operations. Of course this cannot be a real machine or even a Turing machine, but you can imagine and mathematically model a more powerful machine which can do these things. (Turing machines are imaginary anyways.)

This unimplementable algorithm for an imaginary machine is still useful, because it nails down the probability distribution we expect the output samples to have. And because they're sampled from a finite value space and the probabilities of obtaining each possible output are rational numbers, we have a chance of finding an implementable algorithm for a real machine that produces the same output distribution.

The rest of the article goes into detail on what they decided to actually do. It's similar to your proposal but has more edge-case handling and deals with different rounding modes.

> Turing machines are imaginary anyways.

Sure, but there is a simple correspondence between modern/typical computers (that does require a potentially unlimited supply of new hard drives, but that is rarely relevant) and Turing machines, while such a correspondence can probably never exist for the "real number" model.

If you can generate a sequence of independent fair coin flips of indefinite length (this is a big if, but hold that though), then you can effectively generate a true real number uniformly from the unit interval. What you can't do is to access all of its digits all at once. But to correctly round it to a value representable in a given floating-point representation you don't need all the digits, you only need enough digits to decide whether the number falls into an interval where all reals round to the same value.

As for generating independent fair coin flips of indefinite length, none of the PRNGs qualify.

I don't think you can make the non-computable reals with your "indefinite fair coin flips". All you're making there is an approximation.

You can make all the rationals this way, but that's Almost None of the real numbers.

Reply on news.ycombinator.com