"Relative Comparison" 和 "Absolute Comparison" 是什么意思？

Question

引用自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.

最后一段建议做相对比较，而不仅仅是绝对比较。这是什么意思？

Answer 1

最后一段解释了使用绝对差的问题：

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.

a和b的绝对差是

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

由于浮点数的有效数字位数有限，如果绝对值很大，您可能永远看不到像 1e-7.

这样小的绝对差值

相对差异不依赖于比较值的大小：

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

换句话说，通常以下计算结果为真：

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

两个大浮点数的最小差异是它们的最后一个有效数字，其幅度可能比 1e-7.

大得多