14 ms·
How many floating-point numbers are in the interval [0,1]?
- dekhn 10y agoHe references one of my favorite functions, 'nextafter'. http://en.cppreference.com/w/cpp/numeric/math/nextafter http://en.cppreference.com/w/cpp/numeric/math/nextafter I'm the kind of person who understands floats by looking at the underlying bit patterns, and nextafter makes it easy to traverse the integers.
- gajjanag 10y ago> He references one of my favorite functions, 'nextafter'. http://en.cppreference.com/w/cpp/numeric/math/nextafter http://en.cppreference.com/w/cpp/numeric/math/nextafter It is a cool function. I remember using it for some testing I did while checking the accuracy of various implementations of basic math functions.
- santaclaus 10y agoWhat about nan? The test '!(x < 0 || x > 1)' will say yes, while 'x >= 0 && x <= 1' will say no. Or -0 for that matter.
- amelius 10y agoCommon sense approach: like the name says, NaN is not a number. The question was about floating point numbers, not floating point values. So I suppose we shouldn't count NaN. Further, -0 (an arbitrarily small number less than 0) doesn't logically fall in the range [0, 1], so it is excluded.
- mark-r 10y agoThere's no need to exclude -0.0, since mathematically and by all tests available to the floating point unit it's equal to +0.0.
- dnautics 10y agofor many applications, consider randomizing in [1,2) and then subtracting one. Although many of the fp values in [0,1) will be inaccessible, you are guaranteed uniformity, and also the lattice that you're drawing from will be fixed.
- SamReidHughes 10y agoHow do randomize in [1,2)? You might as well just generate numbers from [0, 2^53) or [0, 2^24) and divide. If you didn't do that on the way to generating in [1,2), you're going to have fine-grained non-uniformity anyway.
- Dylan16807 10y ago>How do randomize in [1,2)? 0x3f800000 + 23 random bits
- SamReidHughes 10y agoWell. That'll do it. Probably no slower than the integer to float conversion too. It gets you multiples of 2^-52 instead of 2^-53 though.
- strainer 10y agoI see your talking 64 bit floats there which is my habit too. Having only 24 bit mantissa float32s seem insufficient for producing practically uniform variates - the missing 2^24th can be spotted averaging just a billion or so of them. I dont know if it has been improved recently but last year Chrome's Math.random was only putting 32 bits into its float64 - the missing four-billionth can be suggested from the average of a few hundred billion variates.
- SamReidHughes 10y agoYeah, I really think a better way is to imagine generating a uniform real and rounding -- generating [0,1) instead of [0,1] is just sick. If you do rand() * k + n you can get [n, n+k] anyway, so it's not a good primitive to get a half-open interval with. You can generate an integer n in [1, 2^25], then take (n >> 1) * (1 / (float)(1 << 24)) to get a pretty good [0,1].
- murkle 10y agoArticle says 1,056,964,609 / 1,056,964,610 Quick Java program says 1,065,353,216 / 1,065,353,217 Which one is right? Or are Java floats just "different"? static { float a = 0; long count = 0; while (a < 1) { count++; a = Math.nextAfter(a, 2); } System.out.println("count = " + count); }
- astrodust 10y agoIt might depend on the precise representation. This has become increasingly standardized lately which is why those numbers are really close and not wildly off.
- drv 10y agonextAfter is probably also including the denormals (an additional 2^23 values near 0).
- wwweston 10y agoOfftopic, but: Is this not just shorthand, but an actual legitimate Java program these days?
- SpaceManiac 10y agoA bit of both. Code still belongs in a class, not pictured here. `static` blocks are executed when the class is loaded and are usually used to fill `static final` members. In a toy example like this it's shorter than writing the `main()` incantation.
- 10y ago
- astrodust 10y ago> Of all the float-pointing point numbers your computer can represent, a quarter of them lie in [0,1]. Many people think floating point numbers are magically precise. They're not. They're far more accurate at lower magnitudes and precision fades as you work with larger values.
- semaphoreP 10y agoOr you can think of it as precision in the number of significant digits for a number. Each floating point number can only store a certain amount of significant digits. The fractional precision on each float is the same, but the absolute magnitude of the error in the float value increases as the value increases.
- mirimir 10y agoThat's how I learned it.
- jacobolus 10y agoJohn Gustafson’s new “sigmoid unum”/“posit” proposal is kind of interesting; see his recent talk: http://web.stanford.edu/class/ee380/Abstracts/170201.html http://web.stanford.edu/class/ee380/Abstracts/170201.html https://news.ycombinator.com/item?id=13562164 https://news.ycombinator.com/item?id=13562164 It does a variable number of fraction bits, so that the values near 1 are even more densely represented than under the usual IEEE floats, while also providing greater dynamic range (but at reduced precision). I made a little diagram showing a visual comparison of every represented value in a toy 8-bit version vs. IEEE-style floats: https://groups.google.com/group/unum-computing/attach/e80274981e971/posit_vs_float.pdf?part=0.1&authuser=0 https://groups.google.com/group/unum-computing/attach/e80274...
- sunfish 10y agoOut of curiosity, I started watching this talk, but right there in the introduction, the very first example is a dot product where supposedly IEEE 754 double precision gets the wrong answer; I stopped to check the result, and I got the correct answer with double precision (even without binary sum collapse). Then, he says the x87's results are nondeterministic due to being affected by cache, which is incorrect. Then, he trots out a series of half-truths about IEEE 754, which are somewhat true but don't mean what he's presenting them to mean. He even cites a Cray 1 quirk as an example of IEEE 754 weirdness, when in reality, the Cray 1 (1975) predated IEEE 754 by about 10 years. Designing a good arithmetic system takes a lot of attention to detail, and he doesn't make a good impression by being that loose with details in his introduction.
- pmoriarty 10y agoAsking how many "are" in the interval implies that these numbers exist in some sense in that interval. A clearer way to phrase the question might be: "How many floating-point numbers between 0 and 1 can be generated without duplicates?"
- jfaucett 10y agoHonestly, I think IEEE 754 floating point numbers are a pretty bad way of dealing with real numbers and just cause tons of headaches that every math library has to deal with. Even high level programmers aren't shielded from the NaN nonsense. It would be great if we had an underlying implementation we could ignore and that allowed us to think at a more mathematical level. I actually found something recently on this topic while googling for any alternatives, its called Unum and looks very interesting: https://en.wikipedia.org/wiki/Unum_(number_format) https://en.wikipedia.org/wiki/Unum_(number_format) Does anyone know more about this? Are there any chips out there that support it?
- com2kid 10y agoJust reading the list of disadvantages, the format sounds interesting but not that practical in a world where massive numbers of FPUs operating within a thermal limit is a primary design concern.
- Retra 10y agoWikipedia provides a pretty good summary: William Kahan claims the following issues with unums: 1. Unum computation does not always deliver correct results. 2. The description of unums sidesteps using unum for solving calculus problems. 3. Unums can be expensive in terms of time and power consumption. 4. Each computation in unum space is likely to change the bit length of the structure. This requires either unpacking them into a fixed-size space, or data allocation, deallocation, and garbage collection during unum operations, similar to the issues for dealing with variable-length records in mass storage. 5. Unums provide only two kinds of numerical exception, quiet and signaling NaN (Not-a-Number). 6. Unum computation may deliver overly loose bounds from the selection of an algebraically correct but numerically unstable algorithm. 7. The costs and benefits of unum over short precision floating point for problems requiring low precision are not obvious. 8. Solving differential equations and evaluating integrals with unums guarantee correct answers but may not be as fast as methods that usually work. Point #4 makes implementation tricky and slow. Point #6 (from what I understand) means unum operations tend to guarantee correctness by being overly vague - by denoting results that FP can produce using ranges that are just too big to be useful.
- 10y ago
- deleted 10y ago[deleted]
- stcredzero 10y ago(I invoke my pedant-pass.) As formulated in the title, "How many floating-point numbers are in the interval [0,1]?" you could argue that this is the cardinality of the Real Numbers. What the article says it is really talking about are single-precision IEEE 754 floating-point numbers. However, I could define any number of my own floating-point representations at various sizes. The cardinality of all possible floating point representations would be the same as that of the real numbers. This is true even for irrational numbers, as one could formulate floating point representations that specially represent those numbers. (Also, this is arguably an exception to Betteridge's Law, and arguably not an exception to Betteridge's Law.)
- jacobolus 10y agoWhat makes you think any arbitrary real number qualifies as a “floating point number”? I have never seen the term used in anything like that context. To me, the term “floating point number” is about number representation, not number identity. It is an inherently finite quantity in every instance I’ve ever seen. Examples of floating point numbers: The sexagesimal cuneiform 42 25 35 written on the Babylonian tablet YBC 7289; 3.1415 × 10⁰; 1.010101010101₂ >> 2. Not examples of floating point numbers (in my opinion): 1/√2; π, 1/3.
- theoh 10y agoThe GP is claiming that all possible floating point systems, taken together, would contain the same number of values as there are points on the real line. Consider a floating point system based on https://en.wikipedia.org/wiki/Golden_ratio_base https://en.wikipedia.org/wiki/Golden_ratio_base
- stcredzero 10y agoThanks! To be just a bit more precise, I am claiming that all possible floating point systems, taken together, would contain the same number of values in [0,1] as there are points on the real line.
- deleted 10y ago
- mtklein 10y agoThe correct answer is 1,065,353,216. This is easy to work out yourself if you remember one basic, handy property of floats: adjacent floats are adjacent in bit representation, except -0.0f and 0.0f. For example, 0x00000000 is +0.0f. 0x00000001 is the smallest non-zero positive float. 0x00000002 is the second smallest. The only exception to this is -0.0f and +0.0f, which are 0x80000000 and 0x00000000. The rule works with denormal floats, normal floats, and even right on the line between the two. If you want the next positive float, you always just add 0x00000001. Now, +1.0f happens to be 0x3f800000. Recall +0.0f is 0x00000000. The number of values between the two is 0x3f800000 - 0x00000000 == 0x3f800000. Write that in decimal and you get 1065353216.
- digga3000 10y agothe question is [0, 1] so wouldn't that include +/-0 and 1, so 3 more?
- jacobolus 10y agoProbably shouldn’t include –0, which is used to represent underflow of negative numbers.
- nine_k 10y ago-0 is "below zero, but for so little that we cannot represent", so it's outside [0, 1].
- kr7 10y agoThough for the purposes of comparisons, -0 and +0 are the same in IEEE 754. So the expression "x >= 0.0f && x <= 1.0f" is true for x = -0.
- vog 10y agoWhy 3 more? Grandparent already counted one of the border points, so the correct number is either 1 more or 2 more, depending on whether you consider the floating point number -0 to be in the closed interval [0,1] or not. See my other posting for more details: https://news.ycombinator.com/item?id=13772578 https://news.ycombinator.com/item?id=13772578
- ldarby 10y agoI had a similar question a while ago: how many decimal digits does it take to represent the smallest possible 80 bit float. The answer is ~16000: #include <stdio.h> int main(int argc, char **argv) { unsigned long long int mant, exp ; mant = 0; exp = 1; typedef struct _bitfield80 { unsigned int sign:1; signed int exp:15; unsigned long long int mant:64; } bitfield80; union { long double a; bitfield80 b; } union80; union80.b.sign = 0; union80.b.mant = mant; union80.b.exp = exp; printf ("%0.17000Lf\n", union80.a); return 0; }
- jacobolus 10y agoDepends what you mean by “represent”. The smallest positive “denormal” 80-bit float is (I think) 2^(2 − 2^(14)). I just represented it using 5 decimal digits and two minus signs. :-)
- yiyus 10y agoThe Berry paradox takes this a bit further. It may appear that "the least integer not nameable in fewer than nineteen syllables" is 111777. But "the least integer not nameable in fewer than nineteen syllables" is itself a name consisting of only eighteen syllables, and therefore the least integer not nameable in fewer than nineteen syllables can be named using only eighteen syllables (!). There are alternative expressions, for example wikipedia mentions "the smallest positive integer not definable in fewer than twelve words" and "the smallest positive integer not definable in under sixty letters".
- kumartanmay 10y agoWhat is the practical application of this?
- paulddraper 10y agoCurrently working on monetization strategy. Doing A/B tests with ads. Looking for first round investors.
- ejanus 10y ago): I will buy your IPO.
- js8 10y agoSlightly OT but regarding floats - I was wondering if we could get by just with an exponent and ditch the mantissa. Each number would be represented as an integer exponent of 2^-n for n corresponding to the precision.
- yason 10y agoI don't like the divisions, though, and all the analysis that comes with it. A way that is intuitively more robust would be to generate 23 or 52 random bits from an integer RNG for the mantissa (given you trust you integer RNG is unbiased). For example, take a random uint64_t, clear the sign bit, rewrite the exponent with a predefined value, and let the mantissa be untouched. That will give you a random floating point number in the range between 0.5-1.0, 1.0-2.0, or 2.0-4.0 etc, depending on the exponent you choose. You can trust that the value is entirely random to the precision offered by the mantissa's size. Then you can control the accumulation of error by what you choose to do with the random number. You still can't get to numbers that aren't representable by floating point, of course, but everything will start from the most random and unbiased value you can think of. You might have to introduce some error by subtracting the lower bound and multiplying appropriately to get to your desired range. Or, if you have the luxury to choose your desired range appropriately, you might be able to use the random value directly.
- jxy 10y agoHitting each representable floating point number with an equal probability does not generate an approximately uniform distribution of [0,1). For a sufficiently small positive number, eps, you have to have equal probabilities of numbers falling in [0,eps) and [0.5,0.5+eps) for a uniform distribution, and using random bits would fail this requirement.
- Certhas 10y agoUmmm... maybe I am mistaken, but as the fp numbers are not uniform in [0,1] chances are I don't want to pick one at random. Rather I want to pick a fp representation of a random real between 0 and 1. In that case the readers suggested strategy seems fine. Am I wrong?
- petters 10y agoThe author says in a comment > If hitting exactly zero is much less probable than hitting exactly 0.5, then I would argue that you do not have a uniform distribution… But due to the non-uniformity of floating point numbers, I think the author is wrong here. We can think of each floating point number as an interval. The probability that it is picked should ideally be equal to the size of the interval.
- Certhas 10y agoExactly.
- The_suffocated 10y agoYes. The effect of having a coarser partition around a mesh point is countered by the effect of a higher frequency of hitting that partition. This actually is the essence of importance sampling. For the purposes of numerical integration, as long as the integrand is relatively smooth with respect to the partition size, there shouldn't raise any serious problem. On the contrary, if the integrand does vary wildly between two adjacent floating point numbers, then the real issue here is that the precision (single, double, quadruple, etc.) used is not fine enough, rather than the deviation from uniform distribution.
- riprowan 10y agoI can't believe I'm the only person to ask "what bit depth?" There is a pretty big assumption baked into the title. Edit: hi, I see that I made a mistake, can someone correct my misunderstanding?
- deleted 10y ago[deleted]
- pharrington 10y agoIEEE 754 floats are 32-bit. Doubles are 64-bit.
- aethertron 10y agoThe more I read about the gnarly details of floating point specs and implementations, the more they look like a messy hack. I think it'd be nice to just use rational numbers in my programs.