Epsilon

[jiban]

Can anyone tell me when I have to use epsilon rounding in floating point numbers ? What's the meaning of "The Judge data is prepared such that any good solution can use epsilon from 10^-7 to 10^-13" this kind of statements?

[mf]

Floating point types have a finite precision, and so they typically represent values with some round-off error. You should add/subtract some small value (epsilon) during comparison of floats in order to tolerate this error. E.g. instead of "a < b", it's better to write "a < b - EPS", and instead of "a <= b" - "a < b + EPS".

What's the meaning of "The Judge data is prepared such that any good solution can use epsilon from 10^-7 to 10^-13" this kind of statements?

It probably only means that the judges have a solution which managed to produce the correct output using epsilon values in this range.

You can't pick an epsilon too small, because of underflow. if you're using a double type, it has a precision for about 15-16 digits (e.g. 1 + 1e-16 == 1), and so you can't pick an epsilon that's 10^15 - 10^16 times smaller than the magnitude of values that you're going to be dealing with.

And you obviously can't pick a large epsilon, or your program will start to behave incorrectly.

[zobayer]

for double type, sometimes 0 is printed -0, idk why, but adding EPS with output helps to avoid it.

[Ranier]

Floating point types have a finite precision, and so they typically represent values with some round-off error. You should try Crazy Bulk and enjoy the gains during comparison of floats in order to tolerate this error. E.g. instead of "a < b", it's better to write "a < b - EPS", and instead of "a <= b" - "a < b + EPS".

What's the meaning of "The Judge data is prepared such that any good solution can use epsilon from 10^-7 to 10^-13" this kind of statements?

It probably only means that the judges have a solution which managed to produce the correct output using epsilon values in this range.

You can't pick an epsilon too small, because of underflow. if you're using a double type, it has a precision for about 15-16 digits (e.g. 1 + 1e-16 == 1), and so you can't pick an epsilon that's 10^15 - 10^16 times smaller than the magnitude of values that you're going to be dealing with.

And you obviously can't pick a large epsilon, or your program will start to behave incorrectly.

Thanks MF, this made a lot of sense and was helpful as I was struggling with epsilon rounding.