Comment by ZoFreX | Hacker News Reader

Comment by ZoFreX | Hacker News Reader

Parent Full thread

I've been working on the same problem. I've found two broad solutions, which solve subtly different definitions of the problem:

1) Generate numbers that are uniformly distributed in the sense of, if you generated a bazillion of them and divided the range into buckets of even size, each bucket would have similar numbers of numbers in them.

2) Generate numbers that meet the above definition AND so that any particular floating number is no more likely to be picked than any other.

(The discrepancy being down to there being more representable floating point numbers in some ranges than others)

For my application, I don't need to worry about #2, so I just generate an integer number uniformly across a given range (which is simple enough to do without bias), cast to float, and divide. It meets the definition of #1 unless the buckets chosen are very small.

I have seen a few people write solutions for #2 online, but haven't seen any that have been sufficiently analysed and proven correct.

#2 is extremely easy, isn't it? Use a uniform random generator to generate a bit pattern of the size of a float, reinterpret_cast to float, and repeat until you have something that is in the target range (that gets rid of NaN's as they aren't ever in any range; filter denormalized numbers, if required)

You can speed that up by forcing bits that you know have to be zero or one to those values. If you do that, I think your expected number of iterations can be proven to be fairly small.

That would violate #1, as it would generate numbers more frequently that lay in ranges of higher precision.

But you can't simultaneously have #1 and #2. #2 means that you pick a number between 1 and 2 as often as you pick one between 2 and 4, 4 and 8, etc.

You can compensate for that by never returning many numbers, but that violates #2.

2) Generate numbers that meet the above definition AND so that any particular floating number is no more likely to be picked than any other.

But you can't simultaneously have #1 and #2.

#2 = #1 AND MORE and NOT (#1 AND #2) imply that #2 is impossible independent of #1 or MORE.

You most certainly can.

If you follow the github links in that blog post, you'll see in arbitrary_range.c that that's exactly what I do in "rd_positive". Pick the highest number in the range, calculate the distance to next lower representable number, only return multiples of that (bounded by the total number of those distances within the range). For IEEE 754 doubles, unless your range can't represent that many doubles at all it makes you end up with somewhere between 52 and 53 bits of entropy per number generated.

But doesn't that mean that you decide to split he set of represent able numbers in gate range in those that your code can return and those that it will never return?

Yes, the ones that you decide to return all have the same probability. The ones that you decide to never return have Rob ability zero. That is not "so that any particular floating number is no more likely to be picked than any other."

It's referring to the numbers that could be picked at all.

I made a mistake in my comment. It should say that any particular floating number is no more likely to be picked than any other with the same exponent. (I think that's right? So basically any representable number could be chosen, but ones in 'sparser' rangers will be more likely to be picked than a single number in a 'denser' range)

Reply on news.ycombinator.com