Re: Guillaume's alternative definition(s) of "com"
On 2013-02-16 15:40:11 +0000, John Pryce wrote:
> The dac, together with the bounded input(s), suffices to prove that
> all the intermediate values, as well as the output, are
> mathematically bounded, by compactness. (A continuous function on a
> compact set is bounded.)
>
> I think this was my reason for saying that com should describe what
> actually happens at Level 2, rather than what ideally happens at
> Level 1. Namely, I claim that your i2+o2 can never produce more
> informative results than what such a compactness argument can
> produce using i1+o1. And that there is no other good reason to move
> to i2 and/or o2.
I agree. This is what I said in our private discussion in November:
------------------------------------------------------------------------
From: Vincent Lefevre <vincent@xxxxxxxxxx>
To: John Pryce <j.d.pryce@xxxxxxxxxx>
Subject: Re: Re-starting decorations: a query
Date: Thu, 8 Nov 2012 13:40:38 +0100
Message-ID: <20121108124038.GB5980@xxxxxxxxxxxxxxxxxxxx>
On 2012-11-07 17:01:55 +0000, John Pryce wrote:
> On 7 Nov 2012, at 15:00, John Pryce wrote:
> > Map the resulting
> > xx to (xx,dx) where dx is the tightest decoration
> > for the identity function Id() over xx,
> > i.e. the tightest such p_dx(Id,xx) holds.
> >
> > This is decoration-scheme-independent. For the 5-decoration scheme it says
> > Empty gets emp.
> > Nonempty bounded gets dac.
> > Unbounded gets def.
>
> Sorry, that's nonsense, I was getting mixed up with the bnd
> decoration. Should say
> Empty gets emp.
> Nonempty gets dac.
Yes. Actually that depends on the meaning of dac. I was wondering
whether the users of the continuity information also needed the
boundness. Now, even if they need it, I think that just "defined
and continuity" is sufficient because they can easily check that
the input is bounded (or they already know it) and the image of a
compact by a dac function is a compact, thus bounded.
> Suppose we introduce a com decoration for "common evaluation", defined by
> p_com(f,xx) : xx is a nonempty bounded box and f is
> everywhere defined and continuous on it.
>
> (Hence f is bounded on it by compactness). Then the effect of domain() is
> Empty gets emp.
> Nonempty bounded gets com.
> Unbounded gets dac.
Yes, but my point above suggests that a com decoration wouldn't be
necessary. I mean that if the inputs of an expression are common
intervals (i.e. bounded, non empty), then the decoration of the
output by a "good" implementation cannot be dac. Indeed, if all
functions in the expression are dac, then all intermediate results
would be compact intervals, thus the decoration of the output would
normally be com[*]; otherwise the decoration of the output would be
either def or emp.
Thus in practice, introducing com wouldn't provide additional
information on the expression or the output. The only difference
would occur if an unbounded interval is provided as an input, and
the com/dac difference would just be an information on the input.
I don't think this justifies an additional decoration.
[*] except if an implementation degrades com to dac, but there's no
good reason to do so.
------------------------------------------------------------------------
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)