likecs's blog

By likecs, history, 8 years ago, In English

Hello everyone, I have a doubt regarding precision error problems. For example I wrote a code like here.

Initially the numbers I am multiplying are 2, 10, 10, 10 i.e product should be 2000 but what I get is 1999.

I usually see people use some small value like EPS (10^(-6) or 10^(-10)) in their code. Even while comparing double they do it like abs(a-b)<=EPS, then equal else not. They do not do directly like a!=b.

Please someone explain the above observations and how to effectively take care of it in competitions. Many a times, after passing pretest we fail system tests due to precision errors. What value of EPS (epsilon) do you set or decide from the problem constraints. Please discuss your approach.

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

»
8 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

The set of representable numbers on fixed floating point arithmetic is finite, and numbers that do not belong to it are rounded to the nearest representable number. So in general it is very hard to keep perfect precision while doing floating point operations. That's why you don't see things like a!=b.

In terms of competitive programming, first check if you really need floats. If there is a solution with only integers, stick to it.

If you really need them because the problem cannot be done without floats or the answer is a float, then:

  • The epsilon you actually need to set depends on the problem. But take into account that floating point errors propagate through operations, so it may be nice to set a very "small" epsilon like 10 - 9.

  • Try to avoid big numbers calculation. For example if you are asked to compute something like (abc) / (def) then it may be safer to compute it as (a / d)(b / e)(c / f). Even more, if you know that def > abc, then you could compute the inverse and then invert the result. Keep in mind that floating point operations are not necessarily associative or commutative.

  • If you can, normalise any calculation you are doing to the range [0, 1] or [ - 1, 1]. Not only because the product between numbers on these intervals give a number that it is also inside, but because how floating point arithmetic works there are far more representable numbers on that interval (check the pic below).

  • In geometry problems, try to avoid trigonometric functions, especially the tangent. Instead, try to stick to dot products, cross products and similar stuff. They are far more stable and cheap. Also, try to avoid determinants if you have no guarantee about the matrix numbers.
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell what changes can I make in the program link given above so as to avoid that precision in restoring that number?