10 ms·
What Every Computer Scientist Should Know About Floating-Point Arithmetic (1991)
- s9w 6y agoThat's quite a lot. The by far most important things for me: Floats guarantee at least 7, and doubles at least 15 significant decimal digits. That's regularly surprisingly low to many devs.
- deleted 6y ago[deleted]
- hnick 6y agoThe real problem I see mostly happen when arithmetic gets involved. Two simple and precise floats added or subtracted can get you something like 5.00000000001 if you aren't careful. A fairly innocuous perl snippet shows this: DB<1> $a+=0.1 for 1..10; print $a - 1 -1.11022302462516e-16 I ran into a bug like this on a website, I don't know what they were doing to the inputs but a simple 60.9 or similar turned into 60.9000000001 and tripped up the back-end service.
- slavik81 6y agoThe problem is that they aren't precise floats. 0.1 has no finite representation in binary. It's an infinite repeating string of digits, like 1/3rd is in decimal. Thus, when you add a bunch of them together, the inherent error in rounding them off at some finite number of digits slowly adds up. The same is true of all multiples of 0.1, unless they're also a multiple of 0.5. Hence why your 60.9 is not actually 60.9. It was never exact to begin with.
- hnick 6y agoYes, that is true. But usually symptoms don't surface until errors accumulate which is why I found that web form interesting. 'Precise' was the wrong word. What I meant was the system reports back the exact entered value 0.1 (rather than what it has in memory, which is 0.100000001490116119384765625 according to https://www.h-schmidt.net/FloatConverter/IEEE754.html https://www.h-schmidt.net/FloatConverter/IEEE754.html). Most programs will do this fairly well. I confirmed javascript is entirely capable of storing and retrieving the number I entered, so I'm not entirely sure what they were doing to confuse it :) Must have been some secret maths.
- DarkWiiPlayer 6y ago> 0.1 has no finite representation in binary. b1 / b1010 I don't see the problem. Did you mean to say it has no finite representation in the IEEE float format? > It was never exact to begin with. But the format sadly gets used in situations where people expect it to be reasonably accurate, where it isn't, because developers either underestimate the "reasonable" or overestimate the "accurate" part. It's just sad that most mainstream programming languages have no native accurate data type for rational numbers.
- Gracana 6y ago> Did you mean to say it has no finite representation in the IEEE float format? Of course that's implied.
- DarkWiiPlayer 6y agoIt was a rhetoric question; I just wanted to point out that people blame these inaccuracies on "binary representations" when in reality it's just this one binary representation that's broken.
- deleted 6y ago[deleted]
- account42 6y agoSo are you saying that ⅓ has a finite presentation in decimal? Finite binary rationals ⊋ finite binary numbers.
- DarkWiiPlayer 6y ago> So are you saying that ⅓ has a finite presentation in decimal? Yes: ⅓
- slavik81 6y agoI meant in positional notation, but most people know that as "decimal notation". Unfortunately, that implies base 10, so I avoided the term. I gave both an example in binary and an example in decimal to clarify my imprecise terminology. I worry that by objecting only to the binary example, you may confuse people into thinking the two are different.
- kstenerud 6y agoIt may seem low, but it's really not. At 6 significant digits, you'd have a margin of error of a thousandth of an inch when measuring a football field.
- 0xffff2 6y agoCounterpoint: At 6 significant digits you have a margin of error of thousandths of a millimeter when measuring degrees longitude near the prime meridian, but the error balloons to whole meters when measuring longitudes in Australia. I have a piece of software that I wrote ages ago where I looked at the max error in the US and concluded that 32bit floats were enough. This made sense since at the time I was reasonably confident that the tool would only be used with locations in the continental US and it simplified my architecture. Fast forward a few years and we ended up open sourcing the tool and people started using it all over the world. I'm still dealing with the fallout to this day. I'm dreading the day that the tool gets used in some inter-planetary context and I have to repeat all of the work to add support for 128 bit/arbitrary precision location data.
- T-hawk 6y agoSure, that's low, depending on context. At 6 significant digits, a million-dollar bank account would have a margin of error of up to +/- 5 dollars. And if you add up a million of any item with 6 significant digits, that's enough for inaccuracy to propagate all the way into your first significant digit. (It would require systematic inaccuracy in one direction, but there are certainly data sets and contexts where that would happen.)
- kstenerud 6y agohttps://dzone.com/articles/never-use-float-and-double-for-monetary-calculatio https://dzone.com/articles/never-use-float-and-double-for-mo...
- s9w 6y agoYou are also not able to represent your yearly salary to the cent. At least if you're American haha
- bch 6y agoOriginal paper (PDF): https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf
- dang 6y agoPosted 30 times, but most of the comments are about how many times it has been posted. Here are the on-topic threads: 2017 (just a bit): https://news.ycombinator.com/item?id=13431299 https://news.ycombinator.com/item?id=13431299 2012: https://news.ycombinator.com/item?id=4815399 https://news.ycombinator.com/item?id=4815399 2010 (not a good year): https://news.ycombinator.com/item?id=1982332 https://news.ycombinator.com/item?id=1982332 2009 (also pretty bad): https://news.ycombinator.com/item?id=687604 https://news.ycombinator.com/item?id=687604 https://hn.algolia.com/?query=What%20Every%20Computer%20Scientist%20Should%20Know%20About%20Floating-Point%20Arithmetic&&sort=byDate&dateRange=all&type=story&storyText=none&prefix https://hn.algolia.com/?query=What%20Every%20Computer%20Scie...
- seren 6y agoOddly enough I got an issue with float this week, 2 systems are communicating by transmitting float (rather needlessly I would add) and the conversion from float seems to be implemented differently on both systems, resulting in discrepancy sometimes. This is kind of textbook example of an obvious bug but still surprising when you find it.
- enriquto 6y agoI do not understand what you mean. If you "convert" a float to a float it shouldn't change anything? As long as you keep to floats there should be no problem.
- nestorD 6y agoYou could run into problems with little endians and big endians if you do a binary tranfer or, more likely, have a lossy float->string->float conversion.
- enriquto 6y agoThat seems to be more a problem of strings that of floats, then.
- rini17 6y agoStrings have nothing to do with the issue that there is no widespread lossless text exchange format for FP. Instead we round FP numbers while encoding (like "0.3") and then "deround" it while decoding. (Lossless base10 encoding of 0.3 single precision would be like "10066330*2^-25"..not very readable).
- dahfizz 6y ago> the issue that there is no widespread lossless text exchange format for FP. If you have to use strings as the intermediate representation (why?) Then printf("%x") and scanf("%x") is perfectly lossless and widespread. The only thing that's lossy is converting floats to decimal point numbers, which is absolutely silly if it's just two machines communicating.
- henvic 6y agoThis is gold. I've been forwarding this link for everyone who says they are using float for storing currency values (money, $$$) since forever.
- nurettin 6y agoI use floating point for currency (decimal(19, 10) in db, double precision and rounding functions in memory) and there is nothing wrong with it. If I used integers for everything, I would have to take special care of every mathematical operation instead of rounding the final result to desired precision.
- burntoutfire 6y ago"Decimal" is not floating point... On the contrary, it's fixed point, as you set fixed amount of precision both before and after the decimal point. More importantly, "decimal" does not suffer from the arithmetic issues you get when using IEEE 754 floating point.
- nurettin 6y agoyes, what is your point?
- bjourne 6y agoA follow up to this classic article could be titled "What every language designer should know about humans." :) Floats are among the least user-friendly ways to do decimal arithmetic. They aren't even that fast anymore given the resurgence of fixed point arithmetic in hpc. Imo, in 2020 we should have had mainstream languages in which (2^(1/2))^2 == 2. It's not rocket science. :) Float truncation is a little like an OS silently converting a user's flac collection to mp3 because it was running low on disk space.
- rectang 6y agoWhat primitive numerical type should languages have instead? Can you show us some sample code illustrating how this type would be used for tasks where floats are typically deployed today?
- bjourne 6y agoThe natural type for numbers is expression trees. That's roughly what dl frameworks like TensorFlow and PyTorch does and allows for things like automatic differentiation and distributed computation. For any expression, the runtime is allowed to reduce it only if it can prove that the reduction is value preserving. For example 3/1 => 3, (1/3)*3 => 1, (e^(ln(x)/2))^2 => x and 10/14 => 5/7. But 5/7 cannot be reduced further. The primitive numerical type that should be used instead of floating point is the rational. Rationals have their own problems (no numeric type is perfect) but their problems are much easier to manage than float's.
- rectang 6y agoThanks! Let me follow up by exploring a specific use case: scoring in a Lucene-style search engine, where arbitrarily complex queries repeatedly scale a floating point "score" value which measures document relevancy against a query. Sometimes documents which ought to produce equal scores against a given query (if scoring were evaluated using real number math) do not produce equal scores in practice because of floating point limitations such as not supporting associativity or commutativity. Let's assume we are willing to sacrifice performance for correctness to address this issue. 1) If scores were tracked as expression trees, could this problem be eliminated entirely? If so, I'd hazard a guess that while you'd eventually run into edge case issues such as needing arbitrarily large integers, in practice the CPU cost to track scores as expression trees rather than floats would be increased by a roughly constant factor. 2) If scores were tracked using a rational instead of a float, could the problem of tied scores be eliminated? I suspect that the answer to that is no, because you will quckly run up against integer precision limitations in the numerator/denominator of the rational type.
- deleted 6y ago[deleted]
- randcraw 6y agoSome historical context... IEEE 754 (the current floating point standard in H/W and S/W) arose in 1985, only 6 years before this paper. Before that, floating point representations were often proprietary (e.g. Cray or IBM). Back then, most microprocessors did not have floating point hardware, so most non-scientific apps avoided floating point operations and booleans using them. Few coders had much experience with floating point unless they were engineers or scientists. This paper broke new-ish ground in introducing 'the rest of us' to the nonlinear representation space of digital scientific numbers and subtleties of roundoff & inaccuracy inherent in math-intensive libraries and scientific math functions. It still usefully covers more ground in that space than most of today's BSCS degree programs.
- phkahler 6y agoI'm still hoping posits make it one of these days.
- bass_case 6y agoHello imposter syndrome my old friend
- brudgers 6y agoComputer science is hard and even Knuth is humbled by it. And he's been writing several programs a week for about sixty years.
- kristopolous 6y agoI think what every programmer should know is probably only 4 words: They're approximations. Use accordingly.