When evaluating geometric predicates with floating-point arithmetic, roundoff error can cause programs to make incorrect or inconsistent branching decisions. Jonathan Shewchuk refined and applied arbitrary precision floating-point techniques developed by Douglas Preist and others to the most commonly used geometric predicates. His adaptively evaluated predicates guarantee that their result is consonant with an exact evaluation and allow for the robust implementation of algorithms designed for Real-RAM machines.

Shewchuk’s technique is based on a structure called an expansion. An expansion is a set of regular floating point numbers whose exact sum is equal to the number that the expansion represents. He requires expansions to be nonoverlapping and sorted by magnitude ( largest, smallest). Two floating-point values and are nonoverlapping if the least significant nonzero bit of is more significant than the most significant nonzero bit of , or vice versa. The number zero does not overlap any number. Formally, and are nonoverlapping if there exist integers and such that and , or and .

Given four single-precision IEEE-754 floating-point numbers, a, b, c, and d, we want to know whether |a - b| < |c - d|. Will the following code always give the same answer that we would get if we performed all operations with infinite precision?

bool AbsDiffLT(float a, float b, float c, float d)
{
    return fabsf(a - b) < fabsf(c - d);
}