anajin's blog

By anajin, history, 9 years ago, In English

In the latest contest, i got trouble in problem H.
When i want to compare x is lager than y, i use x>y+eps (i learn this from a book), but i get WRONG ANWSER , but when i just use x>y ,then i accept .
I just wonder which one is true. Thx first.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

In my experience, I've only seen epsilons used when comparing for equality, not for greater-than or less-than.

I can see where the y + ε comes from — we consider x and y to be equal if they are within ε of each other, so it makes sense that for a "strictly greater than" operation we would rule that out — but I think we can make a safe assumption that a greater-than or less-than relationship is, unlike equality, preserved in floating-point operations, if you're not going to the limit of the number's precision boundary. This is relevant.

(Anyone please feel free to prove this incorrect if you have a counterexample.)

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i think you use a large eps, try smaller one

try 1e-15 for example

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Contrary to popular belief that you always need to use eps when working with floating point numbers, there are some situations when eps is not needed and it may decrease the precision. If it was like that then it would be builtin. Keep in mind that floating points are deterministic and they perform operations correctly within limits of their precision, and performing operation with the same arguments twice will give exactly the same result. I will give some examples:

  • Finding maximum value (minimum) — no need for eps. When finding maximum from > 2 values, using eps could change the result depending evaluation order, you probably don't want that. There is no reason to choose slightly smaller value just because it was first in list.
  • Finding maximum elements (index of elements with maximum value). In this case it is most likely necessary to use eps and assume that there can be multiple elements with maximum value.
  • Finding convex hull without points on edges, this is when you probably want to use inequality with eps.
  • Binary search. For binary search range it is better to use fixed count of iterations 64 or 100 should be sufficient to get best precision possible as double has only 64 bits. Doing that will decrease the chance of binary search getting stuck or getting WA due to precision. As for calculations in binary search condition most of the time eps is not needed, because slightly changing middle point will also change the values in calculation of condition. Eps would have effect only when l is close to r, and that point it doesn't matter too much.
  • Sorting list of doubles, there is no point in using eps in comparator. But you should probably take similar values into account when processing sorted list.

When possible try to think of what problem are you trying solve by using eps and choose appropriately. It depends on the task if it is worse to have false positives or false negatives.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your detail explanation. :-p