What is meant by a "Relative Comparison" and an "Absolute Comparison"?

Question

Quoting from this article:

REAL NUMBERS

Binary search can also be used on monotonic functions whose domain is the set of real numbers. Implementing binary search on reals is usually easier than on integers, because you don’t need to watch out for how to move bounds:

binary_search(lo, hi, p):
  while we choose not to terminate:
  mid = lo + (hi - lo) / 2
if p(mid) == true:
  hi = mid
else :
  lo = mid

return lo

Since the set of real numbers is dense, it should be clear that we usually won’t be able to find the exact target value. However, we can quickly find some x such that f(x) is within some tolerance of the border between no and yes. We have two ways of deciding when to terminate: terminate when the search space gets smaller than some predetermined bound (say 10-12) or do a fixed number of iterations. On Topcoder, your best bet is to just use a few hundred iterations, this will give you the best possible precision without too much thinking. 100 iterations will reduce the search space to approximately 10-30 of its initial size, which should be enough for most (if not all) problems.

If you need to do as few iterations as possible, you can terminate when the interval gets small, but try to do a relative comparison of the bounds, not just an absolute one. The reason for this is that doubles can never give you more than 15 decimal digits of precision so if the search space contains large numbers (say on the order of billions), you can never get an absolute difference of less than 10-7.

The last paragraph suggests doing a relative comparison, and not just an absolute one. What does that mean?

Answer 1

The last paragraph explains the issue with using the absolute difference:

If you need to do as few iterations as possible, you can terminate when the interval gets small, but try to do a relative comparison of the bounds, not just an absolute one. The reason for this is that doubles can never give you more than 15 decimal digits of precision so if the search space contains large numbers (say on the order of billions), you can never get an absolute difference of less than 10-7.

The absolute difference between a and b is

auto diff = std::abs(a - b);
if (diff < 0.00000001) break;

As floating point numbers have only limited number of significant digits, with large absolute values you may never see an absolute difference as small as 1e-7.

Relative difference does not depend on the magnitude of the compared values:

auto rel_diff = std::abs( a - b) / a; 
if (rel_diff < 0.00000001) break;

In other words, typically the following evaluates to true:

double very_big_number = 100000000.0;
double very_small_number = 0.000000001;
auto ups = (very_big_number + very_small_number) == very_big_number;

The smallest difference you can meaningfully expect from two big floating point numbers is in their last significant digit, which can be much larger in magnitude than eg 1e-7.