Benezivas / algobattle

Let teams compete by making them create hard instances and fast solvers for problems of your choice. Then pitch these instances and solvers against one another. All language-agnostic.
https://algobattle.org
MIT License
8 stars 3 forks source link

Simple, safe float comparisons #128

Closed ImogenBits closed 1 year ago

ImogenBits commented 1 year ago

This adds an easy way to perform safe float comparisons, to fix the problems we mentioned in the meeting last week. I think the way this works is best illustrated with an example:

Let's say the problem instances contain a set of points and the solution contains a circle of some radius that should cover as many of these points as possible. The issue we now run into when naively comparing

distance(center, point) <= size

is that the instance points might be placed in such a way that this calculated distance is bigger than size because of float rounding errors. This can be solved by instead comparing

distance(center, point) <= size + epsilon

But this will now run into issues if the generating team intentionally places points in such a way that the rounding error occur at size + epsilon rather than just size. Another problem case is when the floats involved are being computed with big intermediate values, then the rounding errors might be bigger than the constant epsilon.

This PR lets you easily sidestep both issues by just comparing like this:

distance(center, point) <= LaxComp(size, role)

or alternatively

lax_comp(distance(center, point), "<=", size, role)

depending on your syntax preference. This will automatically perform the comparison including an epsilon that adjusts to the total size of the involved values and doubles this fudge factor for the solving team.

Benezivas commented 1 year ago

This looks like a good way to handle float rounding imprecisions, thank you