[boost] Re: Numeric Conversion Formal Review

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2003-12-12 19:43:42

Guillaume Melquiond wrote:
> Le ven 12/12/2003 à 21:24, Fernando Cacciola a écrit :
>> Guillaume Melquiond wrote:
>
> [...]
>
>>> So I'm not sure what the best thing to do is. At least, the
>>> documentation should mention the default rounding to nearest is a
>>> strange one. But it may be worthwhile to use a more thorough
>>> implementation.
>>>
>>> And rather than only relying only on floor and ceil, maybe a third
>>> function could be used (it's just a quick thought, there probably
>>> are some drawbacks).
>>>
>> OK, I think I should try to figure out a corrected implementation
>> that ties to even as most people would expect.
>> If you'd like to suggest something I'd appreciate it.
>
> Rounding to nearest with ties to even is hard when the only available
> functions are floor and ceil. I'm not even sure that it is possible
> for
> an udt: you need the user to provide a "good" subtraction.
>
>   a = floor(x); // only works inside the range
>   b = ceil(x);  // not at the boundaries
>   c = (x - a) - (b - x); // the "good" subtraction
>   if (c < 0) return a;
>   else if (c > 0) return b;
>   else return 2 * floor(b / 2); // needs to behave sanely
>
> It's quite ugly. It's why I was suggesting to rely on a third function
> just for this rounding. Unfortunately the current C++ standard isn't
> at
> all as good as C99 when it comes to rounding functions (C99 provides
> floor, ceil, rint, round, lround, and a few others). So in order to
> use
> them, you have to hope there is a C library laying around.
>
OK, here's what I'll do:
The "Round" policy will take itself a "good substraction" functoid and the
default implementation will be the one you've shown.
UDTs can be wild, so the user will have to know if this default
implementation (parametrized on the proper good substraction) actually
works. If it does, she can use it, otherwise, a specialized "Round" will
have to be provided.

> For binary floating-point numbers, there is a funny method to find the
> rounding of a positive number f (I'm not suggesting to use it, it's
> only
> an anecdote). Let's call M the biggest integer such that 2M-1 is
> representable (M = 2^23 for simple precision).
>
>   if (f >= M) return f;    // f is already an integer
>   else return (f + M) - M; // f+M will round f
>
> And obviously it won't work at all for an udt. And for a
> floating-point
> type, the binary representation must be known in order to compute M.
>
Interesting... good to know.

>>>>> In the definition part of the documentation, the notions of
>>>>> "range"
>>>>> of a
>>>>> type and "overflow" don't match the later explanation of float to
>>>>> int rounding.
>>>> I can't find what 'later explanation' are you referring to... or I
>>>> don't see the error :-)
>>>> Can you be more specific?
>>>
>>> In the definition part, you explain a value is out of range if it is
>>> smaller than the smallest target value or bigger than the biggest
>>> target value. But, in the rounding to integer part, a value is out
>>> of range if
>>> it is outside of the destination range plus a fuzz (-1/0, -0.5/+0.5,
>>> 0/+1). Maybe I'm misunderstanding the definitions.
>>>
>> hmmm, help me out... I still don't follow.....
>>
>> Considering that the "value" being used in the definition of
>> overflow is an "abstract" value, not a "typed" value in any
>> particular format, why is it not true that given: H=the biggest
>> target (typed) value, then any N>abt(H) is out-of-range w.r.t to the
>> target type?
>> This is what the definition says.
>>
>> IOW, how is it that the value is out if it's outside "Range(T) +
>> something"? Why plus something?
>
> Now I'm quite sure I misunderstood the whole idea of these "abstract"
> values.

You're not alone :-) I definitely need to extend the description of this
thing.

> Unfortunately, even after reading the documentation one more
> time, I still don't understand.
>
It might be the case that the "abstract value" idea is simply way too wrong
:-)
Let's see,

