art4711

Got pointed back here that there was another response. Sure. If you subtract 1 from [1,2) you will get 52 bit precision (or 23 for floats as your magical constant indicates). This means that the number just before 1.0 will not be picked, then the number before that will be, the next one won't be, etc. You don't pick every other number in the range where you should have problems covering every number without introducing any irregularity to the result. So what? Map your random numbers to the set [0,1,2,3] divide by 4 and you also get a uniformly distributed number in [0,1).

With my method we'd pick the magical constant 16777216.0f and we'd also get 0, 1, 2, ... 16777216.0f is bigger than 8388608f, therefore it's better.

This [1,2)-1.0 method has 0 probability of picking the first number less than 1.0, 2^-52 probability to pick the next one, 0 probability to pick the next one, 2^-52 probability of picking the next one, etc. My algorithm has 2^-53 probability of picking the first number less than 1.0, 2^-53 probability of picking the next one, etc. Down to .5 I can pick every representable number. After that there is a choice. I chose to have the same probability of picking every smaller number (including 0.0) as the probability of picking numbers in the upper half of the range, so I have holes that I can't pick, but at least in the upper half of the range I can pick every number I can represent.

That's why I think that [1,2)-1.0 is flawed. Because it adds an arbitrary limitation to its output, without any good reasons except that it was convenient to implement and they didn't have to think hard.

I'm sorry, but if you mean Makoto Matsumoto who seems to be the name mentioned in the SFMT library, that library is bogus. It generates numbers in [1,2) and then maps that to [0,1) by subtracting 1. This can be trivially shown to lose information, in fact I added a little hack to my github repo two days ago showing why it's bogus when that specific library was mentioned to me (again). Unless you want to lose one bit of entropy in the first conversion every number gets. And it still doesn't get us anywhere close to arbitrary ranges (which is the hard problem).

I also just looked at stuff that Agner Fog has published, thank you for mentioning him. Same thing. Maybe my understanding of floating point is bad, but his is worse. One generator uses the classic rng()/((double)range_of_rng) approach which is the whole reason why the C++ standard generators aren't uniform (because it will only work you use a non-standard rounding mode for floating points and still doesn't get us anywhere close to arbitrary ranges which are a completely different problem). Another uses [1,2) - 1.0 which loses information. And the third one is "combines two different random number generators for improved randomness", which I guess sounds good, how does he do it? He generates two [0,1) numbers, adds them together then subtracts 1.0 when the result is bigger than 1.0 which both loses precision and compounds the rounding problems.

Literally the first thing I did when trying to figure this out months ago was to randomize the bits in the mantissa with a 0 exponent to get a [1,2) number then subtracted 1.0 from it, then it took me 10 minutes to test that this doesn't actually work.

So, maybe my understanding of floating point numbers is bad, but the authorities you cite are worse.

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.

I actually got the link to his code yesterday and it's eerily close to what I wrote a few months ago, but I rejected that approach because I didn't like that any of the numbers in [0.5,1.0) were so much more likely to be returned than 0.0. This gives the highest possible entropy and all numbers representable by floating points in that range can be returned, but the trade-off is that certain values will be returned vastly much more often than others. It's this discussion of trade-offs that I'm actually missing.

I don't feel competent enough to write that paper/article/rant about the trade-offs myself, I barely understand math and randomness, but I'm getting tired of all the libraries out there that say "uniform[1] random[2] floating points[3] [1] - not actually uniform [2] - not actually random [3] - terms and conditions apply, YMMV, not valid where invalid".

Author of the blog post following the sudden surge of traffic here.

> Producing quality random floating point numbers, fast, is a solved problem

Is it? Do you have any reference I can read?

Everything I've found is obviously flawed on the level of `(rand() % 1000)/1000.0`. I don't actually care about the C++ facilities that I'm discussing in that post. I just hoped that they would be a good path to follow to find one good source that discusses the various trade-offs between mapping a set of random integers (or a stream of bits, or whatever) to floating points. I've seen serious peer reviewed papers that just randomize the bits of the exponent and mantissa and call that random or papers that do what I've tried to do (which has its flaws) - count the number of representable, uniformly spaced, floating point numbers between `from` and `to` but then generate their random numbers with `random() % count`, which is like restoring the Mona Lisa with crayons.

So I'm completely serious. I'm desperate for a good source, where can I find it?