0

When I read a book today, I found the following code to check whether two lines intersect:

struct Line{
    static double epsilon = 0.000001;   
    double slope;
    double yintercept;
};

bool intersect(Line& line_1, Line& line_2)
{
    bool ret_1 = abs(line_1.slope - line_2.slope) > epsilon;
    bool ret_2 = abs(line_1.yintercept - line_2.yintercept) < epsilon;

    return ret_1 || ret_2;
}

The program uses slope and y-intercept to determine whether two line intersect. However, I am confusing here why we need epsilon? Why cannot directly make use of '==' here?

There is a common below this method. The author says never check for equality with ==. Instead, check if the difference is less than an epsilon value.

Shanpei Zhou
  • 371
  • 1
  • 2
  • 17
  • 2
    http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html – user657267 Apr 16 '14 at 06:37
  • 2
    You should read [What Every Computer Scientist Should Know About Floating-Point Arithmetic](http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html), or the more average-human-friendly version at [floating-point-gui.de](http://floating-point-gui.de/) – Angew is no longer proud of SO Apr 16 '14 at 06:40
  • 2
    Because it is not possible to fit the +- *infinite range* of real numbers into the +- *finite range* that is floating points, unless of course you know how to create a Tardis (which is bigger on the inside than it is on the outside). – jussij Apr 16 '14 at 06:40
  • 1
    The given code would not compile. E:g. the initialized static member of type `double`, the unqualified use of name `epsilon`. In addition the `intersect` function, when corrected for obvious technical errors, does not compute an intersection or whether there is one. If the code is correctly quoted, this means the book of extremely low quality: **BURN IT**. Which book is it? – Cheers and hth. - Alf Apr 16 '14 at 07:06

1 Answers1

4

Some decimal numbers can only be represented with a certain precision on a system. In the case of normal floating point numbers that precision depends on the format of the number (usually IEEE 754). Hardware differences and base constraints can introduce small rounding errors.

There are also other factors which might come into play: when dealing with software floating point calculations you might get irrational numbers or numbers too small to deal with full-precision calculations (i.e. subnormals or denormals). Some compilers treat them as allowed while others flush the result to zero. And some systems also use the so-called fast-math calculation which allows faster results by using hardware circuitry which works with less precision.

All these behaviors force you to put an epsilon, a "tolerance" threshold that covers you by the approximation errors.

If you're dealing with floating point calculations I strongly recommend reading http://download.oracle.com/docs/cd/E19957-01/806-3568/ncg_goldberg.html

Marco A.
  • 43,032
  • 26
  • 132
  • 246
  • -1 "Decimal numbers can only be represented with a certain precision" is incorrect. – Cheers and hth. - Alf Apr 16 '14 at 07:10
  • I think it was clear what I meant, not "1.0" or "1.2" but a very small number. I'll fix it to be more explicit. – Marco A. Apr 16 '14 at 07:23
  • Denormals are not too small to be represented in IEEE format. In fact, IEEE pretty much invented the denormal representation. Not that it matters for `(1.0/3.0)*3.0 == 1.0`, that's nowhere near denormal. Also, it's not at all related to decimal (base 10) either, so those two reasons are insufficient to prove the need for epsilon. – MSalters Apr 16 '14 at 07:30
  • If you use denormals in your computation to calculate small values you'll eventually lose precision, at least with the normal floating point ones. Some architectures deliberately flush these to zero by default (losing even more precision). This, indeed, matters. But I agree that they can be represented and that the main reason is another one, I'll edit it. – Marco A. Apr 16 '14 at 07:55
  • 0 removed downvote (text fixed). – Cheers and hth. - Alf Apr 16 '14 at 10:10
  • But just to be totally clear, C++ supports decimal floating point representations. You can use `std::numeric_limits` to check if your `double` type has a decimal or binary representation. If it has decimal representation, then the precision is about the number of significant digits in that representation, while if the representation is binary (as it usually is), then the precision is more about the fact that many decimal numbers such as `0.2` can't even in principle be represented exactly as binary floating point. – Cheers and hth. - Alf Apr 16 '14 at 13:21