Live data from Hacker News

Examples of floating point problems

jvns.ca

51–60 of 179 posts

Re: Examples of floating point problems

#51
post #18
post #16

One thing that pains me about this kind of zoo of problems is that people often have the takeaway, "floating point is full of unknowable, random errors, never use floating point, you will never understand it." Floating point is amazingly useful! There's a reason why it's implemented in hardware in all modern computers and why every programming language has a built-in type for floats. You should use it! And you should…

> And you should understand that most of its limitations are an inherent mathematical and fundamental limitation, it is logically impossible to do better on most of its limitations You can do exact real arithmetic. But this is only done by people who prove theorems with computers - or by the Android calculator! https://en.wikipedia.org/wiki/Computable_analysis Other alternatives (also niche) are exact rational arithm…

I wouldn't call computable reals the reals. They are a subset of measure zero. Perhaps all we sentient beings can aspire to use, but still short of the glory of the completed infinities that even one arbitrary real represents.

One half : )

Re: Examples of floating point problems

#52
post #34

> Javascript only has floating point numbers – it doesn’t have an integer type. Can anyone justify this? Do JS developers prefer not having exact integers, or is this something that everyone just kinda deals with?

> not having exact integers

What do you mean? Floating-point arithmetic is, by design, exact for small integers. The result of adding 2.0 to 3.0 is exactly 5.0. This is one of the few cases where it is perfectly legitimate to compare floats for equality.

In fact, using 64-bit doubles to represent ints you get way more ints than using plain 32-bit ints. Thus, choosing doubles to represent integers makes perfect sense (unless you worry about wasting a bit of memory and performance).

Re: Examples of floating point problems

#53
post #18
post #16

One thing that pains me about this kind of zoo of problems is that people often have the takeaway, "floating point is full of unknowable, random errors, never use floating point, you will never understand it." Floating point is amazingly useful! There's a reason why it's implemented in hardware in all modern computers and why every programming language has a built-in type for floats. You should use it! And you should…

> And you should understand that most of its limitations are an inherent mathematical and fundamental limitation, it is logically impossible to do better on most of its limitations You can do exact real arithmetic. But this is only done by people who prove theorems with computers - or by the Android calculator! https://en.wikipedia.org/wiki/Computable_analysis Other alternatives (also niche) are exact rational arithm…

These are only relevant in some circumstances. For example, a calculator is typically bounded in the number of operations you can perform to a small number (humans don’t add millions of numbers). This allows for certain representations that don’t make sense elsewhere.

Re: Examples of floating point problems

#54
post #41
post #34

> Javascript only has floating point numbers – it doesn’t have an integer type. Can anyone justify this? Do JS developers prefer not having exact integers, or is this something that everyone just kinda deals with?

I believe this is technically inaccurate; while Javascript groups most of the number values under, well, "number", modern underlying implementations may resort to perform integer operations when they recognize it is possible. There are also a couple hacks you can do with bit operations to "work" with integers, although I don't remember them off the top of my head - typically used for truncating and whatnot and was ma…

The way runtimes optimize arithmetic is an implementation detail and must conform to IEEE-754.

Re: Examples of floating point problems

#55
post #8
post #7

My favorite floating point weirdness is that 0.1 can't be exactly represented in floating point.

Isn't it equally weird that 1/3 can't be exactly represented in decimal?

The reason why the 0.1 case is weird (unexpected) is that we use decimal notation in floating-point constants (in source code, in formats like JSON, and in UI number inputs), but the value that the constant actually ends up representing is really the closest binary number, where in addition the closeness depends on the FP precision used. If we would write FP values in binary or hexadecimal (which some languages support), the issue wouldn’t arise.

Re: Examples of floating point problems

#56
post #48
post #43

Example 4 mentions that the result might be different with the same code. Here is an example that is particularly counter-intuitive. Some CPU have the instruction FMA(a,b,c) = ab + c and it is guaranteed to be rounded to the nearest float. You might think that using FMA will lead to more accurate results, which is true most of the time. However, assume that you want to compute a dot product between 2 orthogonal vecto…

In general with reals with any source of error anywhere, this caution about equality is always correct. the odds of two reals being equal is zero.

I have an exception that proves the rule. I thought about responding to Julia's call, but decided this was too subtle. But here we go...

A central primitive in 2D computational geometry is the orientation problem; in this case deciding whether a point lies to the left or right of a line. In real arithmetic, the classic way to solve it is to set up the line equation (so the value is zero for points on the line), then evaluate that for the given point and test the sign.

