15 ms·
How many floating-point numbers are in the interval [0,1]? (2017)
- mike_hock 4y agofloat32: 1 for exactly 1.0 (exponent=127,mantissa=0) + 127 * 2^23 for [0,1) (127 distinct exponent values (0 through 126) and any bit pattern in the mantissa; this includes +0 and denormals) + 1 for negative zero = 1065353218 = 0x3f800002 + 2, i.e. two more than the representation of 1.0, because everything up to and including that (as an unsigned integer) represents something in [0,1], plus the missing negative zero.
- pclmulqdq 4y agoOne could make an argument that negative zero is not in [0, 1]. Usually, negative zero is the result of operations like `(small negative number) / (big positive number)`, whose result at infinite precision would not be inside [0, 1]. Negative zero is equal to zero, though, so maybe it is inside [0, 1].
- mike_hock 4y ago[0,1] = {x | 0 <= x and x <= 1}. "<=" does not depend on where x came from or what it would have been had something else happened that didn't happen. There's no "maybe."
- pclmulqdq 4y agoAre we talking about the interval [0, 1] in R or about [0.0f, 1.0f] (the interval in the space of floats)? I'm pretty sure that your definition of an interval is correct even when the set doesn't have a total order, but if we're talking about floats whose values are in [0, 1] in the space of real numbers, that may not include -0.0f, since floating point numbers usually represent one number in a range of real values, and -0.0f represents -epsilon where epsilon is between 0 and the real value of the smallest denorm.
- mike_hock 4y ago> I'm pretty sure that your definition of an interval is correct even when the set doesn't have a total order Yes, and in the usual ordering on floats that's actually implemented by hardware, 0.0f == -0.0f, so -0.0f is in [-0.0f, 0.0f]. > since floating point numbers usually represent one number in a range of real values, and -0.0f represents -epsilon where epsilon is between 0 and the real value of the smallest denorm. That's a valid interpretation but apparently the standard ordering wasn't specified from that perspective.
- mike_hock 4y ago* I meant in [0.0f, 1.0f], of course
- mike_hock 4y ago* 0x3f800000 + 2, of course
- EthicalSimilar 4y agoI apply the above theory for generating random numbers in JavaScript, based on given inputs (server seed, client seed, and nonce). JavaScript uses double precision floating point numbers, meaning 52 bits for the mantissa. const hash = crypto .createHmac('SHA256', serverSeed) .update(`${ clientSeed }:${ nonce }`) .digest('hex'); const significant = hash.substring(0, 52 / 4); const integer = parseInt(significant, 16); const float = integer / (2 * 52); return { float, hash, };
- dr_dshiv 4y ago> 1,056,964,610. There are 4,294,967,296 possible 32-bit words, so about a quarter of them are in the interval [0,1]. Isn’t that interesting? Of all the float-pointing point numbers your computer can represent, a quarter of them lie in [0,1]. By extension, half of the floating-point numbers are in the interval [-1,1].
- Taywee 4y agoI don't think it's that strange. It's a scientific notation with the signed exponent around 0, so (barring special cases like NaN and infinite), it will be divided roughly in half around the pivot of 2^0 for both signs.
- magicalhippo 4y agoSurely this was by design? At least when solving physics problems, you'll frequently scale the equations so the actual values in the problem are around -1..1. Thus having extra precision around -1..1 when solving such problems would be beneficial. For example, if you're trying to solve the motion of a mass on a spring that gets an initial kick, rather than representing the spring length in meters, you divide by some characteristic length[1] and get a non-dimensional length of order 1. If you want the actual length, you just multiply the non-dimensional length by the characteristic length. [1]: https://hplgit.github.io/scaling-book/doc/pub/book/html/._scaling-book2006.html https://hplgit.github.io/scaling-book/doc/pub/book/html/._sc...
- moralestapia 4y ago>Surely this was by design? It is indeed, and one of the first things you learn in scientific computing is to make your values fit mostly within [-1, 1].
- sampo 4y ago> Thus having extra precision around -1..1 when solving such problems would be beneficial. Floating point numbers have the same precision (relative precision) everywhere.
- cormacrelf 4y agoFor 32 bit floats, you can skip the math and just test all of them. LLVM will vectorise and unroll this nicely. fn main() { let start = std::time::Instant::now(); let total = (0..=u32::MAX) .filter(|&x| { let f = f32::from_bits(x); 0. <= f && f <= 1. }) .count(); println!("total {total} in {:?}", start.elapsed()); } total 1065353218 in 1.364751583s Edit: Apparently if you move the sum to its own function it runs in 500ms. A bit temperamental. Edit 2: it's the size of the sum accumulator that makes it slow. The version above is like `.fold(0usize, |a, _| a + 1)`. When I moved it to another function, I cast the return value to u32, so LLVM saw basically `.fold(0u32, |a, _| a + 1)` and could use u32 throughout. Godbolt says the usize version ends up with floats in xmm* registers on x86, which fit 4 32-bit floats, but the u32 version ends up with floats in ymm* registers (8 32-bit floats) and similar half-as-wide behaviour on ARM.
- raphlinus 4y agoThis is 0x3f800002, which should look pretty familiar to people who work with floating point in hex; it's 2 + the representation of 1.0. To understand the lowest order bits, you've got -0.0 (0x80000000) in there, as well as everything from 0.0 (0x00000000) to 1.0 (0x3f800000) inclusive. This is a larger number than the one cited in the post because the latter only includes "normal" numbers. This includes the "denormals" as well. It's very easy to generalize this to 64 bits, there are 4,607,182,418,800,017,410 of them.
- pansa2 4y agoI did the same thing, recalling "There are Only Four Billion Floats–So Test Them All!" [0]. Except I used Python, so it took over 10 minutes: >>> import struct >>> count = 0 >>> for i in range(0x1_0000_0000): ... f = struct.unpack('<f', struct.pack('<I', i))[0] ... if 0 <= f <= 1: count += 1 ... >>> count 1065353218 [0] https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/ https://randomascii.wordpress.com/2014/01/27/theres-only-fou...
- jherskovic 4y ago
- gerdesj 4y ago[flagged]
- cwillu 4y agoI feel the world (okay, maybe just hn :p) would be a better place if people generally kept the “I tried this with GPT and this is what it said” comments to GPT-related posts.
- gerdesj 4y agoI disagree. ChatGPT n that are currently "disruptive". Disruptive to the point that I already have colleagues who get close to palpitations if they can't access it. Within mere weeks or a few months their entire modus operandi has changed. There are major issues (1) with LLM, not least their inscrutability and habit of hallucinating. Soon we might be getting all whizzed up over "hyperdimensional computing" (2) which, let's face it has at least sorted out how to sound like a cool kid. However it is possible to work out how a hyperdimensional ... thingie "works" because of the way it is built and that is a powerful thing. ChatGPT n that are a bunch of weights and who knows what that actually means. No doubt we will have more stuff and frankenAI and who knows what else but it will be exciting. I think things have only just started to get weird. It looks to me like a real paradigm shift. To understand what the hell is happening we need to discuss things and that means discussing the old with the new - hence my comment. Feel free to disagree but please engage. (1) https://arxiv.org/abs/2304.00612 (2) https://www.quantamagazine.org/a-new-approach-to-computation-reimagines-artificial-intelligence-20230413/ (EDIT - fixup formatting and refs)
- cwillu 4y agoThat can be true, simultaneously with the repetitive “I copy/pasted this into chatGPT, here's what it said!” comments being boring. They don't add anything to the discussion. If the grandparent provided some analysis of what was output, maybe tied it back into the sorts of errors humans make and how gpt does or does not make dealing with this sort of issue easier, that'd be fine. I may or may not be terribly interested in it, but I wouldn't downvote it. But it didn't. (edit to add: fwiw, I didn't flag the comment, and upvoted your reply)
- macintux 4y agoPresumably an offshoot of the discussion around floating point gotchas in gaming: https://news.ycombinator.com/item?id=35539595 https://news.ycombinator.com/item?id=35539595
- eimrine 4y agoCan I see a graph to know how many of them are in any interval?
- oprypin 4y agohttps://fabiensanglard.net/floating_point_visually_explained/ https://fabiensanglard.net/floating_point_visually_explained... Not a graph, but gets much closer to answering this.
- nighthawk454 4y agoI always have trouble re-finding the one I remember, but here's a pretty good visualization: https://www.researchgate.net/figure/The-distribution-of-representable-floating-point-number-in-a-computer_fig9_320451960 https://www.researchgate.net/figure/The-distribution-of-repr...
- tand22 4y agoA grey link already for me xD
- sampo 4y agoAbout 1/4 of all of them.
- garbagecoder 4y agoAs many as you want depending on how many bits. Floats are made to approximate real numbers. There is an uncountably infinite number of real numbers on any open interval of real numbers. Since (0,1)\in[0,1] there you go. Just keep adding bits.
- Sharlin 4y agoThe question in the title is obviously something explored in the article and to be understood in the context of the article, not to be answered with a glib non-answer by some random HN commenter who evidently didn’t even take a look at the article.
- garbagecoder 4y agoyes, poor headline writing is my fault. and it's not addressed in the article, so I think it's you that didn't read it. It's not even remotely addressed in the article and in fact, the what I posted is an answer to this comment at the end about changing to 64 bits. if he addressed this he would know the answer, and he didn't appear to. So you chose to just decide I was being "glib" and slander me before understanding the context? Have a weekend. I think you unironically need to touch grass. I really hate this website sometimes.
- pestatije 4y agoSo is it 1,056,964,610 (TFA) or is it 1,065,353,218 (comments) and why the difference?
- jwilk 4y agoTFA counted only normal numbers and zero. The commenters counted also subnormals.
- an1sotropy 4y agoOthers have previously pondered this, and the related issue of how to randomly select floats in [0,1). I found this to be a helpful account: https://mumble.net/~campbell/2014/04/28/uniform-random-float https://mumble.net/~campbell/2014/04/28/uniform-random-float and there's working C code too: http://mumble.net/~campbell/2014/04/28/random_real.c http://mumble.net/~campbell/2014/04/28/random_real.c
- camel-cdr 4y agoI've previously written an algorithm that generates random floats in any [a,b], which can generate all possible floating point values, including subnormals, with the proper probability, and does so quickly for any choice of a and b. [0] [0] https://github.com/camel-cdr/cauldron/blob/main/cauldron/random.h#L1605 https://github.com/camel-cdr/cauldron/blob/main/cauldron/ran...
- an1sotropy 4y agoThanks for sharing this. I was worried when I saw the rejection test at the end (around line 1749) that this could be slow, but I guess that for cases like a=0 and b=1, your code avoids that rejection ever happening, is that right? So the rejection only kicks in when the bounds are in the middle of range of one fixed exponent?
- camel-cdr 4y agoThe rejection case should only ever be executed for ranges that differ in more than one exponent. (This is handles by the cases above) The generated exponent starts of at the max exponent of a and b, and is logarithmically decremented (I'm not sure if this is the correct word for it, but decremented until a coin flip hits tails, would be a better way to explain it). So the exponent and the fraction range can't ever get really small, since there is always at least one exponent that accepts the full range of fractions. Edit: Actually, looking at it again, the second special case doesn't apply to subnormals, so while generating in the range float x = 2.3509886E-38f; // exp=00000001,frac=11111111111111111111111 float min = nextafterf(nextafterf(x, 0), 0); float max = nextafterf(nextafterf(x, 1), 1); works almost instantly (on average 4 iterations), the current code does indeed have a bottle neck for: float x = 1.1754942E-38f; // exp=00000000,frac=11111111111111111111111 float min = nextafterf(nextafterf(x, 0), 0); float max = nextafterf(nextafterf(x, 1), 1); It's not insanely-minutes-long-stall-bad, but takes about 0.02 seconds to generate one number in the above range with a good prng (opposed to 2e-08 seconds for the first case) I'll look into fixing this. Edit 2: I've added a commited a comment about this for now. I wonder why my test suite didn't catch this.
- nighthawk454 4y agoTangentially, it may be interesting to think how this differs for other float formats. Such as: Google Brain's bfloat16, Nvidia's TensorFloat
- dang 4y agoDiscussed at the time: How many floating-point numbers are in the interval [0,1]? - https://news.ycombinator.com/item?id=13759458 https://news.ycombinator.com/item?id=13759458 - Feb 2017 (153 comments)
- yarg 4y agoRelevant: https://stackoverflow.com/questions/43153699/how-can-smallest-floating-point-number-be-2-126-not-2-128 https://stackoverflow.com/questions/43153699/how-can-smalles...