Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

It's OK to compare floating-points for equality

lisyarus.github.io

Post reply on HN
Print view View original

41–50 of 150 posts

Re: It's OK to compare floating-points for equality

#41

Post by magicalhippo »

TomatoCo wrote: post #31
hmry wrote: post #17

Earlier quoted context omitted.

Is there any constant more misused in compsci than ieee epsilon? :) It's defined as the difference between 1.0 and the smallest number larger than 1.0. More usefully, it's the spacing between adjacent representable float numbers in the range 1.0 to 2.0. Because floats get less precise at every integer power of two, it's impossible for two numbers greater than or equal to 2.0 to be epsilon apart. The spacing between 2…

The term I've seen a lot is https://en.wikipedia.org/wiki/Unit_in_the_last_place So I'd probably rewrite that code to first find the ulp of the larger of the abs of a and b and then assert that their difference is less than or equal to that. Edit: Or maybe the smaller of the abs of the two, I haven't totally thought through the consequences. It might not matter, because the ulps will only differ when the numbers are…

This is what was done to a raytracer I used. People kept making large-scale scenes with intricate details, think detailed ring placed on table in a room with a huge field in view through the window. For a while one could override the fixed epsilon based on scene scale, but for such high dynamic range scenes a fixed epsilon just didn't cut it.

IIRC it would compute the "dynamic" epsilon value essentially by adding one to the mantissa (treated as an integer) to get the next possible float. Then subtract from that the initial value to get the dynamic epsilon value.

Definitely use library functions if you got 'em though.

Re: It's OK to compare floating-points for equality

#42

Post by MarkusQ »

rpdillon wrote: post #15
demorro wrote: post #13

