Re: [lmi] TAOCP [4.2.2]: to what can zero be "essentially equal"?

[Greg Chicares]

On 2018-02-17 17:23, Vadim Zeitlin wrote:
> On Thu, 15 Feb 2018 00:45:15 +0000 Greg Chicares <address@hidden> wrote:
[...in 'materially_equal.hpp'...]
> GC> /// This is the "essentially equal to" operator defined in Knuth,
> GC> /// TAOCP, volume 2, section 4.2.2, equation (34), on page 219 of the
> GC> /// second edition.
> GC> 
> GC> But is that comment rigorous, even though I seem to have translated
> GC> equation (34) faithfully?
> 
>  AFAICS it isn't, the condition is indeed sufficient but not required.
> 
> GC> (1) Knuth says that satisfying this test implies "essential" equality,
> GC> so it's a sufficient condition, and not a (biconditional) definition.
> GC> But I don't find anything in the text that's closer to a definition.
> 
>  Although it's also given as an implication, rather than definition, I find
> it useful to think in terms of the neighbourhoods defined in the text just
> before this group of equations. If N(u) is the neighbourhood of u (with
> the given implicit choice of fixed epsilon), then
> 
>       u ??? v ??? u ??? N(v)  ???  v ??? N(u)
> 
> which looks like a nice definition.

Yes, it does. Thanks.

> GC> (2) Can any nonzero value be considered "essentially" equal to zero?
> 
>  According to the definition above, yes.

Similarly, in the 'system_test' makefile target, we filter out
regressions that involve either a relative error less than 1e-15
or an absolute error less than 0.01; the latter condition allows
us to accept 0.0001 as essentially equal to zero.

> GC> The above code determines that 1e-100 is not essentially zero for the
> GC> given tolerance of 1e-13;
> 
>  This is incompatible with the definition above. Whether we want to use
> this definition or not is another question.
> 
> GC> is that sensible? and would Knuth agree or disagree with that
> GC> conclusion--or has he perhaps chosen to leave the answer undefined?
> 
>  This is hard to say. All I can provide here is a cop out: I think it's
> sensible in Knuth's framework, but I'm not so sure that it is for the lmi
> use of it. But I'm not exactly sure how does lmi use it exactly, e.g.
> looking at the code in premium_tax::calculate_load() I have really no idea
> what is it supposed to do when x or y are 0
In that case, the purpose is to avoid catastrophic cancellation
by performing a calculation two ways, choosing either
 - x, if they differ materially, because then x is more accurate; or
 - y, if they don't differ materially, because then y is more precise.
I don't think either can be zero unless they're both exactly zero, but
I don't want to try to prove that today. For now, I'll content myself
with adding examples to the unit test that refer back to this thread.