6 ms·

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

by art4711 12y ago

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?

danieldk 12y ago
I get the impression that it's indeed not a solved problem, and even implementations that do not have to follow standards like C++ get it wrong. I recently submitted this to Hackernews, which is a nice treatment of the problems: http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float?
- art4711 12y ago
  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".
  - danbruc 12y ago
    What do you mean when you say you don't like that some numbers are returned more often than others? This seems completely inevitable for a uniform distribution because floating point numbers don't have a uniform density across the real line. Only if you choose a range like [1,2] with a uniform density of floating point numbers you will see all floating point numbers in the interval - except both bounds of course - with equal probability. You would have to not return some floating point numbers ever to see all returned floating point numbers in the interval with equal probability but that of course hardly qualifies as a uniform distribution if some perfectly valid floating point numbers will never occur.
    - SamReidHughes 12y ago
      It totally qualifies as a uniform distribution. Is it the case that generating [1, 2) generates a uniform distribution, but subtracting 1 from that does not produce a uniform distribution?
ZoFreX 12y ago
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.
- Someone 12y ago
  #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.
  - ZoFreX 12y ago
    That would violate #1, as it would generate numbers more frequently that lay in ranges of higher precision.
    - Someone 12y ago
      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.
acqq 12y ago
As you claim on your page github page: "To be useful this would require vastly more testing and independent verificaiton from someone who actually understands set theory and ieee 754 floating point numbers. I can confidently say that I know neither, but as the industry standard on stackoverflow and the c++ libraries seems to indicate, something something something one-eyed man and the land of the blind." I believe your confusion comes exactly from not really understanding how floating point works on the low level. You really need that before you can write the meaningful numerical code. Moreover, the most effective generation of the range of floating point numbers has to "know" the internal representation of floats. Specifically, the papers and the implementations of random number generators from Prof Makoto Matsumoto use that knowledge, and he specifically claims that he didn't invent the approach, but that it was known at least since 1997, crediting Agner Fog.
- art4711 12y ago
  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.
acqq 12y ago
Do see my answer here: https://news.ycombinator.com/item?id=9370844 https://news.ycombinator.com/item?id=9370844

by art4711 12y ago

danieldk 12y ago

I get the impression that it's indeed not a solved problem, and even implementations that do not have to follow standards like C++ get it wrong. I recently submitted this to Hackernews, which is a nice treatment of the problems: http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float?

art4711 12y ago
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".
- danbruc 12y ago
  What do you mean when you say you don't like that some numbers are returned more often than others? This seems completely inevitable for a uniform distribution because floating point numbers don't have a uniform density across the real line. Only if you choose a range like [1,2] with a uniform density of floating point numbers you will see all floating point numbers in the interval - except both bounds of course - with equal probability. You would have to not return some floating point numbers ever to see all returned floating point numbers in the interval with equal probability but that of course hardly qualifies as a uniform distribution if some perfectly valid floating point numbers will never occur.
  - SamReidHughes 12y ago
    It totally qualifies as a uniform distribution. Is it the case that generating [1, 2) generates a uniform distribution, but subtracting 1 from that does not produce a uniform distribution?

ZoFreX 12y ago

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.

Someone 12y ago
#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.
- ZoFreX 12y ago
  That would violate #1, as it would generate numbers more frequently that lay in ranges of higher precision.
  - Someone 12y ago
    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.

acqq 12y ago

As you claim on your page github page: "To be useful this would require vastly more testing and independent verificaiton from someone who actually understands set theory and ieee 754 floating point numbers. I can confidently say that I know neither, but as the industry standard on stackoverflow and the c++ libraries seems to indicate, something something something one-eyed man and the land of the blind." I believe your confusion comes exactly from not really understanding how floating point works on the low level. You really need that before you can write the meaningful numerical code. Moreover, the most effective generation of the range of floating point numbers has to "know" the internal representation of floats. Specifically, the papers and the implementations of random number generators from Prof Makoto Matsumoto use that knowledge, and he specifically claims that he didn't invent the approach, but that it was known at least since 1997, crediting Agner Fog.

art4711 12y ago
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.

acqq 12y ago

Do see my answer here: https://news.ycombinator.com/item?id=9370844 https://news.ycombinator.com/item?id=9370844