The problem is of course that for points very near the line, roundoff error can give the wrong answer, it is in fact an example of cancellation. The problem has an exact answer, and can be solved with rational numbers, or in a related technique detecting when you're in the danger zone and upping the floating point precision just in those cases. (This technique is the basis of Jonathan Shewchuk's thesis).

However, in work I'm doing, I want to take a different approach. If the y coordinate of the point matches the y coordinate of one of the endpoints of the line, then you can tell orientation exactly by comparing the x coordinates. In other cases, either you're far enough away that you know you won't get the wrong answer due to roundoff, or you can subdivide the line at that y coordinate. Then you get an orientation result that is not necessarily exactly correct wrt the original line, but you can count on it being consistent, which is what you really care about.

So the ironic thing is that if you had a lint that said, "exact floating point equality is dangerous, you should use a within-epsilon test instead," it would break the reasoning outlined above, and you could no longer count on the orientations being consistent.

As I said, though, this is a very special case. Almost always, it is better to use a fuzzy test over exact equality, and I can also list times I've been bitten by that (especially in fastmath conditions, which are hard to avoid when you're doing GPU programming).

Re: Examples of floating point problems

#57
post #44
post #16

One thing that pains me about this kind of zoo of problems is that people often have the takeaway, "floating point is full of unknowable, random errors, never use floating point, you will never understand it." Floating point is amazingly useful! There's a reason why it's implemented in hardware in all modern computers and why every programming language has a built-in type for floats. You should use it! And you should…

> 3. You might not like that floats are in binary, which makes decimal arithmetic look weird. But doing decimal arithmetic does not get rid of numerical error, see point 1 (and binary arithmetic thinks your decimal arithmetic looks weird too). One thing that I suspect trips people a lot is decimal string/literal (binary) float conversions instead of the floating point math itself. This includes the classic 0.1+0.2 th…

The only implementation of IEEE754 decimals I've ever seen is in Python's Decimal package. Is there an easily-available implementation anywhere else?

Re: Examples of floating point problems

#58
post #22

If you have only a couple of minutes to develop a mental model of floating-point numbers (and you have none currently), the most valuable thing IMO would be to spend them staring at a diagram like this one: https://upload.wikimedia.org/wikipedia/commons/b/b6/Floating... (uploaded to Wikipedia by user Joeleoj123 in 2020, made using Microsoft Paint) — it already covers the main things you need to know about floating-po…

If you have even less time, just think of them as representing physical measurements made with practical instruments and the math done with analog equipment. The common cause of floating point problems is usually treating them as a mathematical ideal. The quirks appear at the extremes when you try to to un-physical things with them. You can't measure exactly 0 V with a voltmeter, or use an instrument for measuring th…

Thanks, I actually edited my post (made the second paragraph longer) after seeing your comment. The "physical" / "analog" idea does help in one direction (prevents us from relying on floating-point numbers in unsafe ways) but I think it brings us too close to the "superstition" end of the spectrum, where we start to think that floating-point operations are non-deterministic, start doubting whether we can rely on (say) the operation 2.0 + 3.0 giving exactly 5.0 (we can!), whether addition is commutative (it is, if working with non-NaN floats) and so on.

You could argue that it's "safe" to distrust floating-point entirely, but I find it more comforting to be able to take at least some things as solid and reason about them, to refine my mental model of when errors can happen and not happen, etc.

Edit: See also the floating point isn’t “bad” or random section that the author just added to the post (https://twitter.com/b0rk/status/1613986022534135809).

Re: Examples of floating point problems

#59

Story time. Back in university I was taking part in programming competition. I don't remember the exact details of a problem, but it was expected to be solved as a dynamic problem with dp[n][n] as an answer, n < 1000. But, wrangling some numbers around one could show that dp[n][n] = dp[n-1][n-1] + 1/n, and the answer was just the sum of first N elements of harmonic series. Unluckily for us the intended solution had w…

They didn't take into account that floats come with an estimated uncertainty, and that values that are the same within the limits of experimental error are identical? That's a really badly set problem!

Re: Examples of floating point problems

#60
post #43

Example 4 mentions that the result might be different with the same code. Here is an example that is particularly counter-intuitive. Some CPU have the instruction FMA(a,b,c) = ab + c and it is guaranteed to be rounded to the nearest float. You might think that using FMA will lead to more accurate results, which is true most of the time. However, assume that you want to compute a dot product between 2 orthogonal vecto…

Yes, and this is not just a theoretical concern: There was an article here [1] in 2021 claiming that Apple M1's FMA implementation had "flaws". There was actually no such flaw. Instead, the author was caught off guard by the very phenomenon you are describing.

[1] https://news.ycombinator.com/item?id=27880461

Post reply on HN