> So here is what made me wince. As you said it yourself: H=the biggest
> target (typed) value, then any N>abt(H) is out-of-range w.r.t to the
> target type.
>
> Now if we take a look at the documentation about float to int
> rounding,
> we can read: round_to_zero |--> [...] && (s <  S(HighestT)+S(1)).
>
> So now I'm lost: it seems the definition of overflow has changed.
> However it may only be because I don't understand what this notion of
> abstract value is.
>
OK, let me try to explain it:

NOTE: In the sequel I will use the classic notation "T:v" to denote a value
'v' of ype 'T'

For those definitions I first gathered as much formal information as I could
(and find too little, actually); then tried to fill in the gaps.
The first thing I noticed was that the properties of the result of a
conversion are very hard to specify in general terms since the connection
between the source and taget values is format specific.
Thus, my problem was how to give _any_ definition about overflow or rounding
without a mean to make that connection. I couldn't go on a case by case
basis since numeric formats are not specified by the standard.
Then I figured that I can view a conversion as a two step process were a
common ground is placed in the middle: To convert S:s to T:t means to take
's' from S, put in on the common ground, then get the 's' from the common
ground and put it back into T.
This common ground, call it 'G', is used to view the convertion as
trampolining over G: S->G->T.
G cannot be a type since there is no master type that can be used as long as
C++ is concerned, so G is a mathematical set of actual numbers (not numbers
within a computer)
For example:
Suppose I need to define to properties of the result of converting s=S(1/3)
to T, independently of the specific formats of S and T. I cannot define the
result this way but I can say something about its boundary conditions.
What I can do is to focus on the hipotetical existence of the actual number
1/3 (with all its infinite digits) independetly of the number as currently
represented by S (the value 's'); and then think about the boundary
conditions of represeting that actual number on T.
By stepping over the axiomatic existence of an hypotetical function
"N=abt(n)" which returns the actual number whose representation is n, and
another hypotetical function rep<T>(N) which returns the representation of
the actual number N in a given type T, then the conversion can be lously
defined as:  S:s->T <=> S=abt(s), T:t=rep<T>(S);
This definition is trampolining on the actual set of mathematical numbers to
"put s into a common ground then take it from there".

abt() and rep() are just theoretical functions which don't exist, so the
defiunition above might seem at first actually empty.
However, the common ground allowed me to figure out how to characterize the
boundary conditions of a conversion without knowldege of the actual formats
involved.
The numbers as they exist in this common ground (outside the computer) are
"abstract"... abstract because they do not exist... they'are just a resource
of this definitions.
Their counterparts, the numbers as represented by a given format, are
"typed".... typed because they exist as rendered by the format used.
{s}=abt(s) returns the abstract value s' that corresponds to the typed value
s.
s=rep<S>( {s} ) returns the typed value s that corresponds to the abstract
value {s}.

NOTE: I'm using here a different convetion from the one used in the
document. The reason is that the operation rep should better indicte the
type upon it is operating, so the syntax "rep<type>" is used here.

So,

Looking at the following:

> we can read: round_to_zero |--> [...] && (s <  S(HighestT)+S(1)).

HighestT is the highest representable number of type T, so the upper range
of  T is abt(HighestT). Call it {HighestT}

S(HighestT)+S(1) is a typed value of type S, call it "q" It's abstraction is
abt(q). Call it: {q}

The conversion is given by:

rep<T>( round_to_zero( {s}) ) )

Now here lies the usefulness of abstract values:
{HighestT}, {q}, {s} and round_to_zero({s}) can all be compared, even if
hypotetically (by a human) by putting the T's and S's in context.

Specifically: given that T is a builtin integer and S a builtin float, we
know that:

{q}={HighestT}+{1}
thus, If {s} is < {q}, then round_to_zero({s}) is exactly equal to
{HighestT}.

The condition indicates when the abstract value "round_to_zero( {s} )"
won't overflow, i.e., <={HighestT}.

Fernando Cacciola
SciSoft