Robust Geometry

Replies to This Discussion

Permalink Reply by Ortler Mark on June 24, 2016 at 1:06pm

Hey Tom,

Good questions!
Independence is the major reason, but also exactness...

A simple TestCase which fails hard:

(sure, this isn't a real-world example, its just simple arithmetic. But I guess important to be correct/robust)

[TestMethod]
public void SimpleArithmetic()
{
    double a = 12312.23223213;
    double b = 12455343.123187843;

    var xa = new ExactNummeric(a);
    var xb = new ExactNummeric(b);

    ExactNummeric xr = (xa + xb + xb) * xa * xb;
    ExactNummeric xrs = (xa * xa * xb + xb * xa * xb + xb * xa * xb);
    ExactNummeric xre = xr - xrs;

    double r = (a + b + b) * a * b;
    double s = (a * a * b + b * a * b + b * a * b);
    double e = r - s;

    double xrd = xre;

    Assert.AreEqual(0d, xrd);
    Assert.AreNotEqual(0d, e);
}

The second Assert:

Expected = 0
Actual = 1024 (variable 'e')

(For testing, there are .cs files attached)

gaußian solver
I'm going to have a look at this. thanks to point this out. I had a quick look; looks promising. But I have to have a deeper look... In the meantime, thanks...

Attachments:

• Exact.zip, 4 KB

Permalink Reply by Arend on July 6, 2016 at 7:43am

It's not simple arithmetic. You found out limitations of floating points numbers.

Aside from that your testcase is comparing two floating point numbers without a "epsilon" value (some would argue this to be mortal sin). There are much more cases where two floating points will not be exactly the same.

You correctly point out that there's a limitation around 15 to 17 digits. (s/r are about this size). In proportion the error between the two numbers is about 2.67E-16.

Not sure what you're trying to accomplish with the ExactArithmatic / ExactNumber? But if you change the type from double to decimal in C#, this testcase will succeed.

decimal a = 12312.23223213M;
decimal b = 12455343.123187843M;
decimal r = (a + b + b) * a * b;
decimal s = (a * a * b + b * a * b + b * a * b);
decimal e = r - s;

// e = 0

.NET floating point numbers:

https://msdn.microsoft.com/en-us/library/9ahet949.aspx|

Floating point guide: http://floating-point-gui.de/

This is also why you never should compare floating point numbers to check if they're exact, but if they're close enough. 

I still have no clue where you would want to be going from here? What problem are you trying to solve?