I guess I'm confused. I thought epsilon was the smallest possible value to account for accuracy drift across the range of a floating point representation, not just "1e-4". Done some reading. Thanks to the article to waking me up to this fact at least. I didn't realize that the epsilon provided by languages tends to be the one that only works around 1.0, and if you want to use episilons globally (which the article wou…

Yeah, I'm not sure how widespread the knowledge is that floating point trades precision for magnitude. Its obvious if you know the implementation, but I'm not sure most folks do.

Always remember https://m.xkcd.com/2501/

Re: It's OK to compare floating-points for equality

#44

Post by bee_rider »

jph wrote: post #7

I have this floating-point problem at scale and will donate $100 to the author, or to anyone here, who can improve my code the most. The Rust code in the assert_f64_eq macro is: if (a >= b && a - b I'm the author of the Rust assertables crate. It provides floating-point assert macros much as described in the article. https://github.com/SixArm/assertables-rust-crate/blob/main/s... If there's a way to make it more prec…

EQ should be exactly equal, I think. Although we often (incorrectly) model floats as a real plus some non-deterministic error, there are cases where you can expect an exact bit pattern, and that’s what EQ is for (the obvious example is, you could be writing a library and accept a scaling factor from the user—scaling factors of 1 or 0 allow you to optimize).

You probably also want an isclose and probably want to push most users toward using that.

Re: It's OK to compare floating-points for equality

#45

Post by jcranmer »

jph wrote: post #7

I have this floating-point problem at scale and will donate $100 to the author, or to anyone here, who can improve my code the most. The Rust code in the assert_f64_eq macro is: if (a >= b && a - b I'm the author of the Rust assertables crate. It provides floating-point assert macros much as described in the article. https://github.com/SixArm/assertables-rust-crate/blob/main/s... If there's a way to make it more prec…

Everyone has already made several comments on the incorrect use of EPSILON here, but there's one more thing I want to add that hasn't yet been mentioned:

EPSILON = (1 ulp for numbers in the range [1, 2)). is a lousy choice for tolerance. Every operation whose result is in the range [1, 2) has a mathematical absolute error of ½ ulp. Doing just a few operations in a row has a chance to make the error term larger than your tolerance, simply because of the inherent inaccuracy of floating-point operations. Randomly generate a few doubles in the range [1, 10], then randomize the list and compute the sum of different random orders in the list, and your assertion should fail. I'd guess you haven't run into this issue because either very few people are using this particular assertion, or the people who do happen to be testing it in cases where the result is fully deterministic.

If you look at professional solvers for numerical algorithms, one of the things you'll notice is that not only is the (relative!) tolerance tunable, but there's actually several different tolerance values. The HiGHS linear solver for example uses 5 different tolerance values for its simplex algorithm. Furthermore, the default values for these tolerances tend to be in the region of 10^-6 - 10^-10... about the square root of f64::EPSILON. There's a basic rule of thumb in numerical analysis that you need your internal working precision to be roughly twice the number of digits as your output precision.

Re: It's OK to compare floating-points for equality

#46

Post by adrian_b »

amelius wrote: post #22

Think about this. It's silly to use floating point numbers to represent geometry, because it gives coordinates closer to the origin more precision and in most cases the origin is just an arbitrary point.

You are right, but only for a certain meaning of the word "geometry".

If "geometry" refers to the geometry of an affine space, i.e. a space of points, then indeed there is nothing special about any point that is chosen as the origin and no reason do desire lower tolerances for the coordinates of points close to the current origin.

Therefore for the coordinates of points in an affine space, using fixed-point numbers would be a better choice. There are also other quantities for which usually floating-point numbers are used, despite the fact that fixed-point numbers are preferable, e.g. angles and logarithms.

On the other hand, if you work with the vector space associated to an affine space, i.e. with the set of displacements from one point to another, then the origin is special, i.e. it corresponds with no displacement. For the components of a vector, floating-point numbers are normally the right representation.

So for the best results, one would need both fixed-point numbers and floating-point numbers in a computer.

These were provided in some early computers, but it is expensive to provide hardware for both, so eventually hardware execution units were provided only for floating-point numbers.

The reason is that fixed-point numbers can be implemented in software with a modest overhead, using operations with integer numbers. The overhead consists in implementing correct rounding, keeping track of the position of the fraction point and doing some extra shifting when multiplications or divisions are done.

In languages that allow the user to define custom types and that allow operator overloading and function overloading, like C++, it is possible to make the use of fixed-point numbers as simple as the use of the floating-point numbers.

Some programming languages, like Ada, have fixed-point numbers among the standard data types. Nevertheless, not all compilers for such programming languages include an implementation for fixed-point numbers that has a good performance.

Re: It's OK to compare floating-points for equality

#47

Post by jstanley »

throwup238 wrote: post #34
vouwfietsman wrote: post #21

This explanation is relatively reductive when it comes to its criticism of computational geometry. The thing with computational geometry is, that its usually someone else's geometry , i.e you have no control over its quality or intention. In other words, whether two points or planes or lines actually align or align within 1e-4 is no longer really mathematically interesting because its all about the intention of the u…

> This is why most geometry kernels (see open cascade) sport things like "fuzzy boolean operations" [0]) that lean into epsilons. These epsilons mask the error-prone supply chain of these meshes that arrive in your program by allowing some tolerance. They don’t just lean into epsilons, the session context tolerance is used for almost every single point classification operation in geometric kernels and many primitives…

> This is a fundamentally unsolvable problem with floating point math

It's a fundamentally unsolvable problem with B-reps! The problem completely disappears with F-reps. (In exchange for some other difficult problems).

Re: It's OK to compare floating-points for equality

#49

Post by sobellian »

jph wrote: post #7

I have this floating-point problem at scale and will donate $100 to the author, or to anyone here, who can improve my code the most. The Rust code in the assert_f64_eq macro is: if (a >= b && a - b I'm the author of the Rust assertables crate. It provides floating-point assert macros much as described in the article. https://github.com/SixArm/assertables-rust-crate/blob/main/s... If there's a way to make it more prec…

Machine eps provides the maximum rounding error for a single op. Let's say I write:

  let y = 2.0;
  let x = sqrt(y);
Now is `x` actually the square root of 2? Of course not - because the digit expansion of sqrt(2) doesn't terminate, the only way to precisely represent it is with symbolics. So what do we actually have? `x` was either rounded up or down to a number that does have an exact FP representation. So, `x` / sqrt(2) is in `[1 - eps, 1 + eps]`. The eps tells you, on a relative scale, the maximum distance to an adjacent FP number for any real number. (Full disclosure, IDK how this interacts with weird stuff like denormals).

Note that in general we can only guarantee hitting this relative error for single ops. More elaborate computations may develop worse error as things compound. But it gets even worse. This error says nothing about errors that don't occur in the machine. For example, say I have a test that takes some experimental data, runs my whiz-bang algorithm, and checks if the result is close to elementary charge of an electron. Now I can't just worry about machine error but also a zillion different kinds of experimental error.

There are also cases where we want to enforce a contract on a number so we stay within acceptable domains. Author alluded to this. For example - if I compute some `x` s.t. I'm later going to take `acos(x)`, `x` had better be between `[-1, 1]`. `x >= -1 - EPS && x - "I want to relax exact equality because my computation has errors" -> Make `assert_rel_tol` and `assert_abs_tol`.

- "I want to enforce determinism" -> exact equality.

- "I want to enforce a domain" -> exact comparison

Your code here is using eps for controlling absolute error, which is already not great since eps is about relative error. Unfortunately your assertion degenerates to `a == b` for large numbers but is extremely loose for small numbers.

Re: It's OK to compare floating-points for equality

#50

Post by valicord »

ryandrake wrote: post #38
rpdillon wrote: post #15

Earlier quoted context omitted.

Yeah, I'm not sure how widespread the knowledge is that floating point trades precision for magnitude. Its obvious if you know the implementation, but I'm not sure most folks do.

I remember having convincing a few coworkers that the number of distinct floating point values between 0.0 and 1.0 is the same as the number of values between 1.0 and infinity. They must not be teaching this properly anymore. Are there no longer courses that explain the basics of floating point representation? I was arguing that we could squeeze a tiny bit more precision out of our angle types by storing angles in ra…

Wait this doesn't make sense. Yes you'd get smaller absolute error in radians, but it doesn't really help because it's different units. Relative error is the same in degrees and radians, that's the whole point of exponential representation. All you're doing is adding a fixed offset to the exponent, but it doesn't give you any more precision when converting to radians
Post reply on HN