Re: Explicit vs Implicit bounds on range and precision
> Date: Wed, 14 Jul 2010 14:00:50 -0400
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> From: Michel Hack <hack@xxxxxxxxxxxxxx>
> Subject: Explicit vs Implicit bounds on range and precision
>
> (Was: Subject: Re: Proposal for a new structure of the standard)
>
> Both Vincent Lefèvre and I have been arguing that entities bounded
> only by available resources should be treated as "infinite" sets of
> representations, in contrast to representations with bounds derived
> from their format.
Michel,
I'm OK with that. I'm even OK with calling it something
informally related to infinity, like colloquially infinite
or practically infinite.
(So long as you are willing to concede that practically
no problems can be solved on data structures that are
practically infinite. :-)
No, the terminology is fine if a bit informal.
It is not that to which I object.
Nor am I trying to have any limits put into the standard.
Limits like the size of the largest finite number or how
many digits of precision can exist. Indeed any such limits
would be foolish in light of Moore's law.
(And, Baker, we are discussing the finitude or infinitude
of the collection of sets at level 2. Not whether they
contain elements that are unbounded at one end or the
other.)
No, my objection is related to the practical matter of what
sets are useful at level 2 for any given interval type, not
for interval types in general or the standard as a whole.
I think that Vincent believes I am trying to put arbitrary
limits on the range & precision of things that can be
represented in an interval type. I am not. But there ARE
limits to both for any given interval type even if there
are none for intervals as a whole.
Perhaps more examples might help. (Perhaps not. :-)
A simple example first:
Let us say we wish to define an interval datatype in the
inf-sup style with its endpoints implemented as Binary64
numbers.
In that case the sets that live at level 2 are those
contiguous subsets of the Reals for which each endpoint
can be found in the level 2 set of the Binary64 numbers.
The mapping from the Reals to this set (the hull operation)
goes from the set in the Reals to some element at level 2
which wholly contains those Reals. It may be the least or
tightest such set or some other. It is not important yet.
But the mapping from level 2 to the representations at
level 3 is EXACT. Every representation has an element at
level 2 to land on & every element at level 2 may be
represented by one or more objects at level 3.
Indeed, the set at level 2 was CHOSEN so that this would
be true.
Arithmetic is done by moving the represented intervals to
level 2, doing the arithmetic at level 1, mapping the result
back onto level 2 via (some) hull operation, & finding an
exact representation at level 3 for that result.
A less simple example & perhaps more to the point:
Now let me use a mid-rad case to show how this gets us out
of (most of) our specification difficulty with them.
Let us say we want to define a midrad datatype with 125
decimal digits with 5 exponent digits for the midpoint &
25 digits with 3 exponent digits for the radius. Then the
set chosen at level 2 is EXACTLY all possible M +/- R with
elements chosen from these floating-point types. They
need not be all distinct but every element at level 2 has
at least one representation & every representation has an
element at level 2.
Arithmetic is done as before: Exact map from representation
to level 2, then to level 1, arithmetic among the Reals,
(some) hull down to level 2, & back to bits again with an
exact representation of that interval at level 3.
Now let us suppose that during your quadrature of that
infinite product of cosines you discovered that the resulting
integral contains pi/8 & you want to narrow it further to
see if that is the answer.
So you move your entire problem to a 1200 digit precision
type with a 7 digit exponent range together with 100 digits
& 4 exponent digits in the radius.
All your work is now possible here. There are no arbitrary
bounds on the range or precision of your numbers beyond
those that you have asked for. Some of your previous result
may transfer. The transfer is exact as the previous level 2
set is a proper subset of the current level 2 set.
And, lo & behold, you discover that your new, far narrower
interval EXCLUDES pi/8 by a very tiny amount & you have an
interesting result on your hands.
(It could happen. It DID happen to a friend of mine. :-)
I guess I have strayed from the topic a bit here. Sorry.
The bottom line is that the set of intervals at level 2 is
chosen to exactly match what you can represent at level 3
WITHOUT making any reference to it at all.
Each precision (& style) has its own level 2 set. All are
subsets of higher precision (& range) sets. And all are
finite even if the one that sucks up all your resources is
practically infinite.
Perhaps you think that a cheat & perhaps it is.
But it keeps all the language at the level of set theory
& leaves issues of bit patterns out of it.
It has nothing to do with infinite sets. It places no
bounds on finite but unbounded sets. It has nothing to
do with tightness (although that comes into it later).
And it meets the FTIA if everyone plays fair.
>
> . . .
>
> Michel.
Things would be much more difficult to define if we said
that the set of intervals at level 2 were chosen from the
set of all contiguous intervals with endpoints that are
either dyadic rationals (a/2^b) or decadal rationals
(a/10^b) for arbitrary integers a & b.
While this is true, it is not useful.
And THIS is where issues of tightness & uniqueness come
into play. I can certainly map Real intervals such as
[-pi,pi] onto either of these sets. But I cannot define
a hull operation on these sets without mention of the
representation limitations of the target interval type.
I cannot define a tightest hull as there IS no tightest
hull among these rationals. Nor can I define a unique
hull of any flavor.
All that is simpler if the set at level 2 is exactly the
set I can represent.
Not always trivial but much simpler.
Yours,
Dan